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