Proof without words: Sum n

A “proof without words” is so convincing that one actually takes it for a proof, although it is none from the mathematician’s point of view. However, such a proof is often a very good way to quickly arrive at a mathematical proof. Why? The presented conjecture is not proved universally, but only for some cases, e.g. up to n=6. A mathematically complete proof would have to cover all possible natural numbers n, i.e. infinitely many cases. That would be done for these examples here using the proof principle of complete induction. However, the exhibits are very good for making a suitable conjecture for a general formula. This is very important, because without a conjecture you have nothing to prove either. Moreover, after careful observation, one can imagine what the next step would look like, then the one after that, and on and on, which is sufficient for a good justification of the facts. In the proof by complete induction, nothing else is done in principle. Such a proof consists of two parts: the induction start and the induction step. First one shows on a simple case (usually n=1) that the established assumption is correct for it. This first step is called the induction start. Then, starting from the assumption that the conjecture is correct for an (arbitrary) n, it is shown that the conjecture is then also true for the successor n+1. This is often illustrated by the image of a ladder on which one has already climbed to the n-th step, and from there always gets to the next, (n+1)-th step. Like the set of natural numbers, this ladder is also thought of as infinite. The exhibit on the sum of odd numbers consists of L-shaped plastic pieces of different sizes. The first piece consists of one box, the second of 3, the third of 5, etc., the n-th piece of 2n-1 boxes. So, adding the number of all these boxes, we get the sum of the first n odd numbers. The exhibit even makes it possible for the viewer not to do the math himself, but only to add them up. This is because the L-shaped parts fit together and, in the correct order (one must not leave any gaps), each makes a square. For each added part (corresponding to another summand when adding), the square grows by one box length in each direction. More precisely, if you add the part of size 2n-1, you get a collapsed square with edge length n, i.e. n^2 boxes big. This leads to the formula

    \[1+3+5+\cdots+2n-1=\sum_{i=1}^n{(2n-1)}=n^2.\]


The proof by complete induction

Now, as an example, we perform a proof by complete induction of the statement just given about the sum of the first n odd numbers:

Behauptung:

    \[1+3+5+\cdots+(2n-1)=\sum_{i=1}^n{(2i-1)}=n^2.\]

Induction start: for n=1, obviously \sum_{i=1}^n{(2i-1)}=1 and also n^2=1. So the conjecture is correct for n=1.

Now it is assumed that \sum_{i=1}^n{(2i-1)}=n^2 holds. Now it is to be shown that \sum_{i=1}^{n+1}{(2i-1)}=(n+1)^2 then also holds.

Induction step: Here first the limits of the summation are shifted in such a way that then the assumption can be used. Now we transform and apply the binomial formula so that we get the desired result:

    \[\sum_{i=1}^{n+1}{(2i-1)}=\sum_{i=1}^n{(2i-1)}+(2(n+1)-1)=n^2+2(n+1)-1=n^2+2n+1=(n+1)^2.\]


A related problem

We now turn to a similar statement, but this time not about the sum of the first n odd numbers, but of the first n numbers:

There is an anecdote about this task from the school days of Carl Friedrich Gauss (1777–1855). In the “Spektrum der Wissenschaft Spezial”, 2/2009, it is reported: “About the nine-year-old Gauss it is told that he is finished in the shortest time with an arithmetic problem which his teacher Büttner has given to the class: 1+2+3+\cdots+100=5050. His reasoning is: proceeding from the “outside” to the “inside”, he sums up the smallest and the largest number respectively: 1+100, 2+99, 3+98, …, 50+51. This results in the sum 101 50 times… Teacher Buettner senses that he can’t really teach this boy anything and gives him a textbook on arithmetic, which he works out on his own.” This is not the same approach as shown in the corresponding exhibit in MATHEMATICS ADVENTURE LAND, but this story also makes it clear that you can get faster and farther with systematic thinking than with just “calculating on the fly”. But the result is the same: Gauss also obtains (for the case n= 100):

    \[50\cdot 101=\frac{100\cdot 101}{2}=\frac{n(n+1)}{2}.\]

Again we want to demonstrate the induction proof:

Behauptung:

    \[1+2+3+\cdots+n=\sum_{i=1}^n{i}=\frac{n(n+1)}{2}.\]

Induction start: for n=1 \sum_{i=1}^n{i}=1 and also \frac{n(n+1)}{2}=2/2=1. So the conjecture is correct for n=1.

Now we assume that

    \[\sum_{i=1}^n{i}=\frac{n(n+1)}{2}\]

holds. So now we want to show that also

    \[\sum_{i=1}^{n+1}{i}=\frac{(n+1)(n+2)}{2}\]

holds.

Induction step: Here first the upper bound of the sum sign is shifted so that then the assumption can be inserted. Then we transform and factor out so that we get the desired result:

    \[\sum_{i=1}^{n+1}{i}=\sum_{i=1}^n{i}+(n+1)=\frac{n(n+1)}{2}+n+1=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+2)(n+1)}{2}.\]


One last proof

Figure 1: Exhibit for the sum of the first n square numbers

We conclude with a final induction proof on the sum of the first n square numbers:

Behauptung:

    \[1^2+2^2+3^2+\cdots+n^2=\sum_{i=1}^n{i^2}=\frac{n(n+1)(2n+1)}{6}.\]

Induction start: for n=1, obviously \sum_{i=1}^{n}{i^2}=1 and also \frac{n(n+1)(2n+1)}{2}=\frac{1\cdot 2\cdot 3}{6}=1. So our conjecture is correct for n=1.

Now we assume that

    \[\sum_{i=1}^n{i^2}=\frac{n(n+1)(2n+1)}{6}\]

holds.

Induction step: Here first the upper bounds of the summation are shifted so that then the equation of the assumption can be inserted. Then we transform, factor out and sum up again, so that we get the desired result:

    \[\sum_{i=1}^{n+1}{i^2}=\sum_{i=1}^n{i^2}+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\frac{(n+1)(n(2n+1)+6(n+1))}{6}=\frac{(n+1)(n+2)(2n+3)}{6}.\]


Literature

[1] https://de.wikipedia.org/wiki/Vollständige_Induktion.

[2] https://de.wikipedia.org/wiki/Gaußsche_Summenformel.