41st Balkan Mathematical Olympiad

Denote the given equation by (1). Note that if $a_n\le k$, for $n\ge 2$, we get a contradiction, so $a_n>k$ for all $n\ge 2$. Then (1) becomes $$a_{n+2}=\frac{a_n(a_{n+1}+k)}{a_{n+1}-k}.$$ We deduce that $a_{n+2}\ge a_n+1$. Now $a_{n+2}=\frac{a_n(a_{n+1}+k)}{a_{n+1}-k}$ so $a_{n+1}-k\mid a_n(a_{n+1}+k)$. However, $a_{n+1}-k\mid a_n(a_{n+1}-k)$ and subtracting gives $a_{n+1}-k\mid 2k{a}_n$. Let $r\ge 1$ such that $r(a_{n+1}-k)=2k{a}_n$. Applying (1), $a_{n+2}=a_n+r$. We apply (1) again to get $$\begin{array}{rl}{a}_{n+3}& =\frac{a_{n+1}(a_{n+2}+k)}{a_{n+2}-k}=\frac{a_{n+1}(a_n+r+k)}{a_n+r-k}=a_{n+1}+\frac{2k{a}_{n+1}}{a_n+r-k}\\ & =a_{n+1}+\frac{2k{a}_{n+1}}{\frac{r(a_{n+1}-k)}{2k}+r-k}=a_{n+1}+\frac{4k^2{a}_{n+1}}{r{a}_{n+1}+rk-2k^2}.\end{array}$$ Thus, $r{a}_{n+1}+rk-2k^2\mid 4k^2{a}_{n+1}$ so $r{a}_{n+1}+rk-2k^2\le 4k^2{a}_{n+1}$. If $r\ge 4k^2$ we get a contradiction, so $r<4k^2$. Now we use the fact that if $a,b,c\in \mathbb{Z}$, $a,b,c\ne 0$ then there is a finite number of natural numbers $x$ for which $ax+b\mid c$. So if $rk\ne 2k^2$ (whence $r\ne 2k$), we get a finite number of possibilities for $a_{n+1}$ (which depends on $k$ but not on $r$!). Let $S$ be this finite set. On the other hand, if $r=2k$, it leads us to $a_{n+1}=a_n+k$. In short, for all $n\ge 2$ we either have $a_n\in S$ or $a_n=a_{n-1}+k$. But $a_{n+2}\ge a_n+1$ for all $n\ge 2$ so for $n$ sufficiently large, we can't have $a_n\in S$. So there exists $N\ge 2$ such that $a_n=a_{n-1}+k$ for all $n\ge N$. Using $a_{N+1}=a_N+k$ we use (backward) induction to get $a_n=a_{n-1}+k$ for all $n$ so $(a_n{)}_{n\ge 1}$ is an arithmetic progression of common difference $k$ and, conversely, these satisfy (1).