3
$\begingroup$

I'm a bit stuck on this... my only thought was to use second induction on $n$, which works well enough for the case where $n$ is composite and has two or more distinct prime factors, but if $n$ is prime or a prime power the induction hypothesis does nothing, so I'm thinking there must be another way. Any ideas?

  • 1
    This may be a duplicate of http://math.stackexchange.com/q/2593/15432011-09-07

2 Answers 2

8

As Arturo's answer (and André's comment) points out, this question is incorrect.

But there are related statements that are, in fact, true. Erdős showed the interesting

Theorem. If $f$ is an increasing multiplicative function, then there exists a constant $\alpha \geq 0$ such that $f(n) = n^{\alpha}$ for all $n \geq 1$.

Here, "increasing" means that $f(n) \geq f(m)$ if $n \geq m$. Also, a function $f$ is said to be multiplicative if it satisfies $f(nm) = f(n) \cdot f(m)$ for all relatively prime $n, m$. This is precisely the condition satisfied by the sequence $a_n$ in the question. For the sake of consistency, we will use the notation $f(n)$ in place of $a_n$.

Now, coming to the question, if we also add the condition that $f$ is increasing, then by the theorem, $f(n) = n^{\alpha}$ for some $\alpha$. The base condition $f(2) = 2$ guarantees that the only possible function satisfying all these conditions is $f(n) = n$, corresponding to $\alpha = 1$.

For the theorem I quote, please refer to A new proof of Erdős's theorem on Monotone Multiplicative Functions by Everett Howe (JSTOR link: here). I cannot be fully sure about this, but I do remember seeing some direct/elementary proofs for the special case when $f(2)$ is equal to $2$. I think this is false. I now think the easier proofs deal with the special case when $f$ is integer-valued. Thanks to Michael Lugo and Mark Bennet pointing this out.

  • 0
    @Mark I agree. See my previous comment.2011-09-06
4

Let $a_1=1$, $a_2=2$. For each positive integer $k\gt 1$, let $a_{2^k}=c_{2^k}$ be arbitrary; and for each prime $p$ and positive integer $\ell\gt 0$, let $a_{p^{\ell}} = c_{p^{\ell}}$ be arbitrary. For a positive integer $m$, factor $m$ into primes $m = p_1^{\alpha_1}\cdots p_r^{\alpha_r},$ $\alpha_i\gt 0$, and $p_1\lt p_2\lt\cdots \lt p_r$ primes. Then define $\begin{align*} a_m &= a_{p_1^{\alpha_1}}\times\cdots\times a_{p_r^{\alpha_r}}\\ &= c_{p_1^{\alpha_1}}\times\cdots\times c_{p_r^{\alpha_r}} \end{align*}$ Satisfies the given conditions; but unless $c_{p^k}=p^k$, the conclusion will be false.

For example, define $a_m$, with $m$ factored as above, to be $a_m = 2^{\alpha_1+\cdots + \alpha_r}$. Then $a_{mn}=a_ma_n$ for all $m,n$ (not just those that are coprime), but $a_m$ is always a power of $2$.