New Zealand Mathematical Olympiad

Solution:

Proof by induction on $k$.

For the base cases ($k \leq 3$) we can simply choose $n = 2^{3 - k}$ to get $n2^{k} - 7 = 2^{3} - 7 = 1^{2}$.

For the inductive step let $k \geq 3$ and assume there exist integers $a$ and $n$ such that
$$a^{2} = n2^{k} - 7.$$
We will now endeavour to find integers $b$ and $m$ such that $b^{2} = m2^{k + 1} - 7$.

To do this we have two cases:

- If $n$ is even then choose $b = a$ and $m = n / 2$. Thus $b^{2} = (2m)2^{k} - 7 = m2^{k + 1} - 7$, as required.

- If $n$ is odd, then note that $a$ must also be odd. Let $n = 2x + 1$ and let $a = 2y + 1$. Now consider $(a + 2^{k - 1})^{2}$.

$$(a + 2^{k - 1})^{2} = a^{2} + 2^{k}a + 2^{2k - 2}$$
$$\qquad = \left(n2^{k} - 7\right) + 2^{k}a + 2^{2k - 2}$$
$$\qquad = \{\bigl (\}(2x + 1)2^{k} - 7\{\bigr)\} + 2^{k}\left(2y + 1\right) + 2^{2k - 2}$$
$$\qquad = \left(x + y + 1 + 2^{k - 3}\right)2^{k + 1} - 7.$$
So in this case we can simply choose $b = a + 2^{k - 1}$ and $m = x + y + 1 + 2^{k - 3}$.

Note here that this inductive step only works when $k \geq 3$ (otherwise $m = x + y + 1 + 2^{k - 3}$ is not an integer).