There is no sequence such that $a_{a_n}=a_{n+1}a_{n-1}-a_{n}^2$ 
Prove that there is no infinite sequence of natural numbers such that $a_{a_n}=a_{n+1}a_{n-1}-a_{n}^2$ for all $n\geq 2$.

This question is from a Belarusian math contest and any help is appreciated.
 A: Here's how to start.
The key to the whole problem is that the numbers must be natural, hence positive.  In particular, that means that $$a_{n+1}a_{n-1}>a_n^2$$
Hence, for all $n\ge 2$, either $a_{n+1}>a_n$ or $a_{n-1}>a_n$ (or both).  Suppose for some $n$ that $a_{n+1}\ge a_n$.  Now we must have $a_{n+2}>a_{n+1}$, and then $a_{n+3}>a_{n+2}$, hence the rest are increasing $$a_n\le a_{n+1}<a_{n+2}<a_{n+3}<\cdots$$
Thus the sequence as a whole has a (possibly empty, but definitely finite) segment where it is strictly decreasing, and then possibly two terms in a row are the same, and then after that all terms are strictly increasing.
Now I would consider how fast the sequence grows.  
A: Taking vadim123 idea:
We have $a_{n+1}>a_{n}$ or $a_{n-1}>a_{n}$.
If $a_{n-1}>a_{n}$ and since $a_{a_{n-1}}>0$ then $a_{n}a_{n-2}>a_{n-1}^2$ from which $a_{n-2}>a_{n-1}>a_{n}$.
Following this reasoning we have that the sequence $a_{n}$ is strictly decreasing, 
which is a contraction since all terms of this infinite sequence are natural numbers.
So $a_{n-1}< a_{n}$.
As vadim123 showed previously $a_n\le a_{n+1}<a_{n+2}<a_{n+3}<\cdots$.
Wlog assume $a_1< a_{2}<a_{3}<a_{4}<\cdots$, i.e. the sequence is stricly increasing.
We will use the fact that $a_{a_{n}}\geq a_{n}$ (since the sequence is strictlty increasing and $a_{n}\geq n$) repeatedly.
Let $N>1$ be such that $a_{n}>N$.
$a_{a_{n}}\geq a_{n}$
$a_{n+1}a_{n-1}>a_{n}^2+N$
$a_{n+1}a_{n-1}>Na_{n-1}+N$
$a_{n+1}>N+N/a_{n-1}$
$a_{n}>N+N/a_{n-2}$ and since $a_{n-2}<a_{n-1}$
$a_{n}>N+N/a_{n-1}$.
Again, from $a_{a_{n}}\geq a_{n}$ we have
$a_{n+1}a_{n-1}>a_{n}^2+N+N/a_{n-1}$
$a_{n+1}a_{n-1}>Na_{n-1}+N+N/a_{n-1}$
$a_{n+1}>N+N/a_{n-1}+N/a_{n-1}^2$
$a_{n}>N+N/a_{n-2}+N/a_{n-2}^2$
$a_{n}>N+N/a_{n-1}+N/a_{n-1}^2$.
Let $L=\sum_{i=0}^{\infty }1/a_{n}^i>1$.
Repeating the above process over and over we can see that
$a_{n}\geq NL$.
Again, from $a_{a_{n}}\geq a_{n}$ we have
$a_{n+1}a_{n-1}\geq a_{n}^2+NL$
$a_{n+1}a_{n-1}>NLa_{n-1}+NL$
$a_{n+1}>NL+NL/a_{n-1}$
$a_{n}>NL+NL/a_{n-2}$
$a_{n}>NL+NL/a_{n-1}$.  
Repeating the above process over and over we have:
$a_{n}\geq NL^k$ for all positive integers $k$, which is a contradiction since $\lim_{k \to \infty}NL^k=\infty$.
