For every positive integer n there exists an odd integer m such that $2^{2n} + m$ is a perfect square.

Solution 1:

Compare $2^{2n}+2k+1$ with the general form of $(a+b)^2$:

$$(a+b)^2 = a^2 + 2ab + b^2$$

What could $a$ be? If you choose such an $a$, what would $k$ have to be?

Solution 2:

That is a very trivial statement and can be extended to "if $a$ is an even number there always exist and odd $m$ such that $a+m$ is a perfect square".

Proof: given an even $a$ select an odd $b$ such that $a<b^2$. $b^2$ is a perfect square and $m:=b^2-a$ is odd.

If $a$ is an even perfect square, so $a=c^2$, then $(c+1)^2$ is the smallest odd square greater than $a$.

Proof: $c+1$ is odd and there is no perfect square between $c^2$ and $(c+1)^2$.

Because the numbers $2^{2n}=((2^n)^2$ are even squares, the next odd square is $(2^n+1)^2=2^{2n}+2^n+1=2^{2n}+m$, where $m=2\cdot2^{n-1}+1$ is odd.