5. Find all integers n for which the number

$$
2^{n}+n^{2}
$$

is a perfect square of some integer.

(Tomáš Jurík)
SOLUTION. We will show that the only integer solutions for $n$ are $n=0$ and $n=6$.

In the case of integer $n$, $m-n$ are powers of two, so $m-n \mid m+n$. Thus, $m-n$ also divides the number $(m+n)-(m-n)$ equal to $2n$, where, however, $n$ is an odd factor, so $4 \nmid m-n$. A power of two equal to $m-n$ is an even number, since the numbers $m, n$ are odd. Therefore, from $4 \nmid m-n$ it follows that $m-n=2$. Substituting $m=n+2$ into (1) and rearranging, we get $2^{n}=4n+4$. However, we will show by mathematical induction that for every integer $n \geq 5$, $2^{n}>4n+4$, thereby leading to a contradiction in case a). Indeed, for $n=5$, it is a valid inequality $32>24$. Assuming now that for some $n \geq 5$, $2^{n}>4n+4$, then multiplying by two we get $2^{n+1}>8n+8$, and considering the obvious inequality $8n+8>4(n+1)+4$, we obtain the desired inequality for the value $n+1$. This completes the analysis of case a).

b) The case of even $n$. Then the number $m$ from the equation $2^{n}+n^{2}=m^{2}$ is also even. Let $n=2k$, where $k$ is an integer that, due to the assumption $n \geq 7$, satisfies the inequality $k \geq 4$. We will further prove that the inequalities $\left(2^{k}\right)^{2}<2^{2k}+4k^2<\left(2^{k}+1\right)^{2}$ hold. The left inequality is trivial, the right inequality after canceling the same terms $2^{2k}$ and dividing both sides by four becomes the equivalent inequality $k^{2}<2^{k}+1$. We will prove this for every integer $k \geq 4$ by mathematical induction. For $k=4$, it is a valid inequality $16<17$. Assuming now that for some $k \geq 4$, $k^{2}<2^{k}+1$, then multiplying by two and subtracting one, we get $2k^{2}-1<2^{k+1}+1$. The desired inequality for the value $k+1$ will be proven if we show that $(k+1)^{2}<2k^{2}-1$ or $2<k(k-2)$, which is clearly true even for every $k \geq 3$. This concludes the analysis of case b).