Subsection 8.8.3 The Sum of the First n Positive Integers
We are trying to fill in the blank here:
∀n≥1 (\(\sum_{i\ = \ 1\ }^{n}{i =}\) )
Let’s look at a few examples:
Let n = 10. Then we can lay out the numbers and pair them as shown here:
1 2 3 4 5 6 7 8 9 10
Notice that each pair sums to 11, which is 10+1. And there are \(\frac{10}{2}\) such pairs. So, when n is 10, we have that the sum of the first n integers is:
\(\frac{10}{2}\) ⋅ (10 + 1), which we can rewrite as \(\frac{10\ (10 + 1)}{2}\text{,}\) or \(\frac{n\ (n + 1)}{2}\)
This argument seems not to depend on n, so maybe we’ve got the answer in general. But, because we divided by 2, maybe our system only works for even values of n. Let’s try it for 9:
1 2 3 4 5 6 7 8 9
Now each pair sums to 10 (i.e., n+1). There are \(\frac{n - 1}{2}\) (i.e., 4) such pairs. And then we must add 5 (i.e., \(\frac{n + 1}{2}\)). So, when n is 9, we have that the sum of the first n integers is:
\(\frac{(n - 1)(n + 1)}{2}\ \) + \(\frac{n + 1}{2}\) = \(\frac{n\ (n + 1)}{2}\)
We got the same answer as for 10.
So now we have a claim that we believe is true:
∀n≥1 (\(\sum_{i\ = \ 1\ }^{n}{i =}\ \frac{n\ (n + 1)}{2}\) )
In other words, for any particular value of n ≥ 1, the sum, as i goes from 1 to n, of i (i.e., the sum of the first n positive integers), is \(\ \frac{n\ (n + 1)}{2}\text{.}\)
It is possible to generalize the argument that we just made and thus to turn it into a proof. But it’s easy to make mistakes in arguments of this sort. More importantly, sometimes we have hunches like this that we can’t see how to prove in this way.
What we need is a good, general purpose technique for proving claims of this sort. Mathematical induction is such a technique. Let’s see how it works.