# Growing sequence of $a_n$

Question: Find all strictly increasing sequences $a_n$ , such that $a_2 = 2$, and $a_{mn} = a_m\cdot a_n$ for all integers $m, n$

How can I solve it? In particular, I'd like to show that $a_n = n$ is the only such sequence.

My work

I have something like this:

$a_{1}$ = 1

$a_{2}$ = 2

$a_{4}$ = 4

Let m = 3 and n = 2

I designate $a_{3}$

So:

$$a_{1} < a_{2} < a_{3} < a_{4} < \dots < a_{n}$$

So:

$$1 < 2 < a_{3} < 4 \implies a_{3} = 3$$

But how to continue?

• what does "of the total words" mean? Also, what have you tried? – Ant Sep 11 '15 at 18:30
• $$a_4=a_{(2)(2)}=(a_2)(a_2)=(2)(2)=4$$ – nathan.j.mcdougall Sep 11 '15 at 21:05
• @Jon.Don No problem. Now can you find, for all positive integers $n$, a general form for $a_{2^n}$? – nathan.j.mcdougall Sep 11 '15 at 21:08
• Nathan, not yet :( how I can to this? – Jon.Don Sep 12 '15 at 6:08
• How I can formalize the solution? – Jon.Don Sep 12 '15 at 8:18

Since the sequence is strictly increasing, it turns out that it's pretty easy. I believe it is also true if we allow non-strict inequalities, but I haven't been able to prove it.

First, it is easy to see that this sequence is determined by the values we assign to prime numbers. So if $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ then $$a_n = a_{p_1}^{\alpha_1} \cdots a_{p_k}^{\alpha_k}$$

From this it's clear that $a_{2^n} = 2^n$. It is also clear that $a_n = n$ is a sequence which works.

We want to show that is the only sequence.

The op already found that $a_1 = 1$ and $a_3 = 3$. Now suppose there exists (some) primes $p$ such that $a_p \neq p$. Let $q$ be the minimum of such numbers (ie, $a_n = n$ for all $n < p$).

Now since $a_{q-1} = q-1$, we have $a_q \ge q$. We want to show that $a_q > q$ is impossible.

And indeed, $a_{q+1}$ is not a prime and all of his prime factors are less than $q$. Since the prime-indexed numbers less than $q$ are just the primes themselves, it follows that $a_{q+1} = q+1$. But then $$q-1 < a_q < q+1$$

So the only possibility is that $a_q = q$ for all primes and this implies $a_n = n$ for all $n$

• Wow, greats prove my friend :) – Jon.Don Sep 12 '15 at 17:21
• hm what if a number of complex x < q such that ax different x? – Jon.Don Sep 12 '15 at 18:19
• @Jon.Don by definition of $q$, for every $x < q$ we have $a_x = x$ – Ant Sep 12 '15 at 18:57
• How do you know q + 1 is complex? – Jon.Don Sep 12 '15 at 19:01
• @Jon.Don You should say composite, complex refers to imaginary numbers and stuff. However, since $q$ is prime (hence odd), $q+1$ is even, hence divisible by $2$, hence composite – Ant Sep 12 '15 at 19:03