Help me understand this sequence problem

Question

Today, I encountered a problem in "Problem-Solving Strategies" by Arthur Engel (Chapter $9$. Sequences, page-$225$):

Prove that there does not exist a monotonically increasing sequence of nonnegative integers $a_1,a_2,a_3,...$ so that $a_{nm}=a_n+a_m$ for all $n,m \in \mathbb{N}$.

I could not prove it. So, I checked the solution provided in the book. It was:

Solution: For a strictly increasing function $a_n$, we have $a_{2n}=a_n+a_2 \geq a_2+(n-1)$. This is impossible for any finite value $a_2$.

I don't quite understand the proof. I just cannot insert $(n-1)$ in the picture. Is the solution correct? If it is, what am I missing?

Answer 1

See if the follwoing explanation is of any help.

Assume on the contrary that there exists a monotonically increasing sequence $ \{ a_n \}_{n \ge 1}$ such that $a_n \in \mathbb{N} \cup \{ 0 \}$ for all $n \in \mathbb{N}$ and $a_{nm} = a_n + a_m$ for all $n, m \in \mathbb{N}$.

Then since $ \{ a_n \}_{n \ge 1}$ is a monotonically increasing sequence of integers, we must have $a_{n+1}-a_n \ge 1$ for all $n \in \mathbb{N}$ yielding $a_{2^{k+1}}-a_{2^k} \ge 2^{k+1}-2^k$ for all $k \in N$.

Now see that it follows from induction that $a_{2^k}=ka_2$ for all $k \in N$, and thus we have $$a_{2^{k+1}}-a_{2^k}=(k+1)a_2-ka_2=a_2 \ge 2^{k+1}-2^k=2^k$$ which is not possible for any finite value of $a_2$.

Answer 2

Trusting that "monotonically increasing" means "strictly increasing" (so $a_n>a_{n-1}$ for all $n$), then an easy induction, starting from $a_1≥0$ shows that $a_n≥n-1$.

To conclude, look at terms of the form $a_{2^kn}$. Another easy induction shows that $$a_{2^kn}=a_n+ka_2$$ But then we deduce that $$a_n+ka_2≥2^kn-1\implies a_n≥(2^kn-1)- ka_2$$ But then letting $k\to\infty$ yields a contradiction.