Gauss's Summation Formula for 1, 2, ..., n-1, n

true

2022-12-29

An inductive proof of the sum of the first n natural numbers

Written by: Ned

This is a pretty straightforward proof of a very useful method for calculating sums. The formula itself is $\Sigma_{i=1}^n i = \frac{n(n+1)}{2}$. As an example, I’ll look at the sum of 1 to 10, so n in this case is 10. From the formula it’s expected the sum will be $\frac{10(11)}{2} = 55$. Suppose we write the numbers 1 to n, and n to 1 in columns and sum them. We have a constant sum which is $n+1$ for each pair. We have n pairs, but we also used the numbers twice instead of once so to get the correct sum we should divide the result by $2$.

$1 + 10 = 11$

$2 + 9 = 11$

$3 + 8 = 11$

$4 + 7 = 11$

$5 + 6 = 11$

$6 + 5 = 11$

$7 + 4 = 11$

$8 + 3 = 11$

$9 + 2 = 11$

$10 + 1 = 11$ -> these 10 pairs add up to $10(11) = 110$

Since we used each number twice, we divide by $110$ by $2$ to get $55$.

To prove this by induction we identify the base case, here when n = 1, and plug it into the formula. Which, since the sum of 1 is 1, should give us 1.

$\frac{1(1+1)}{2} = \frac{1(2)}{2} = 1$ as expected.

Now, we assume the formula is true for n = k, that is that $\Sigma_{i=1}^k = \frac{k(k+1)}{2}$, this is the induction hypothesis. Then we show that it also holds for $k+1$. That is we show that:

$\Sigma_{i=1}^{k+1} = \frac{(k+1)(k+2)}{2}$

Begin with the LHS:

$\Sigma_{i=1}^{k+1} = 1 + 2 + ... + (k-1) + k + (k + 1)$

$= \frac{k(k+1)}{2} + (k + 1)$ by the induction hypothesis.

Get a common denominator by multiplying the $(k + 1)$ term by the needed representation of $1$, in this case $\frac 2 2$:

$= \frac{k(k+1)}{2} + \frac{2(k + 1)}{2}$

$= \frac{k(k+1)+ 2(k+1)}{2}$

Factoring the common $(k+1)$ term gives:

$= \frac{(k+1)(k+2)}{2}$

Thus $k \implies k+1$. So by induction it is shown that the sum of the first n positive numbers, $\Sigma_{i=1}^n i = \frac{n(n+1)}{2}$.

$\square$

Techniques and Observations

This is a fairly intuitive formula once you see it laid out in columns or rows as in the example. But it makes a good first inductive proof as well since it’s fairly simple and doesn’t involve anything more complicated than expanding and factoring quadratics. Induction is a very useful proof technique, so if you aren’t already familiar with it, it’s worth running through some more examples.

You could for instance show that $\Sigma_{i=1}^n i^2 =\frac{n(n+1)(2n+1)}{6}$ using the same technique.