Induction Example: The Gaussian Sum

The Gaussian sum is a practical example of the induction method

In 1789. Carl Friedrich Gauss (who would become a great mathematician and physicist), while in school, at the age of nine, his teacher wanted to keep the children busy for a while, he ordered them to add the first hundred numbers. He had barely finished assigning homework when Gauss got up and handed over his whiteboard. On the board there was a single number: 5050. It turned out that 5050 was precisely the sum of the numbers from one to one hundred. How had he found the solution so quickly?

Gauss realized something curious. The sum to be made was \sum\limits_{k=1}^{100} k, which can take a long time if done in that order, but if you add the first and last numbers, you get 101. The same happens if you add the second with the penultimate and the third with the penultimate, and so on. You can see that all these sums have the same result: 101

Since there are obviously 50 pairs whose sum is 101, the result of adding from one to one hundred is 50\times 101=5050. This way of dealing with the problem is an excellent example of an elegant solution

This solution is not only valid for numbers from one to one hundred. In general, the sum of the first n numbers (where n is an even number) is the last number plus one times the number of pairs, that is \sum\limits_{k=1}^{n} k=\frac{n\cdot(n+1)}{2}

Now we are going to prove that \sum\limits_{k=1}^{n} k=\frac{n\cdot(n+1)}{2} is true for all natural numbers using the induction method:

We take it as a P_n the left side of the equality, we check that for P_1 is true: P_1=\sum\limits_{k=1}^{1} k=1

Now compare it with the right side \frac{1\cdot(1+1)}{2}=\frac{1\cdot 2}{2}=\frac{2}{2}=1. Since 1=1, we have that the equality was true for P_1

We assume that it is true up to n: \sum\limits_{k=1}^{n} k=\frac{n\cdot(n+1)}{2}

Now we check that it is true for n+1:

\sum\limits_{k=1}^{n+1} k=\frac{(n+1)\cdot((n+1)+1)}{2}=\frac{(n+1)\cdot(n+2)}{2}=\frac{n^2+2\cdot n+n+2}{2}=\frac{n^2+3\cdot n+2}{2}
(\sum\limits_{k=1}^{n} k)+(n+1)=\frac{n^2+3\cdot n+2}{2}

We apply the induction hypothesis: (\frac{n\cdot(n+1)}{2})+(n+1)=\frac{n^2+3\cdot n+2}{2}

\frac{n\cdot(n+1)+2\cdot(n+1)}{2}=\frac{n^2+3\cdot n+2}{2}
\frac{n^2+n+2\cdot n+2}{2}=\frac{n^2+3\cdot n+2}{2}
\frac{n^2+3\cdot n+2}{2}=\frac{n^2+3\cdot n+2}{2}

It is fulfilled, then P_n it is certain for all n\geq n_0 and therefore is true for all natural numbers