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$.
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.