Skip to main content

Section 4.2 Mathematical Induction

In this section we learn a new proof technique, mathematical induction. This technique is useful for proving statements about the positive (or nonnegative) integers. It is based on the following principle.

Principle of Mathematical Induction.

Let P(n) be a property defined for integers n, and let a be a fixed integer. Suppose the following are true:
  1. P(a) is true;
  2. For all kZ with ka, if P(k) is true then P(k+1) is true;
then for all na, P(n) is true.
The way to think about the Principle of Mathematical Induction is that if you know the statement is true for some starting value, (P(a) is true), and if you can show that knowing the statement is true for some value allows you to know it is true for the next value (P(k)P(k+1)), then you know it for all values greater than or equal to a.
So why should this work? Suppose you know two things:
  1. P(1) is true, and
  2. P(k)P(k+1).
Note, you do not know P(k) is true, just that if it is true, then P(k+1) will be true. Now since P(1) is true, by (2), P(2) must be true. Since P(2) is true, P(3) must be true, etc. In this way we can see that P(n) must be true for all n1.
The Principle of Mathematical Induction lets us skip all the intermediate steps, P(1)P(2),P(2)P(3), and conclude P(n) once we have (1) and (2).

Structure of a Mathematical Induction Proof.

To prove P(n),n1,
  • Base Step.
    Show P(1) is true.
  • Induction Step.
    Assume P(k) for some kZ, show P(k+1).
Conclude P(n) is true for all n1
In the above structure we used a=1 for simplicity, but an induction proof could have a base step starting at a different a. Most commonly, the base step starts with 0 or 1.
When writing induction proofs, make sure you use the actual statement you are proving rather than the notation P(1),P(k),P(n).

Activity 4.2.1. Adding the Next Term.

Since the induction step in mathematical induction connects a statement about k to a statement about k+1, we need to be comfortable with the relationship between sums of k terms and sums of k+1 terms.

(a)

Write out the summation for i=1ki.

(b)

Write out the summation for i=1k+1i.

Example 4.2.1. Proof by Induction: Summation Formula.

Prove i=1ni=n(n+1)2 for n1.

Proof.

Base Step: Let n=1. Then
i=1ni=i=11i=1n(n+1)2=1(1+1)2=1
Since the left hand side of the equation equals the right hand side, i=1ni=n(n+1)2 for n=1.
Induction Step:
Assume i=1ki=k(k+1)2 for some k1.
Show i=1k+1i=(k+1)(k+2)2.
Proof of induction step:
i=1ki=k(k+1)2   by the induction assumptioni=1k+1i=i=1ki+(k+1)   add the k+1 term of the sum=k(k+1)2+(k+1)=k(k+1)2+2(k+1)2=k(k+1)+2(k+1)2   factor out (k+1) on the top=(k+1)(k+2)2.
Thus, i=1k+1i=(k+1)(k+2)2.
Hence, by induction i=1ni=n(n+1)2 for n1.
Note, in the base step we looked at each side of what we wanted to show separately. We can refer to this as a “left hand side/ right hand side proof”, or in short hand, a LHS/RHS proof. If we just start with the equation we want to show, then we are assuming what we are trying to prove. To avoid this, it is best, when trying to show two things are equal in the base step, to do a LHS/ RHS proof.
Example 4.2.1 now gives us a useful formula for finding the sum of 1 through n:
(4.2.1)i=1ni=n(n+1)2.

Activity 4.2.2. Adding k+1 Terms.

Before the next example, we practice the relationship between sums of k terms and sums of k+1 terms.

(a)

Write out the summation for i=0kri.

(b)

Write out the summation for i=0k+1ri.

Example 4.2.2. Proof by Induction: Powers of 2.

Prove i=0n2i=2n+11 for n0.

Proof.

Base Step: Let n=0. Then
i=002i=20=120+11=21=1
Since the left hand side of the equation equals the right hand side, i=0n2i=2n+11 for n=0.
Induction Step:
Assume i=0k2i=2k+11 for some k0.
Show i=0k+12i=2k+21.
Proof of induction step:
i=0k2i=2k+11 by the induction assumptioni=0k+12i=i=0k2i+(2k+1) add the k+1 term of the sum=2k+11+2k+1=2k+1+2k+11=2k+1(1+1)1=2k+1(2)1=2k+21.
Thus, i=0k+12i=2k+21.
Hence, by induction i=0n2i=2n+11 for n0.
Example 4.2.2 can be generalized to the sum i=0nri.

Example 4.2.3. Proof by Induction: Geometric Sum.

Prove i=0nri=rn+11r1 for n0.

Proof.

Base Step: Let n=0. Then
i=00ri=r0=1r0+11r1=r1r1=1
Since the left hand side of the equation equals the right hand side, i=0nri=rn+11r1 for n=0.
Induction Step:
Assume i=0kri=rk+11r1 for some k0.
Show i=0k+1ri=rk+21r1.
Proof of induction step:
i=0kri=rk+11r1 by the induction assumptioni=0k+1ri=i=0kri+(rk+1) add the k+1 term of the sum=rk+11r1+(rk+1)=rk+11r1+(r1)(rk+1)r1=rk+11+(r1)(rk+1)r1 factor out rk+1 on the top=rk+1(1+r1)1r1=rk+1(r)1r1=rk+21r1.
Thus, i=0k+1ri=rk+21r1.
Hence, by induction i=0nri=rn+11r1 for n0.
The sum in Example 4.2.3 is called a geometric sum. Now we have a useful formula for the sum of ri for various values of r>1:
(4.2.2)i=0nri=rn+11r1.

Activity 4.2.3. Practice with Induction.

Suppose you want to prove i=1ni2=n(n+1)(2n+1)6 for all n1 by induction.

(a)

What would you want to prove in the base step?

(b)

What should you assume in the induction step?

(c)

What should you show in the induction step?

(d)

Now try to put this all together in the form of an induction proof. If you are unable to prove it, where do you get stuck?
The closed form of a sum is the computational formula for the sum. For example, the closed form of i=0n2i is 2n+11, as proved in Example 4.2.2.

Exercises Exercises

1.

Use mathematical induction to prove for all integers n1,
i=1n2i=n2+n.

2.

Use mathematical induction to prove for all integers n1,
i=1ni3=[n(n+1)2]2.

3.

Use mathematical induction to prove for all integers n1,
i=1ni(i!)=(n+1)!1.

5.

Find a formula for i=0n2i1. Prove your formula using induction.

6.

Observe that
113=13113+135=25113+135+157=37113+135+157+179=49
Conjecture a general formula for i=1n1(2i1)(2i+1), and prove your conjecture by mathematical induction.

7.

Evaluate the sum i=1ni(i+1)! for all n=1,2,3,4,5. Make a conjecture for a formula for the sum for a general n, and prove your conjecture by induction.