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}$


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


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

But how to continue?

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

  • $\begingroup$ Wow, greats prove my friend :) $\endgroup$ – Jon.Don Sep 12 '15 at 17:21
  • $\begingroup$ hm what if a number of complex x < q such that ax different x? $\endgroup$ – Jon.Don Sep 12 '15 at 18:19
  • $\begingroup$ @Jon.Don by definition of $q$, for every $x < q$ we have $a_x = x$ $\endgroup$ – Ant Sep 12 '15 at 18:57
  • $\begingroup$ How do you know q + 1 is complex? $\endgroup$ – Jon.Don Sep 12 '15 at 19:01
  • $\begingroup$ @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 $\endgroup$ – Ant Sep 12 '15 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.