Simplifying the alternating sum of n squares This question is based on a curious problem from Donald Knuth's The Art of Computer Programming, exercise 7 to chapter 1.2.1. It's stated as the following:

Formulate and prove by induction a rule for the sums $1^2$, $2^2-1^2$, $3^2-2^2+1^2$, $4^2-3^2+2^2-1^2$, $5^2-4^2+3^2-2^2+1^2$, etc.

Please note that during this simplification I assume that I know nothing neither about the sum of first $n$ natural numbers, nor about triangular numbers. (1)
Below is my attempt to build a solution.
Formulation
Let's take as an observation that these sums are following a couple of rules:

*

*The signs alternate in such way that summands with odd indices are positive, and the rest negative.

*The sum goes from $n$ to $1$.

Thus, we can express alternating signs by multiplying each summand by $(-1)^k$ where $k$ is even for summands with odd indices and odd for summands with even indices, which makes it possible to say $k=j-1$ where $j$ is the index of the current summand because the first summand is odd so we need an even power.
Sub-question: can we go $k=j+1$ here instead and if yes, then why?
Taking the largest summand as $n^2$, we can express the rest of them as $(n-1)^2$, $(n-2)^2$, and so on all the way down to $(n-(n-1))^2$, which is $1^2$, for the last summand.
Expressing the first index as $n-n$ and the last one as $n$, this gives us a formula:
$$(-1)^{n-n}n^2+(-1)^{n-(n-1)}(n-1)^2+...+(-1)^{n}(n-(n-1))^2$$
Note that it's possible to express each of the terms in brackets with indexes, which provides us way prettier formula to look at:
$$\sum\limits_{j=0}^{n-1}(-1)^j(n-j)^2$$
Simplification
As with any sum with alternating signs, it's always a good idea to group them in pairs and try to find partial sums. Here, it can be done by the difference of squares formula. Below are results for some first pairs of summands:
$$n^2-(n-1)^2=(n-n+1)(n+n-1)=2n-1\\
(n-2)^2-(n-3)^2=2n-5\\
(n-4)^2-(n-5)^2=2n-9$$
Thus, by finding the partial sums above, we've transformed the sum to the following form:
$$(2n-1)+(2n-5)+(2n-9)+...$$
If $n$ is odd, then the amount of summands is also odd, thus the last summand will not get a pair, and will remain the same. If $n$ is even, then all summands will get grouped into pairs. So, for the general case, a new sum will have $k=\left\lceil\dfrac{n}2\right\rceil$ summands.
For the even case, I can find partial sums again:
$$(2n-1)=1(2n-1)\\
(2n-1)+(2n-5)=2(2n-3)\\
(2n-1)+(2n-5)+(2n-9)=3(2n-5)$$
...and so on.
With $n=2k$, this directly leads to a formula for sum of $k$ such summands: $k(4k-(2k+1))=k(2k-1)$. Substituting $k=\dfrac{n}2$, we get the formula $\dfrac{n(n-1)}2$.
I can't derive the same formula for the 'odd summands' case, neither I can go further to get to $1+2+...+n$.
Proving by induction
A good proof can be found here. However, it supposes that the $\dfrac{n(n+1)}2$ is already known, thus I must obtain it before usage, which I haven't done fully.
The question
How do I come to the $\dfrac{n(n+1)}2$ or $1+2+...+n$, knowing neither of these sums? E.g. through equivalent transformations of the sum formula obtained in the first section of this question. If this helps, I've seen this question, but I don't have such subtraction in my case (or I'm plain ignoring it right in my sight).
 A: There was an answer inside my question which slipped from my initial attention. I've got $n^2-(n-1)^2=2n-1$, which is correct. However, there is more to it. As mathlove has said, $2n-1=n+n-1=n+(n-1)$, which is a sum of two consecutive numbers.
Thus, $(n-2)^2-(n-3)^2=(n-2)+(n-3)$, and so on.
This way, the initial sum gets transformed into:
$[n^2-(n-1)^2]+[(n-2)^2-(n-3)^2]+...+1$
No matter whether the sum has odd or even amount of summands, we will always add 1. Here is the proof of that:

*

*Suppose the amount of summands is even. Then we have a pair for each summand, and the last pair will be transformed as $2^2-1^2=2+1$, which means we have $1$ added as the last summand.

*Now suppose the amount of summands is odd. In that case, the last summand won't have a pair, but if the amount of summands is odd, then $n$ is as well odd, then $(-1)^{n-1}=1$, and we still have $1$ added as the last summand.

Thus, we conclude that the following equality is correct:
$$(-1)^{n-n}n^2+(-1)^{n-(n-1)}(n-1)^2+...+(-1)^{n}(n-(n-1))^2=1+2+...+n$$
