# increasing sequence specific properties

I am doing some olympiad exercises and have difficulties with the following one:

Consider a sequence $a_1,a_2,...$ which is strictly monotonically increasing and $a_1,a_2,...\in\mathbb N$

Now I know that $a_2=2$ and $a_{xy}=a_xa_y$ if $\gcd(x,y)=1$

I would like to show that $a_n=n$

The first thing I did was to write down the first values $a_1,2,a_3,a_4,a_5,2a_3,...$

Now I think it is necessary to separate cases where n is odd and even but I have no idea how to do it, may you could help me.

EDIT: As discussed in the comments, it seems the sequence $a_n=n$ is not unique, but I would like to prove $a_n=n$ using my assumptions, no matter if it is unique or not. If you see a different explicit formula I would also be interested in.

-

Let $f(x)=a_x$. The strict monotonicity hypothesis can be rewritten as $f(j)-f(i) \geq j-i$ for any $i<j$.

Denote by $\Omega$ the set of all integers $x \geq 1$ such that $f(x)=x$. Since $f$ is strictly monotonic, $\Omega$ is “convex” : if $a<b$ are in $\Omega$ then all the integers between $a$ and $b$ are in $\Omega$ also.

Also, $\Omega$ is weakly multiplicative : if $a,b\in \Omega$ are coprime, then $ab\in \Omega$.

We have $f(15)=f(3)f(5)$ and $f(18)=2f(9)$, so $2f(9) \geq f(3)f(5)+3$ by strict monotonicity. On the other hand, $f(10)=2f(5)$ and hence $2f(5) \geq f(9)+1$ by strict monotonicity. Combining those two inequalities,

$$4f(5) \geq 2f(9)+2 \geq f(3)f(5)+5 \gt f(3)f(5)$$

This implies $4 \gt f(3)$, so $f(3)=3$ and hence $3\in \Omega$.

So $6=2\times 3 \in \Omega$ since $\Omega$ is weakly multiplicative.

Then $2\in \Omega,6\in \Omega$ yields $[2,6] \subseteq \Omega$ since $\Omega$ is convex.

So $15=3\times 5 \in \Omega$ since $\Omega$ is weakly multiplicative.

Then $2\in \Omega,15\in \Omega$ yields $[2,15] \subseteq \Omega$ since $\Omega$ is convex.

So $42=3\times 14 \in \Omega$ since $\Omega$ is weakly multiplicative.

Then $2\in \Omega,42\in \Omega$ yields $[2,42] \subseteq \Omega$ since $\Omega$ is convex.

More generally, if we define a sequence $(u_k)$ by $u_1=5$ and $u_{k+1}=3u_k-1$ then by induction, every $u_k$ is in $\Omega$, qed.

UPDATE (in answer to a comment) Here is how the induction works :

Suppose $u_k \in \Omega$. As $u_k$ is congruent to $2$ modulo $3$, it is coprime to $3$, so $3u_k \in \Omega$ since $\Omega$ is weakly multiplicative. Then $2$ and $3u_k$ are both in $\Omega$, so $[2,3u_k] \subseteq \Omega$ since $\Omega$ is convex. In particular, $3u_k-1 \in \Omega$, i.e. $u_{k+1} \in \Omega$. So $\Omega$ contains all the $u_k$ and finally $\Omega$ contains all the positive integers.

-
Thank you for your help, could you explain the last part a little bit more in detail? Why $u_1=5$? –  Alexander Mar 26 '13 at 16:26
@Alexander : you can take $u_1=2$ if you prefer. Please see my edit above –  Ewan Delanoy Mar 26 '13 at 16:38