About sequences of positive integers

Prove there is no sequence of positive integers $(x_n)_{n \ge 1}$ so that: $$ x_{n+2} = x_{n+1} + x_{x_n} \quad \forall n\ge1 $$

I think the idea is to find two different values for the same index.

Solution 1:

If there was such a sequence, apart from possibly the first term, it would be strictly increasing. We'd have

\begin{align} x_3 &= x_2 + x_{x_1} \geqslant 1 + 1 = 2\\ x_4 &= x_3 + x_{x_2} \geqslant 2 + 1 = 3\\ x_5 &= x_4 + x_{x_3} \geqslant 3 + 1 = 4\\ x_6 &= x_5 + x_{x_4} \geqslant 4 + x_3 \geqslant 6\\ x_7 &= x_6 + x_{x_5} \geqslant 6 + x_4 \geqslant 9, \end{align}

and thus $x_k \geqslant k + 2$ for all $k \geqslant 7$. But then we'd have

$$x_{n+2} = x_{n+1} + x_{x_n} > x_{x_n} \geqslant x_{n+2}$$

for $n \geqslant 7$. Which of course is impossible.