Mathematical Induction

Section 5.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:

🔗

$P (a)$ is true;
For all $k \in Z$ with $k \geq a,$ if $P (k)$ is true then $P (k + 1)$ is true;

then for all

n \geq a,

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) \to 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:

🔗

$P (1)$ is true, and
$P (k) \to 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

n \geq 1 .

🔗

The Principle of Mathematical Induction lets us skip all the intermediate steps,

P (1) \to P (2), P (2) \to P (3),

and conclude

P (n)

once we have (1.) and (2.).

🔗

Induction proofs follow a fairly formal structure. You are encouraged to follow the structure closely.

🔗

Structure of a Mathematical Induction Proof.

To prove

P (n), \forall n \geq 1,

🔗

Base Step.
Show $P (1)$ is true.
Induction Step.
Assume $P (k)$ for some $k \in Z,$ show $P (k + 1) .$

Conclude

P (n)

is true for all

n \geq 1

🔗

In the above structure we used

a = 1

for simplicitiy, 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 5.2.1.

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

\sum_{i = 1}^{k} i .

🔗

(b)

Write out the summation for

\sum_{i = 1}^{k + 1} i .

🔗

(c)

How do (a) and (b) differ?

🔗

Example 5.2.1. Proof by Induction: Summation Formula.

Prove

\sum_{i = 1}^{n} i = \frac{n (n + 1)}{2}

for

n \geq 1 .

Proof.

Base Step: Let

n = 1 .

Then

\begin{matrix} \sum_{i = 1}^{n} i = \sum_{i = 1}^{1} i = 1 \\ \frac{n (n + 1)}{2} = \frac{1 (1 + 1)}{2} = 1 \end{matrix}

Since the left hand side of the equation equals the right hand side,

\sum_{i = 1}^{n} i = \frac{n (n + 1)}{2}

for

n = 1 .

Induction Step:

Assume

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

for some

k \geq 1 .

Show

\sum_{i = 1}^{k + 1} i = \frac{(k + 1) (k + 2)}{2} .

Proof of induction step:

\begin{aligned} \sum_{i = 1}^{k} i & = \frac{k (k + 1)}{2} by the induction assumption \\ \sum_{i = 1}^{k + 1} i & = \sum_{i = 1}^{k} i + (k + 1) add the k + 1 term of the sum \\ = \frac{k (k + 1)}{2} + (k + 1) \\ = \frac{k (k + 1)}{2} + \frac{2 (k + 1)}{2} \\ = \frac{k (k + 1) + 2 (k + 1)}{2} factor out (k + 1) on the top \\ = \frac{(k + 1) (k + 2)}{2} . \end{aligned}

Thus,

\sum_{i = 1}^{k + 1} i = \frac{(k + 1) (k + 2)}{2} .

Hence, by induction

\sum_{i = 1}^{n} i = \frac{n (n + 1)}{2}

for

n \geq 1 .

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 5.2.1 now gives us a useful formula for finding the sum of 1 through

n :

🔗

\begin{matrix} (5.2.1) & \sum_{i = 1}^{n} i = \frac{n (n + 1)}{2} . \end{matrix}

🔗

Activity 5.2.2.

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

\sum_{i = 0}^{n} r^{i} .

🔗

(b)

Write out the summation for

\sum_{i = 0}^{n + 1} r^{i} .

🔗

(c)

How do (a) and (b) differ?

🔗

Example 5.2.2. Proof by Induction: Geometric Sum.

Prove

\sum_{i = 0}^{n} r^{i} = \frac{r^{n + 1} - 1}{r - 1}

for

n \geq 0 .

Proof.

Base Step: Let

n = 0 .

Then

\begin{matrix} \sum_{i = 0}^{0} r^{i} = r^{0} = 1 \\ \frac{r^{0 + 1} - 1}{r - 1} = \frac{r - 1}{r - 1} = 1 \end{matrix}

Since the left hand side of the equation equals the right hand side,

\sum_{i = 0}^{n} r^{i} = \frac{r^{n + 1} - 1}{r - 1}

for

n = 0 .

Induction Step:

Assume

\sum_{i = 0}^{k} r^{i} = \frac{r^{k + 1} - 1}{r - 1}

for some

k \geq 0 .

Show

\sum_{i = 0}^{k + 1} r^{i} = \frac{r^{k + 2} - 1}{r - 1} .

Proof of induction step:

\begin{aligned} \sum_{i = 0}^{k} r^{i} & = \frac{r^{k + 1} - 1}{r - 1} by the induction assumption \\ \sum_{i = 0}^{k + 1} r^{i} & = \sum_{i = 0}^{k} r^{i} + (r^{k + 1}) add the k + 1 term of the sum \\ = \frac{r^{k + 1} - 1}{r - 1} + (r^{k + 1}) \\ = \frac{r^{k + 1} - 1}{r - 1} + \frac{(r - 1) (r^{k + 1})}{r - 1} \\ = \frac{r^{k + 1} - 1 + (r - 1) (r^{k + 1})}{r - 1} factor out r^{k + 1} on the top \\ = \frac{r^{k + 1} (1 + r - 1) - 1}{r - 1} \\ = \frac{r^{k + 1} (r) - 1}{r - 1} \\ = \frac{r^{k + 2} - 1}{r - 1} . \end{aligned}

Thus,

\sum_{i = 0}^{k + 1} r^{i} = \frac{r^{k + 2} - 1}{r - 1} .

Hence, by induction

\sum_{i = 0}^{n} r^{i} = \frac{r^{n + 1} - 1}{r - 1}

for

n \geq 0 .

The sum in Example 5.2.2 is called a geometric sum. Now we have a useful formula for the sum of

r^{i}

for various values of

r > 1 :

🔗

\begin{matrix} (5.2.2) & \sum_{i = 0}^{n} r^{i} = \frac{r^{n + 1} - 1}{r - 1} . \end{matrix}

🔗

Activity 5.2.3.

Suppose you want to prove

\sum_{i = 1}^{n} i^{2} = \frac{n (n + 1) (2 n + 1)}{6}

for all

n \geq 1

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?

🔗

Example 5.2.3. Using Summation Formulas.

Use one of the sum formulas, (5.2.2) or (5.2.1), to calculate the following sums.

1 + 2 + 3 + 4 + 5 + 6 + 7 = \sum_{i = 1}^{7} i = \frac{7 (7 + 1)}{2} = 28

1 + 2 + 3 + \dots + 1000 = \sum_{i = 1}^{1000} i = \frac{1000 (1000 + 1)}{2} = 500500

1 + 2 + 4 + 8 + 16 = \sum_{i = 0}^{4} 2^{i} = \frac{2^{4 + 1} - 1}{2 - 1} = 31

1 + 3 + 9 + \dots + 3^{8} = \sum_{i = 0}^{8} 3^{i} = \frac{3^{8 + 1} - 1}{3 - 1} = 9841

The closed form of a sum is the computational formula for the sum. For example, the closed form of

\sum_{i = 0}^{n} 3^{i}

\frac{3^{n + 1} - 1}{2} .

🔗

Reading Questions Check Your Understanding

1.

Determine the values of

a, n

in the summation formula to find

3 + 4 + 5 + 6 + 7 + 8 .

🔗

\sum_{i = a}^{n} i = \sum_{i = 1}^{n} i - (1 + 2) = \frac{n (n + 1)}{2} - (3) = 33

🔗

a :

n :

🔗

2.

Determine the values of

a, n

in the summation formula to find

2 + 4 + 6 + 8 + 10 + 12 .

🔗

\sum_{i = a}^{n} 2 i = 2 \sum_{i = a}^{n} i = (2) \frac{n (n + 1)}{2} = 42

🔗

a :

n :

🔗

3.

Determine the values of

n, r

in the summation formula to find

1 + 5 + 25 + 125 + 625 .

🔗

\sum_{i = 0}^{n} r^{i} = \frac{r^{n + 1} - 1}{r - 1} = 781

🔗

n :

r :

🔗

4.

Determine the values of

n, r

in the summation formula to find

1 + 7 + 7^{2} + \dots + 7^{50} .

🔗

\sum_{i = 0}^{n} r^{i} = \frac{r^{n + 1} - 1}{r - 1} = 781

🔗

n :

r :

🔗

5.

Write out the rest of the summation formula for

1 + 7 + 7^{2} + \dots + 7^{n} .

🔗

\sum_{i = 0}^{n} 7^{i} =

🔗

6.

Suppose you want to prove

\sum_{i = 1}^{n} i^{2} = \frac{n (n + 1) (2 n + 1)}{6} .

Show the formula holds for

n = 1 .

🔗

Hint.

Use a LHS/RHS proof.

🔗

7.

Suppose you want to prove

\sum_{i = 1}^{n} i^{2} = \frac{n (n + 1) (2 n + 1)}{6} .

What should you assume in the induction step?

🔗

Hint.

Let

n = k .

🔗

8.

Suppose you want to prove

\sum_{i = 1}^{n} i^{2} = \frac{n (n + 1) (2 n + 1)}{6} .

What should you show in the induction step?

🔗

Hint.

Let

n = k + 1 .

🔗

9.

Consider

\sum_{i = 1}^{k} i^{3} .

What is the

k + 1

term in the sum?

🔗

10.

Consider

\sum_{i = 1}^{k} \frac{1}{i + 1} .

What is the

k + 1

term in the sum?

🔗

Exercises Exercises

1.

Use one of the formulas (5.2.1) or (5.2.2) to evaluate

🔗

4 + 8 + 12 + 16 + \dots + 200.

🔗

2.

Use one of the formulas (5.2.1) or (5.2.2) to write the closed form of the following sums.

🔗

$1 + 2 + 3 + \dots + (k - 1), where k \in Z and k \geq 2.$
$3 + 3^{2} + 3^{3} + \dots + 3^{n}, where n \in Z and n \geq 1.$
$1 + \frac{1}{2} + \frac{1}{2^{2}} + \dots + \frac{1}{2^{n}}, where n \in Z and n \geq 0.$

🔗

3.

For each integer

n

with

n \geq 2,

let

P (n)

be the formula

🔗

\sum_{i = 1}^{n - 1} i (i + 1) = \frac{n (n - 1) (n + 1)}{3} .

🔗

Write out the statement $P (2) .$ Is $P (2)$ true?
Write out the statement $P (k) .$
Write out the statement $P (k + 1) .$
In a proof by mathematical induction that the formula holds for all $n \geq 2,$ what must be shown in the inductive step?