Girls European Mathematical Olympiad

The answer is no. Suppose that there exist a sequence $(a_n)$ of positive integers satisfying the given condition. We will show that this will lead to a contradiction. For each $n\ge 2$ define $b_n=a_{n+1}-a_n$. Then, by assumption, for $n\ge 2$ we get $b_n=\sqrt{a_n+a_{n-1}}$ so that we have $$b_{n+1}^2-b_n^2=(a_{n+1}+a_n)-(a_n+a_{n-1})=(a_{n+1}-a_n)+(a_n-a_{n-1})=b_n+b_{n-1}.$$ Since each $a_n$ is a positive integer we see that $b_n$ is positive integer for $n\ge 2$ and the sequence $(b_n)$ is strictly increasing for $n\ge 3$. Thus $b_n+b_{n-1}=(b_n-b_{n-1})(b_n+b_{n-1})\ge (b_{n+1}+b_n)$, whence $b_{n-1}\ge b_{n+1}$ - a contradiction to increasing of the sequence $(b_i)$. Thus we conclude that there exists no sequence $(a_n)$ of positive integers satisfying the given condition of the problem.

---

Alternative solution.

Suppose that such a sequence exists. We will calculate its members one by one and get a contradiction. From the equality $a_3=a_2+\sqrt{a_2+a_1}$ it follows that $a_3>a_2$. Denote positive integers $\sqrt{a_3+a_2}$ by $b$ and $a_3$ by $a$, then we have $\sqrt{2a}>b$. Since $a_4=a+b$ and $a_5=a+b+\sqrt{2a+b}$ are positive integers, then $\sqrt{2a+b}$ is positive integer. Consider $a_6=a+b+\sqrt{2a+b}+\sqrt{2a+2b+\sqrt{2a+b}}$. Number $c=\sqrt{2a+2b+\sqrt{2a+b}}$ must be positive integer, obviously it is greater than $\sqrt{2a+b}$. But $$(\sqrt{2a+b}+1{)}^2=2a+b+2\sqrt{2a+b}+1=2a+2b+\sqrt{2a+b}+(\sqrt{2a+b}-b)+1>c^2.$$ So $\sqrt{2a+b}<c<\sqrt{2a+b}+1$ which is impossible.

---

Alternative solution.

We will show that there is no sequence $(a_n)$ of positive integers which consists of $N>5$ members and satisfies $$a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_n}(1)$$ for all $n=1,2,\dots ,N-2$. Moreover, we will describe all such sequences with five members. Since every $a_i$ is a positive integer it follows from (1) that there exists such positive integer $k$ (obviously $k$ depends on $n$) that $$a_{n+1}+a_n=k^2(2)$$ From (1) we have $(a_{n+2}-a_{n+1}{)}^2=a_{n+1}+a_n$, consider this equality as a quadratic equation with respect to $a_{n+1}$, $$a_{n+1}^2-(2a_{n+2}+1)a_{n+1}+a_{n+2}^2-a_n=0.$$ Obviously its solutions are $(a_{n+1}{)}_{1/2}=\frac{2a_{n+2}+1\pm \sqrt{D}}{2}$, where $$D=4(a_n+a_{n+2})+1.(3)$$ Since $a_{n+2}>a_{n+1}$ we have $$a_{n+1}=\frac{2a_{n+2}+1-\sqrt{D}}{2}.$$ From the last equality, using that $a_{n+1}$ and $a_{n+2}$ are positive integers, we conclude that $D$ is a square of some odd number i.e. $D=(2m+1{)}^2$ for some positive integer $m\in \mathbb{N}$, substitute this into (3): $$a_n+a_{n+2}=m(m+1).(4)$$ Now adding $a_n$ to both sides of (1) and using (2) and (4) we get $m(m+1)=k^2+k$ whence $m=k$. So $$\{\begin{array}{l}{a}_n+a_{n+1}=k^2\\ a_n+a_{n+2}=k^2+k\end{array}(5)$$ for some positive integer $k$ (recall that $k$ depends on $n$). Write equations (5) for $n=2$ and $n=3$, then for some positive integers $k$ and $l$ we get $$\{\begin{array}{l}{a}_2+a_3=k^2\\ a_2+a_4=k^2+k\\ a_3+a_4=l^2\\ a_3+a_5=l^2+l\end{array}.(6)$$ Solution of this linear system is $$a_2=\frac{2k^2-l^2+k}{2},a_3=\frac{l^2-k}{2},a_4=\frac{l^2+k}{2},a_5=\frac{l^2+2l+k}{2}.(7)$$ From $a_2<a_4$ we obtain $k^2<l^2$ hence $k<l$. Consider $a_6$: $$a_6=a_5+\sqrt{a_5+a_4}=a_5+\sqrt{l^2+l+k}.$$ Since $0<k<l$ we have $l^2<l^2+l+k<(l+1{)}^2$. So $a_6$ cannot be integer i.e. there is no such sequence with six or more members. To find all required sequences with five members we must find positive integers $a_2,a_3,a_4$ and $a_5$ which satisfy (7) for some positive integers $k<l$. Its clear that $k$ and $l$ must be of the same parity. Vice versa, let positive integers $k,l$ be of the same parity and satisfy $k<l$ then from (7) we get integers $a_2,a_3,a_4$ and $a_5$ then $a_1=(a_3-a_2{)}^2-a_2$ and it remains to verify that $a_1$ and $a_2$ are positive i.e. $2k^2+k>l^2$ and $2(l^2-k^2-k{)}^2>2k^2-l^2+k$.

---

Alternative solution.

It is easy to see that $(a_n)$ is increasing for large enough $n$. Hence $$a_{n+1}<a_n+\sqrt{2a_n}(1)$$ and $$a_n<a_{n-1}+\sqrt{2a_{n-1}}(2)$$ Lets define $b_n=a_n+a_{n-1}$. Using AM-QM inequality we have $$\frac{\sqrt{2a_n}+\sqrt{2a_{n-1}}}{2}\le \sqrt{\frac{2a_n+2a_{n-1}}{2}}(3)$$ Adding (1), (2) and (3): $$b_{n+1}<b_n+\sqrt{2a_n}+\sqrt{2a_{n-1}}\le b_n+2\sqrt{b_n}.$$ Let $b_n=m^2$. Since $(b_n)$ is increasing for large enough $n$ we have: $$m^2<b_{n+1}<m^2+2m<(m+1{)}^2.$$ So, $b_{n+1}$ can't be a perfect square, so we get contradiction.