Problem 1099

Solution:

We have $a_{1}=1+2 \cdot 1^{2}, a_{2}=3^{2}+2 \cdot 1^{2}, a_{3}=3^{2}+2 \cdot 4^{2}, a_{4}=11^{2}+2 \cdot 4^{2}$, etc. We will prove by induction on $n$ that
$$a_{2 n-1}=a_{n-1}^{2}+2\left(\frac{a_{n}-a_{n-1}}{2}\right)^{2} \quad \text { and } \quad a_{2 n}=a_{n}^{2}+2\left(\frac{a_{n}-a_{n-1}}{2}\right)^{2},$$
where $a_{0}=1$. Assume that the claim holds for $n$. Then
$$\begin{aligned} a_{2 n+1} & =4 a_{2 n}-a_{2 n-1}=4 a_{n}^{2}+8\left(\frac{a_{n}-a_{n-1}}{2}\right)^{2}-a_{n-1}^{2}-2\left(\frac{a_{n}-a_{n-1}}{2}\right)^{2} \\ & =\frac{11}{2} a_{n}^{2}-3 a_{n} a_{n-1}+\frac{1}{2} a_{n-1}^{2}=\frac{11}{2} a_{n}^{2}-3 a_{n}\left(4 a_{n}-a_{n+1}\right)+\frac{1}{2}\left(4 a_{n}-a_{n+1}\right)^{2} \\ & =\frac{3}{2} a_{n}^{2}-a_{n} a_{n+1}+\frac{1}{2} a_{n+1}^{2}=a_{n}^{2}+2\left(\frac{a_{n+1}-a_{n}}{2}\right)^{2} \\ a_{2 n+2} & =4 a_{2 n+1}-a_{2 n}=4 a_{n}^{2}+8\left(\frac{a_{n+1}-a_{n}}{2}\right)^{2}-a_{n}^{2}-2\left(\frac{a_{n}-a_{n-1}}{2}\right)^{2} \\ & =3 a_{n}^{2}+8\left(\frac{a_{n+1}-a_{n}}{2}\right)^{2}-2\left(\frac{a_{n+1}-3 a_{n}}{2}\right)^{2}=\frac{3}{2} a_{n+1}^{2}-a_{n} a_{n+1}+\frac{1}{2} a_{n}^{2} \\ & =a_{n+1}^{2}+2\left(\frac{a_{n+1}-a_{n}}{2}\right)^{2}, \end{aligned}$$
which completes the proof.

Second solution. It is known that an odd natural number $m>1$ can be represented in the form $a^{2}+2 b^{2}$ for some coprime $a, b \in \mathbb{N}$ if and only if all prime divisors of $m$ are of the form $8 k+1$ or $8 k+3, k \in \mathbb{N}_{0}$. It is easy to see that all terms of the sequence $( a_{n})$ are odd; it remains to show that if a prime number $p$ divides $a_{n}$, then $p=8 k+1$ or $p=8 k+3$ for some $k \in \mathbb{N}_{0}$.

One shows by induction on $n$ that $a_{n} a_{n+2}=a_{n+1}^{2}+2$. Indeed, this holds for $n \leq 2$, and for $n>2$, assuming it holds for $n-2$, we have
$$\begin{aligned} \frac{a_{n+1}^{2}+2}{a_{n}} & =\frac{\left(4 a_{n}-a_{n-1}\right)^{2}+2}{a_{n}}=16 a_{n}-8 a_{n-1}+\frac{a_{n-1}^{2}+2}{a_{n}} \\ & =16 a_{n}-8 a_{n-1}+a_{n-2}=4 a_{n+1}-a_{n}=a_{n+2} \end{aligned}$$
From this it follows that $-2$ is a quadratic residue modulo every prime divisor $p$ of the number $a_{n}$, so $p \equiv 1$ or $p \equiv 3(\bmod 8)$.