2
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ You're right. Actually this is what I was looking for. $\endgroup$ Dec 6 '15 at 17:50
  • 1
    $\begingroup$ The answer in your book should have said $a_{2n}-a_n=a_2 \ge n$ which is not possible for any finite value of $a_2$. $\endgroup$ Dec 6 '15 at 17:58
  • 1
    $\begingroup$ Yes. You're right. It just left me clueless. Thanks you so much. $\endgroup$ Dec 6 '15 at 18:02
2
$\begingroup$

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.

$\endgroup$

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.