Putnam 2000, Problem A-2

Prove that there exist infinitely many integers $n$ such that $n, n+1, n+2$ are each the sum of the squares of two integers. [Example: $0 = 0^2 + 0^2$, $1 = 0^2 + 1^2$, $2 = 1^2 + 1^2$.]

Solution:
First solution: Let \(a\) be an even integer such that \(a^2 + 1\) is not prime. (For example, choose \(a \equiv 2 \pmod{5}\), so that \(a^2 + 1\) is divisible by \(5\).) Then we can write \(a^2 + 1\) as a difference of squares \(x^2 - b^2\), by factoring \(a^2 + 1\) as \(rs\) with \(r \geq s > 1\), and setting \(x = (r+s)/2\), \(b = (r-s)/2\). Finally, put \(n = x^2 - 1\), so that \(n = a^2 + b^2\), \(n + 1 = x^2\), \(n + 2 = x^2 + 1\).  

Second solution: It is well-known that the equation \(x^2 - 2y^2 = 1\) has infinitely many solutions (the so-called "Pell" equation). Thus setting \(n = 2y^2\) (so that \(n = y^2 + y^2\), \(n + 1 = x^2 + 0^2\), \(n + 2 = x^2 + 1^2\)) yields infinitely many \(n\) with the desired property.  

Third solution: As in the first solution, it suffices to exhibit \(x\) such that \(x^2 - 1\) is the sum of two squares. We will take \(x = 3^{2^n}\), and show that \(x^2 - 1\) is the sum of two squares by induction on \(n\): if \(3^{2^n} - 1 = a^2 + b^2\), then  
\[
(3^{2^{n+1}} - 1) = (3^{2^n} - 1)(3^{2^n} + 1) = (3^{2^n}a + b)^2 + (a - 3^{2^n}b)^2.
\]  

Fourth solution (by Jonathan Weinstein): Let \(n = 4k^4 + 4k^2 = (2k^2)^2 + (2k)^2\) for any integer \(k\). Then \(n + 1 = (2k^2 + 1)^2 + 0^2\) and \(n + 2 = (2k^2 + 1)^2 + 1^2\).