Skip to main content

Subsection 8.8.6 The Sum of the First n Positive Integers

We’re now ready to try our hand at using the Principle of Mathematical Induction.

Let’s return to the claim that we derived several slides ago. It tells us what the sum of the first n positive integers is:

n1 ((∑_(i = 1 )^n▒〖i)=〗 (n (n+1))/2)

We want to prove it. Generally, before we try to prove a claim, we check for plausibility. We don’t want to waste time trying to prove something that isn’t true. But we’ve already done that in this case. So let’s go directly to the proof.

The proof is by induction on n.

(Step 1) Define P(n) (the property that we’re trying to prove holds):

P(n)  (∑_(i = 1 )^n▒〖i)=〗 (n (n+1))/2

(Step 2, Base Case) Prove P(b) for some appropriately chosen base case, b. It makes sense here to start at 1 (as we did in the statement of our claim) since we cannot sum zero numbers. So we must prove P(1). We have (substituting 1 for n):

(∑_(i = 1 )^1▒〖i)=〗 (1 (1+1))/2 = 2/2 = 1 This is correct. The sum of the first 1 integer is 1.

(Step 3, Inductive Step) Prove that P(n)  P(n + 1). Before we start, we should expand this generic statement of the claim to specify the specific P we are trying to prove something about. So, specifically we must prove:

[1] For n  1, ((∑_(i = 1 )^n▒〖i)=〗 (n (n+1))/2)  ((∑_(i = 1 )^(n+1)▒〖i)=〗 ((n+1)((n+1)+1))/2)

Note that, in the expression on the right, we’ve simply substituted (n+1) for n.

Before we begin the proof of this claim, let’s write out explicitly the induction hypothesis (the expression to the left of ). We have:

Inductive hypothesis: (∑_(i = 1 )^n▒〖i)=〗 (n (n+1))/2 This is what we will assume.

Now we must prove [1].

Observe that the sum of the first n+1 positive integers is the sum of the first n of them, plus the next one. So we have:

[2] (∑_(i = 1 )^(n+1)▒〖i)=(∑_(i = 1 )^n▒〖i)+(n+1)〗〗

At this point, generally the thing to do is to look at what we’ve written and see whether there is any way to exploit the inductive hypothesis. For example, can we use it to substitute for some piece of an equation that we’re working with? In this case the answer is yes. It tells us a value for (∑_(i = 1 )^n▒〖i)〗. Let’s substitute that value into [2], giving us:

[3] (∑_(i = 1 )^(n+1)▒〖i)=〗 (n (n+1))/2+(n+1)

[4] = (n (n+1))/2+(2 (n+1))/2

[5] = ((n+1)((n+1)+1))/2 Check this against [1], the thing we’re trying to prove.

Thus we’ve shown that n (P(n)  P(n + 1)). Since the summation formula holds for 1 and, if it holds for any integer n it must also hold for n + 1, by the Principle of Mathematical Induction, we have:

n1 ((∑_(i = 1 )^n▒〖i)=〗 (n (n+1))/2 )