When is $n^2-1$ a sum of two squares? I am trying to work out when $n^2-1$ is a sum of two squares. Is there a formula for such $n$? I have found $n=1$, $n=3$ and $n=9$ so far but am struggling to find a pattern that will generalise. If there is no such pattern then how might I prove that there are infinitely many such $n$ that have this property? 
E.g. For $n=3$ we have $n^2-1=9-1=8=2^2+2^2$ and for $n=9$ we have $n^2-1=9^2-1=80=8^2+4^2$.
 A: Here is a proof that there are infinitely many such $n$.  Note that for any $m\in\mathbb{N}$, both $m^2=m^2+0^2$ and $m^2+1=m^2+1^2$ are a sum of two squares.  It follows that both $2m^2$ and $2m^2+2$ are a sum of two squares (since a product of two sums of two squares is a sum of two squares).  Letting $n=2m^2+1$, then, $n^2-1=(n-1)(n+1)=2m^2(2m^2+2)$ is a sum of two squares.  So, $n^2-1$ is a sum of two squares whenever $n$ has the form $2m^2+1$.
More explicitly, we have $$(2m^2+1)^2-1=4m^4+4m^2=(2m^2)^2+(2m)^2.$$

In some sense, all examples must come from an idea similar to this one (and indeed, that is how I came up with this one).  If $n^2-1$ is a sum of two squares, then mod $4$ considerations require that $n$ is odd.  We then have $n^2-1=4a(a+1)$ where $a=\frac{n-1}{2}$ is an integer.  By the classification of sums of two squares, $n^2-1$ is a sum of two squares iff $a$ and $a+1$ are both sums of two squares (since $a$ and $a+1$ share no prime factors, and in particular their prime factors that are $3$ mod $4$ are distinct).  So every example comes from a pair of consecutive integers that are both sums of two squares; my method above just came from the observation that $m^2$ and $m^2+1$ always gives you such a pair.
