# For which positive integers $k$ does $\frac{a^2 + b^2}{2} = n^2 + k$ have an integer solution?

The other day I was playing around with averages of perfect squares and noticed that I could find perfect squares whose averages were perfect squares, one more than a perfect square, three more than a perfect square, and four more than a perfect square. That got me wondering for which values of $$k$$ it’s possible to find perfect squares $$a^2$$ and $$b^2$$ whose average was exactly $$k$$ more than a perfect square. Stated more precisely: for which positive integers $$k$$ does the equation $$\frac{a^2 + b^2}{2} = n^2 + k$$ have a solution over the positive integers?

I wrote a quick Python script to look at the first 100 perfect squares and it found solutions for all values of $$k$$ up to 100. Heuristically, that suggests that the answer might be “every $$k$$ works.” But in looking over the solutions my program found, I didn’t see any obvious pattern jump out that would let me prove that this is indeed the case.

Is it true that the equation has positive integer solutions for all $$k$$? If so, is there a simple proof of that fact?

For reference, here’s what my program found for $$k$$ up to $$100$$:

\begin{aligned}\frac{1^2 + 1^2}{2} &= 1^2 + 0\\ \frac{1^2 + 3^2}{2} &= 2^2 + 1\\ \frac{6^2 + 16^2}{2} &= 12^2 + 2\\ \frac{2^2 + 2^2}{2} &= 1^2 + 3\\ \frac{1^2 + 3^2}{2} &= 1^2 + 4\\ \frac{1^2 + 9^2}{2} &= 6^2 + 5\\ \frac{2^2 + 4^2}{2} &= 2^2 + 6\\ \frac{4^2 + 4^2}{2} &= 3^2 + 7\\ \frac{3^2 + 3^2}{2} &= 1^2 + 8\\ \frac{1^2 + 5^2}{2} &= 2^2 + 9\\ \frac{2^2 + 12^2}{2} &= 8^2 + 10\\ \frac{2^2 + 6^2}{2} &= 3^2 + 11\\ \frac{1^2 + 5^2}{2} &= 1^2 + 12\\ \frac{1^2 + 15^2}{2} &= 10^2 + 13\\ \frac{6^2 + 8^2}{2} &= 6^2 + 14\\ \frac{4^2 + 4^2}{2} &= 1^2 + 15\\ \frac{1^2 + 7^2}{2} &= 3^2 + 16\\ \frac{3^2 + 15^2}{2} &= 10^2 + 17\\ \frac{2^2 + 8^2}{2} &= 4^2 + 18\\ \frac{2^2 + 6^2}{2} &= 1^2 + 19\\ \frac{2^2 + 18^2}{2} &= 12^2 + 20\\ \frac{1^2 + 7^2}{2} &= 2^2 + 21\\ \frac{4^2 + 6^2}{2} &= 2^2 + 22\\ \frac{8^2 + 12^2}{2} &= 9^2 + 23\\ \frac{1^2 + 7^2}{2} &= 1^2 + 24\\ \frac{1^2 + 9^2}{2} &= 4^2 + 25\\ \frac{4^2 + 18^2}{2} &= 12^2 + 26\\ \frac{2^2 + 10^2}{2} &= 5^2 + 27\\ \frac{3^2 + 7^2}{2} &= 1^2 + 28\\ \frac{3^2 + 9^2}{2} &= 4^2 + 29\\ \frac{2^2 + 8^2}{2} &= 2^2 + 30\\ \frac{4^2 + 8^2}{2} &= 3^2 + 31\\ \frac{1^2 + 9^2}{2} &= 3^2 + 32\\ \frac{2^2 + 8^2}{2} &= 1^2 + 33\\ \frac{2^2 + 24^2}{2} &= 16^2 + 34\\ \frac{6^2 + 6^2}{2} &= 1^2 + 35\\ \frac{1^2 + 11^2}{2} &= 5^2 + 36\\ \frac{1^2 + 9^2}{2} &= 2^2 + 37\\ \frac{2^2 + 12^2}{2} &= 6^2 + 38\\ \frac{4^2 + 8^2}{2} &= 1^2 + 39\\ \frac{1^2 + 9^2}{2} &= 1^2 + 40\\ \frac{1^2 + 27^2}{2} &= 18^2 + 41\\ \frac{4^2 + 10^2}{2} &= 4^2 + 42\\ \frac{2^2 + 10^2}{2} &= 3^2 + 43\\ \frac{3^2 + 9^2}{2} &= 1^2 + 44\\ \frac{1^2 + 11^2}{2} &= 4^2 + 45\\ \frac{6^2 + 8^2}{2} &= 2^2 + 46\\ \frac{12^2 + 20^2}{2} &= 15^2 + 47\\ \frac{2^2 + 10^2}{2} &= 2^2 + 48\\ \frac{1^2 + 13^2}{2} &= 6^2 + 49\\ \frac{6^2 + 24^2}{2} &= 16^2 + 50\\ \frac{2^2 + 10^2}{2} &= 1^2 + 51\\ \frac{1^2 + 11^2}{2} &= 3^2 + 52\\ \frac{3^2 + 13^2}{2} &= 6^2 + 53\\ \frac{4^2 + 10^2}{2} &= 2^2 + 54\\ \frac{4^2 + 12^2}{2} &= 5^2 + 55\\ \frac{3^2 + 11^2}{2} &= 3^2 + 56\\ \frac{1^2 + 11^2}{2} &= 2^2 + 57\\ \frac{2^2 + 12^2}{2} &= 4^2 + 58\\ \frac{6^2 + 10^2}{2} &= 3^2 + 59\\ \frac{1^2 + 11^2}{2} &= 1^2 + 60\\ \frac{1^2 + 33^2}{2} &= 22^2 + 61\\ \frac{14^2 + 24^2}{2} &= 18^2 + 62\\ \frac{8^2 + 8^2}{2} &= 1^2 + 63\\ \frac{1^2 + 15^2}{2} &= 7^2 + 64\\ \frac{2^2 + 12^2}{2} &= 3^2 + 65\\ \frac{2^2 + 16^2}{2} &= 8^2 + 66\\ \frac{6^2 + 10^2}{2} &= 1^2 + 67\\ \frac{3^2 + 15^2}{2} &= 7^2 + 68\\ \frac{1^2 + 13^2}{2} &= 4^2 + 69\\ \frac{2^2 + 12^2}{2} &= 2^2 + 70\\ \frac{4^2 + 12^2}{2} &= 3^2 + 71\\ \frac{4^2 + 16^2}{2} &= 8^2 + 72\\ \frac{2^2 + 12^2}{2} &= 1^2 + 73\\ \frac{2^2 + 36^2}{2} &= 24^2 + 74\\ \frac{2^2 + 14^2}{2} &= 5^2 + 75\\ \frac{1^2 + 13^2}{2} &= 3^2 + 76\\ \frac{1^2 + 15^2}{2} &= 6^2 + 77\\ \frac{8^2 + 10^2}{2} &= 2^2 + 78\\ \frac{4^2 + 12^2}{2} &= 1^2 + 79\\ \frac{3^2 + 13^2}{2} &= 3^2 + 80\\ \frac{1^2 + 13^2}{2} &= 2^2 + 81\\ \frac{6^2 + 16^2}{2} &= 8^2 + 82\\ \frac{2^2 + 18^2}{2} &= 9^2 + 83\\ \frac{1^2 + 13^2}{2} &= 1^2 + 84\\ \frac{1^2 + 39^2}{2} &= 26^2 + 85\\ \frac{6^2 + 12^2}{2} &= 2^2 + 86\\ \frac{4^2 + 16^2}{2} &= 7^2 + 87\\ \frac{1^2 + 15^2}{2} &= 5^2 + 88\\ \frac{3^2 + 39^2}{2} &= 26^2 + 89\\ \frac{4^2 + 14^2}{2} &= 4^2 + 90\\ \frac{2^2 + 14^2}{2} &= 3^2 + 91\\ \frac{3^2 + 15^2}{2} &= 5^2 + 92\\ \frac{5^2 + 13^2}{2} &= 2^2 + 93\\ \frac{2^2 + 16^2}{2} &= 6^2 + 94\\ \frac{8^2 + 12^2}{2} &= 3^2 + 95\\ \frac{1^2 + 17^2}{2} &= 7^2 + 96\\ \frac{1^2 + 15^2}{2} &= 4^2 + 97\\ \frac{18^2 + 32^2}{2} &= 24^2 + 98\\ \frac{2^2 + 14^2}{2} &= 1^2 + 99\\ \frac{1^2 + 19^2}{2} &= 9^2 + 100 \end{aligned}

Yes, every positive integer $$k$$ has positive integer solutions to
$$\frac{a^2+b^2}{2} = n^2 + k \;\;\to\;\; k = \frac{a^2+b^2}{2} - n^2$$
You already have solutions for $$k = 1$$ and $$k = 2$$, so consider only $$k \gt 2$$. If $$k$$ is odd, then a solution is $$a = b = \frac{k+1}{2}$$ and $$n = \frac{k-1}{2}$$, with this giving
$$\frac{\left(\frac{k+1}{2}\right)^2 + \left(\frac{k+1}{2}\right)^2}{2} - \left(\frac{k-1}{2}\right)^2 = \frac{k^2 + 2k + 1}{4} - \frac{k^2 - 2k + 1}{4} = \frac{4k}{4} = k$$
With $$k$$ being even, a solution is then $$a = \frac{k+2}{2}$$ and $$b = n = \frac{k-2}{2}$$, resulting in
$$\frac{\left(\frac{k+2}{2}\right)^2 + \left(\frac{k-2}{2}\right)^2}{2} - \left(\frac{k-2}{2}\right)^2 = \frac{2k^2 + 8}{8} - \frac{k^2 - 4k + 4}{4} = \frac{4k}{4} = k$$