Prove $\forall n\in\mathbb{N}, \exists m\in\mathbb{N}; n=\pm1^2\pm2^2\pm\cdots\pm m^2.$

Question

And we choose the positive and negative signs in a way that the equation becomes true.

I think it can be proved with mathematical induction. So here's how I begin:

For $n=1$, $1=+1^2$ which is true. It's also true for 2 and 3, e.g. $2=-1^2-2^2-3^2+4^2$.

Let it be true for $n$ and now I need to show it holds for $n+1$. I've got some ideas, but are a bit fuzzy. Do you have any ideas to prove the statement with or without using mathematical induction?

Answer 1

Lemma A. We may represent $0,1,2,3$. $$\begin{eqnarray*}0 &=& 1^2 + 2^2 - 3^2 + 4^2 - 5^2 - 6^2 + 7^2\\ 1 &=& 1^2\\2&=&-1^2-2^2-3^2+4^2\\3&=&-1^2+2^2.\end{eqnarray*}$$

$\phantom{}$

Lemma B. If we are able to represent some $n$, we may represent $n+4$ as well.

Since for any $m$ we have $(m+1)^2-(m+2)^2-(m+3)^2+(m+4)^2=4$,
we may simply take the representation of $n$ and, assuming it ends with $\pm m^2$, and append to it $+(m+1)^2-(m+2)^2-(m+3)^2+(m+4)^2$, getting a representation of $n+4$.