The Principle of Mathematical Induction

Section 4.1 The Principle of Mathematical Induction

Beginning Activity Beginning Activity 1: Exploring Statements of the Form $(\forall n \in N) (P (n))$
A4 US

One of the most fundamental sets in mathematics is the set of natural numbers

N .

In this section, we will learn a new proof technique, called mathematical induction, that is often used to prove statements of the form

(\forall n \in N) (P (n)) .

In Section 4.2, we will learn how to extend this method to statements of the form

(\forall n \in T) (P (n)),

where

T

is a certain type of subset of the integers

Z .

🔗

For each natural number

n,

let

P (n)

be the following open sentence:

4 divides (5^{n} - 1) .

🔗

1.

Does this open sentence become a true statement when $n = 1 ?$ That is, is 1 in the truth set of $P (n) ?$

🔗

2.

Does this open sentence become a true statement when $n = 2 ?$ That is, is 2 in the truth set of $P (n) ?$

🔗

3.

Choose at least four more natural numbers and determine whether the open sentence is true or false for each of your choices.

🔗

All of the examples that were used should provide evidence that the following proposition is true:

For each natural number n, 4 divides (5^{n} - 1) .

🔗

We should keep in mind that no matter how many examples we try, we cannot prove this proposition with a list of examples because we can never check if 4 divides

(5^{n} - 1)

for every natural number

n .

Mathematical induction will provide a method for proving this proposition.

🔗

For another example, for each natural number

n,

we now let

Q (n)

be the following open sentence:

\begin{matrix} (15) & 1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6} . \end{matrix}

🔗

The expression on the left side of the previous equation is the sum of the squares of the first

n

natural numbers. So when

n = 1,

the left side of equation (15) is

1^{2} .

When

n = 2,

the left side of equation (15) is

1^{2} + 2^{2} .

🔗

4.

Does $Q (n)$ become a true statement when

🔗

(a)

$n = 1 ?$ (Is 1 in the truth set of $Q (n) ?$ )

🔗

(b)

$n = 2 ?$ (Is 2 in the truth set of $Q (n) ?$ )

🔗

(c)

$n = 3 ?$ (Is 3 in the truth set of $Q (n) ?$ )

🔗

5.

Choose at least four more natural numbers and determine whether the open sentence is true or false for each of your choices. A table with the columns $n,$ $1^{2} + 2^{2} + \dots + n^{2},$ and $\frac{n (n + 1) (2 n + 1)}{6}$ may help you organize your work.

🔗

All of the examples we have explored, should indicate the following proposition is true:

For each natural number $n,$ $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6} .$

In this section, we will learn how to use mathematical induction to prove this statement.

🔗

Beginning Activity Beginning Activity 2: A Property of the Natural Numbers
A4 US

🔗

Intuitively, the natural numbers begin with the number 1, and then there is 2, then 3, then 4, and so on. Does this process of “starting with 1” and “adding 1 repeatedly” result in all the natural numbers? We will use the concept of an inductive set to explore this idea in this activity.

🔗

Definition.

A set $T$ that is a subset of $Z$ is an inductive set provided that for each integer $k,$ if $k \in T,$ then $k + 1 \in T .$

🔗

1.

Carefully explain what it means to say that a subset $T$ of the integers $Z$ is not an inductive set. This description should use an existential quantifier.

🔗

2.

Use the definition of an inductive set to determine which of the following sets are inductive sets and which are not. Do not worry about formal proofs, but if a set is not inductive, be sure to provide a specific counterexample that proves it is not inductive.

🔗

(a)

$A = {1, 2, 3, \dots, 20}$

🔗

(b)

The set of natural numbers, $N$

🔗

(c)

$B = {n \in N ∣ n \geq 5}$

🔗

(d)

$S = {n \in Z ∣ n \geq - 3}$

🔗

(e)

$R = {n \in Z ∣ n \leq 100}$

🔗

(f)

The set of integers, $Z$

🔗

(g)

The set of odd natural numbers.

🔗

3.

This part will explore one of the underlying mathematical ideas for a proof by induction. Assume that $T \subseteq N$ and assume that $1 \in T$ and that $T$ is an inductive set. Use the definition of an inductive set to answer each of the following:

🔗

(a)

Is $2 \in T ?$ Explain.

🔗

(b)

Is $3 \in T ?$ Explain.

🔗

(c)

Is $4 \in T ?$ Explain.

🔗

(d)

Is $100 \in T ?$ Explain.

🔗

(e)

Do you think that $T = N ?$ Explain.

🔗

Subsection Inductive Sets

🔗

The two open sentences in Beginning Activity 1 appeared to be true for all values of

n

in the set of natural numbers,

N .

That is, the examples in this beginning activity provided evidence that the following two statements are true.

For each natural number $n,$ 4 divides $(5^{n} - 1) .$
For each natural number $n,$ $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6} .$

🔗

One way of proving statements of this form uses the concept of an inductive set introduced in Beginning Activity 2. The idea is to prove that if one natural number makes the open sentence true, then the next one also makes the open sentence true. This is how we handle the phrase “and so on” when dealing with the natural numbers. In Beginning Activity 2, we saw that the number systems

N

and

Z

and other sets are inductive. What we are trying to do is somehow distinguish

N

from the other inductive sets. The way to do this was suggested in Exercise 3 of Beginning Activity 2. Although we will not prove it, the following statement should seem true.

🔗

Statement 1.

🔗

For each subset

T

N,

1 \in T

and

T

is inductive, then

T = N .

🔗

Notice that the integers,

Z,

and the set

S = {n \in Z ∣ n \geq - 3}

both contain 1 and both are inductive, but they both contain numbers other than natural numbers. For example, the following statement is false:

🔗

Statement 2.

🔗

For each subset

T

Z,

1 \in T

and

T

is inductive, then

T = Z .

🔗

The set

S = {n \in Z ∣ n \geq - 3} = {- 3, - 2, - 1, 0, 1, 2, 3, \dots}

is a counterexample that shows that this statement is false.

🔗

Progress Check 4.1. Inductive Sets.

Suppose that $T$ is an inductive subset of the integers. Which of the following statements are true, which are false, and for which ones is it not possible to tell?

🔗

(a)

$1 \in T$ and $5 \in T .$

Solution.

It is not possible to tell if $1 \in T$ and $5 \in T .$

🔗

(b)

If $1 \in T,$ then $5 \in T .$

Solution.

True.

🔗

(c)

If $5 \notin T,$ then $2 \notin T .$

Solution.

True. The contrapositive is, “If $2 \in T,$ then $5 \in T,$ ” which is true.

🔗

(d)

For each integer $k,$ if $k \in T,$ then $k + 7 \in T .$

Solution.

True.

🔗

(e)

For each integer $k,$ $k \notin T$ or $k + 1 \in T .$

Solution.

True, since “ $k \notin T$ or $k + 1 \in T$ ” is logically equivalent to “If $k \in T,$ then $k + 1 \in T .$ ”

🔗

(f)

There exists an integer $k$ such that $k \in T$ and $k + 1 \notin T .$

Solution.

False. If $k \in T,$ then $k + 1 \in T .$

🔗

(g)

For each integer $k,$ if $k + 1 \in T,$ then $k \in T .$

Solution.

It is not possible to tell if this is true. It is the converse of the conditional statement, “For each integer $k,$ if $k \in T,$ then $k + 1 \in T .$ ”

🔗

(h)

For each integer $k,$ if $k + 1 \notin T,$ then $k \notin T .$

Solution.

True. This is the contrapositive of the conditional statement, “For each integer $k,$ if $k \in T,$ then $k + 1 \in T .$ ”

🔗

Subsection The Principle of Mathematical Induction

🔗

Although we proved that Statement 2 is false, in this text, we will not prove that Statement 1 is true. One reason for this is that we really do not have a formal definition of the natural numbers. However, we should be convinced that Statement 1 is true. We resolve this by making Statement 1 an axiom for the natural numbers so that this becomes one of the defining characteristics of the natural numbers.

🔗

The Principle of Mathematical Induction.

If $T$ is a subset of $N$ such that

$1 \in T,$ and
For every $k \in N,$ if $k \in T,$ then $(k + 1) \in T,$

then $T = N .$

🔗

Subsection Using the Principle of Mathematical Induction

🔗

The primary use of the Principle of Mathematical Induction is to prove statements of the form

(\forall n \in N) (P (n)),

🔗

where

P (n)

is some open sentence. Recall that a universally quantified statement like the preceding one is true if and only if the truth set

T

of the open sentence

P (n)

is the set

N .

So our goal is to prove that

T = N,

which is the conclusion of The Principle of Mathematical Induction To verify the hypothesis of the The Principle of Mathematical Induction, we must

Prove that $1 \in T .$ That is, prove that $P (1)$ is true.
Prove that if $k \in T,$ then $(k + 1) \in T .$ That is, prove that if $P (k)$ is true, then $P (k + 1)$ is true.

🔗

The first step is called the basis step or the initial step, and the second step is called the inductive step. This means that a proof by mathematical induction will have the following form:

🔗

Procedure for a Proof by Mathematical Induction.

To prove: $(\forall n \in N) (P (n))$

Basis step:: Prove $P (1) .$
Inductive step:: Prove that for each $k \in N,$ if $P (k)$ is true, then $P (k + 1)$ is true.

We can then conclude that $P (n)$ is true for all $n \in N .$

🔗

Note that in the inductive step, we want to prove that the conditional statement “for each

k \in N,

P (k)

then

P (k + 1)

” is true. So we will start the inductive step by assuming that

P (k)

is true. This assumption is called the inductive assumption or the inductive hypothesis.

🔗

The key to constructing a proof by induction is to discover how

P (k + 1)

is related to

P (k)

for an arbitrary natural number

k .

For example, in Beginning Activity 1, one of the open sentences

P (n)

was

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

🔗

Sometimes it helps to look at some specific examples such as

P (2)

and

P (3) .

The idea is not just to do the computations, but to see how the statements are related. This can sometimes be done by writing the details instead of immediately doing computations.

\begin{aligned} P (2) & is & 1^{2} + 2^{2} & = \frac{2 \cdot 3 \cdot 5}{6} \\ P (3) & is & 1^{2} + 2^{2} + 3^{2} & = \frac{3 \cdot 4 \cdot 7}{6} . \end{aligned}

🔗

In this case, the key is the left side of each equation. The left side of

P (3)

is obtained from the left side of

P (2)

by adding one term, which is

3^{2} .

This suggests that we might be able to obtain the equation for

P (3)

by adding

3^{2}

to both sides of the equation in

P (2) .

Now for the general case, if

k \in N,

we look at

P (k + 1)

and compare it to

P (k) .

\begin{aligned} P (k) & is & 1^{2} + 2^{2} + \dots + k^{2} & = \frac{k (k + 1) (2 k + 1)}{6} \\ P (k + 1) & is & 1^{2} + 2^{2} + \dots + {(k + 1)}^{2} & = \frac{(k + 1) [(k + 1) + 1] [2 (k + 1) + 1]}{6} \end{aligned}

🔗

The key is to look at the left side of the equation for

P (k + 1)

and realize what this notation means. It means that we are adding the squares of the first

(k + 1)

natural numbers. This means that we can write

1^{2} + 2^{2} + \dots + {(k + 1)}^{2} = 1^{2} + 2^{2} + \dots + k^{2} + {(k + 1)}^{2} .

🔗

This shows us that the left side of the equation for

P (k + 1)

can be obtained from the left side of the equation for

P (k)

by adding

{(k + 1)}^{2} .

This is the motivation for proving the inductive step in the following proof.

🔗

Proposition 4.2.

For each natural number $n,$

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

🔗

Proof.

We will use a proof by mathematical induction. For each natural number $n,$ we let $P (n)$ be

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

We first prove that $P (1)$ is true. Notice that $\frac{1 (1 + 1) (2 \cdot 1 + 1)}{6} = 1 .$ This shows that

1^{2} = \frac{1 (1 + 1) (2 \cdot 1 + 1)}{6},

which proves that $P (1)$ is true.

For the inductive step, we prove that for each $k \in N,$ if $P (k)$ is true, then $P (k + 1)$ is true. So let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that

\begin{matrix} (16) & 1^{2} + 2^{2} + \dots + k^{2} = \frac{k (k + 1) (2 k + 1)}{6} . \end{matrix}

The goal now is to prove that $P (k + 1)$ is true. That is, it must be proved that

\begin{aligned} 1^{2} + 2^{2} + \dots + k^{2} + (k + 1)^{2} & = \frac{(k + 1) [(k + 1) + 1] [2 (k + 1) + 1]}{6} \\ (17) & = \frac{(k + 1) (k + 2) (2 k + 3)}{6} . \end{aligned}

To do this, we add ${(k + 1)}^{2}$ to both sides of equation (16) and algebraically rewrite the right side of the resulting equation. This gives

\begin{aligned} 1^{2} + 2^{2} + \dots + k^{2} + (k + 1)^{2} & = \frac{k (k + 1) (2 k + 1)}{6} + (k + 1)^{2} \\ = \frac{k (k + 1) (2 k + 1) + 6 (k + 1)^{2}}{6} \\ = \frac{(k + 1) [k (2 k + 1) + 6 (k + 1)]}{6} \\ = \frac{(k + 1) (2 k^{2} + 7 k + 6)}{6} \\ = \frac{(k + 1) (k + 2) (2 k + 3)}{6} . \end{aligned}

Comparing this result to equation (17), we see that if $P (k)$ is true, then $P (k + 1)$ is true. Hence, the inductive step has been established, and by the The Principle of Mathematical Induction, we have proved that for each natural number $n,$ $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6} .$

🔗

Subsection Writing Guideline

🔗

The proof of Proposition 4.2 shows a standard way to write an induction proof. When writing a proof by mathematical induction, we should follow the guideline that we always keep the reader informed. This means that at the beginning of the proof, we should state that a proof by induction will be used. We should then clearly define the open sentence

P (n)

that will be used in the proof.

🔗

Subsection Summation Notation

🔗

The result in Proposition 4.2 could be written using summation notation as follows:

For each natural number $n,$ $\sum_{j = 1}^{n} j^{2} = \frac{n (n + 1) (2 n + 1)}{6} .$

In this case, we use

j

for the index for the summation, and the notation

\sum_{j = 1}^{n} j^{2}

tells us to add all the values of

j^{2}

for

j

from 1 to

n,

inclusive. That is,

🔗

\sum_{j = 1}^{n} j^{2} = 1^{2} + 2^{2} + \dots + n^{2} .

🔗

So in the proof of Proposition 4.2, we would let

P (n)

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

and we would use the fact that for each natural number

k,

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

🔗

Progress Check 4.3. An Example of a Proof by Induction.

🔗

(a)

Calculate $1 + 2 + 3 + \dots + n$ and $\frac{n (n + 1)}{2}$ for several natural numbers $n .$ What do you observe?

🔗

(b)

Use mathematical induction to prove that $1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2} .$ To do this, let $P (n)$ be the open sentence, “ $1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2} .$ ” For the basis step, notice that the equation $1 = \frac{1 (1 + 1)}{2}$ shows that $P (1)$ is true. Now let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that

1 + 2 + 3 + \dots + k = \frac{k (k + 1)}{2},

and complete the proof.

Solution.

🔗

Proof.

Let $P (n)$ be the predicate, “ $1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2} .$ ” For the basis step, notice that the equation $1 = \frac{1 (1 + 1)}{2}$ shows that $P (1)$ is true. Now let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that

\begin{matrix} (18) & 1 + 2 + 3 + \dots + k = \frac{k (k + 1)}{2} . \end{matrix}

We now need to prove that $P (k + 1)$ is true or that

\begin{matrix} (19) & 1 + 2 + 3 + \dots + k + (k + 1) = \frac{(k + 1) (k + 2)}{2} . \end{matrix}

By adding $(k + 1)$ to both sides of equation (18) we see that

\begin{aligned} 1 + 2 + 3 + \dots + k + (k + 1) & = \frac{k (k + 1)}{2} + (k + 1) \\ = \frac{k (k + 1) + 2 (k + 1)}{2} \\ = \frac{k^{2} + 3 k + 2}{2} \\ = \frac{(k + 1) (k + 2)}{2} \end{aligned}

By comparing the last equation to equation (19) we see that we have proved that if $P (k)$ is true, then $P (k + 1)$ is true, and the inductive step has been established. Hence, by the Principle of Mathematical Induction, we have proved that for each integer $n,$ $1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2} .$

🔗

Subsection Some Comments about Mathematical Induction

The basis step is an essential part of a proof by induction. See Activity 21 for an example that shows that the basis step is needed in a proof by induction.
Activity 22 provides an example that shows the inductive step is also an essential part of a proof by mathematical induction.
It is important to remember that the inductive step in an induction proof is a proof of a conditional statement. Although we did not explicitly use the forward-backward process in the inductive step for Proposition 4.2, it was implicitly used in the discussion prior to Proposition 4.2. The key question was, “How does knowing the sum of the first $k$ squares help us find the sum of the first $(k + 1)$ squares?”
When proving the inductive step in a proof by induction, the key question is,
How does knowing $P (k)$ help us prove $P (k + 1) ?$
In Proposition 4.2, we were able to see that the way to answer this question was to add a certain expression to both sides of the equation given in $P (k) .$ Sometimes the relationship between $P (k)$ and $P (k + 1)$ is not as easy to see. For example, in Beginning Activity 1, we explored the following proposition:
For each natural number $n,$ 4 divides $(5^{n} - 1) .$
This means that the open sentence, $P (n),$ is “4 divides $(5^{n} - 1) .$ ” So in the inductive step, we assume $k \in N$ and that 4 divides $(5^{k} - 1) .$ This means that there exists an integer $m$ such that

$\begin{matrix} (20) & 5^{k} - 1 = 4 m . \end{matrix}$

In the backward process, the goal is to prove that 4 divides $(5^{k + 1} - 1) .$ This can be accomplished if we can prove that there exists an integer $s$ such that

$\begin{matrix} (21) & 5^{k + 1} - 1 = 4 s . \end{matrix}$

We now need to see if there is anything in equation (20) that can be used in equation (21). The key is to find something in the equation $5^{k} - 1 = 4 m$ that is related to something similar in the equation $5^{k + 1} - 1 = 4 s .$ In this case, we notice that

$5^{k + 1} = 5 \cdot 5^{k} .$

So if we can solve $5^{k} - 1 = 4 m$ for $5^{k},$ we could make a substitution for $5^{k} .$ This is done in the proof of the following proposition.

🔗

Proposition 4.4.

For every natural number $n,$ 4 divides $(5^{n} - 1) .$

🔗

Proof.

(Proof by Mathematical Induction) For each natural number $n,$ let $P (n)$ be “4 divides $(5^{n} - 1) .$ ” We first prove that $P (1)$ is true. Notice that when $n = 1,$ $(5^{n} - 1) = 4 .$ Since 4 divides 4, $P (1)$ is true.

For the inductive step, we prove that for all $k \in N,$ if $P (k)$ is true, then $P (k + 1)$ is true. So let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that

4 divides (5^{k} - 1) .

This means that there exists an integer $m$ such that

5^{k} - 1 = 4 m .

Thus,

\begin{matrix} (22) & 5^{k} = 4 m + 1 . \end{matrix}

In order to prove that $P (k + 1)$ is true, we must show that 4 divides $(5^{k + 1} - 1) .$ Since $5^{k + 1} = 5 \cdot 5^{k},$ we can write

\begin{matrix} (23) & 5^{k + 1} - 1 = 5 \cdot 5^{k} - 1 . \end{matrix}

We now substitute the expression for $5^{k}$ from equation (22) into equation (23). This gives

\begin{aligned} 5^{k + 1} - 1 & = 5 \cdot 5^{k} - 1 \\ = 5 (4 m + 1) - 1 \\ = (20 m + 5) - 1 \\ = 20 m + 4 \\ (24) & = 4 (5 m + 1) \end{aligned}

Since $(5 m + 1)$ is an integer, equation (24) shows that 4 divides $(5^{k + 1} - 1) .$ Therefore, if $P (k)$ is true, then $P (k + 1)$ is true and the inductive step has been established. Thus, by the Principle of Mathematical Induction, for every natural number $n,$ 4 divides $(5^{n} - 1) .$

🔗

Proposition 4.4 was stated in terms of “divides.” We can use congruence to state a proposition that is equivalent to Proposition 4.4. The idea is that the sentence, 4 divides

(5^{n} - 1)

means that

5^{n} \equiv 1 (\mod 4) .

So the following proposition is equivalent to Proposition 4.4.

🔗

Proposition 4.5.

For every natural number $n,$ $5^{n} \equiv 1 (\mod 4) .$

🔗

Since we have proved Proposition 4.4, we have in effect proved Proposition 4.5. However, we could have proved Proposition 4.5 first by using the results in Theorem 3.34. This will be done in the next progress check.

🔗

Progress Check 4.6. Proof of Proposition 4.5.

To prove Proposition 4.5, we let $P (n)$ be $5^{n} \equiv 1 (\mod 4)$ and notice that $P (1)$ is true since $5 \equiv 1 (\mod 4) .$ For the inductive step, let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that $5^{k} \equiv 1 (\mod 4) .$

🔗

(a)

What must be proved in order to prove that $P (k + 1)$ is true?

Solution.

To prove that $P (k + 1)$ is true, we must prove $5^{k + 1} \equiv 1 (\mod 4) .$

🔗

(b)

Since $5^{k + 1} = 5 \cdot 5^{k},$ multiply both sides of the congruence $5^{k} \equiv 1 (\mod 4)$ by 5. The results in Theorem 3.34 justify this step.

Solution.

Since $5^{k + 1} = 5 \cdot 5^{k},$ we multiply both sides of the congruence $5^{k} \equiv 1 (\mod 4)$ by 5 and obtain

5 \cdot 5^{k + 1} \equiv 5 \cdot 1 (\mod 4) or 5^{k + 1} \equiv 5 (\mod 4) .

🔗

(c)

Now complete the proof that for each $k \in N,$ if $P (k)$ is true, then $P (k + 1)$ is true and complete the induction proof of Proposition 4.5.

Solution.

Since $5^{k + 1} \equiv 5 (\mod 4)$ and we know that $5 \equiv 1 (\mod 4),$ we can use the transitive property of congruence to obtain $5^{k + 1} \equiv 1 (\mod 4) .$ This proves that if $P (k)$ is true, then $P (k + 1)$ is true, and hence, by the Principle of Mathematical Induction, we have proved that for each natural number $n,$ $5^{n} \equiv 1 (\mod 4) .$

It might be nice to compare the proofs of Proposition 4.4 and Proposition 4.5 and decide which one is easier to understand.

🔗

Exercises Exercises

🔗

1.

Which of the following sets are inductive sets? Explain.

🔗

(a)

$Z$

Answer.

This set is inductive.

🔗

(b)

${x \in N ∣ x \geq 4}$

Answer.

This set is inductive.

🔗

(c)

${x \in Z ∣ x \leq 10}$

Answer.

This set is not inductive.

🔗

(d)

${1, 2, 3, \dots, 500}$

Answer.

This set is not inductive.

🔗

2.

Explain the following.

🔗

(a)

Can a finite, nonempty set be inductive?

Answer.

A finite nonempty set is not inductive (why?).

🔗

(b)

Is the empty set inductive?

Answer.

The empty set is inductive (why?).

🔗

3.

Use mathematical induction to prove each of the following:

🔗

(a)

For each natural number $n,$ $2 + 5 + 8 + \dots + (3 n - 1) = \frac{n (3 n + 1)}{2} .$

Answer.

For each $n \in N,$ let $P (n)$ be, $2 + 5 + 8 + \dots + (3 n - 1) = \frac{n (3 n + 1)}{2} .$ When we use $n = 1,$ the summation on the left side of the equation is 2, and the right side is $\frac{1 (3 \cdot 1 + 1)}{2} = 2 .$ Therefore, $P (1)$ is true. For the inductive step, let $k \in N$ and assume that $P (k)$ is true. Then,

2 + 5 + 8 + \dots + (3 k - 1) = \frac{k (3 k + 1)}{2} .

We now add $3 (k + 1) - 1$ to both sides of this equation. This gives

\begin{aligned} 2 + 5 + 8 + \dots + (3 k - 1) \\ + 3 (k + 1) - 1 & = \frac{k (3 k + 1)}{2} + (3 (k + 1) - 1) \\ = \frac{k (3 k + 1)}{2} + (3 k + 2) \end{aligned}

If we now combine the terms on the right side of the equation into a single fraction, we obtain

\begin{aligned} 2 + 5 + \dots + (3 k - 1) + 3 (k + 1) - 1 & = \frac{k (3 k + 1) + 6 k + 4}{2} \\ = \frac{3 k^{2} + 7 k + 4}{2} \\ = \frac{(k + 1) (3 k + 4)}{2} \\ = \frac{(k + 1) (3 (k + 1) + 1)}{2} \end{aligned}

This proves that if $P (k)$ is true, then $P (k + 1)$ is true.

🔗

(b)

For each natural number $n,$ $1 + 5 + 9 + \dots + (4 n - 3) = n (2 n - 1) .$

🔗

(c)

For each natural number $n,$ $1^{3} + 2^{3} + 3^{3} + \dots + n^{3} = {[\frac{n (n + 1)}{2}]}^{2} .$

🔗

4.

Based on the results in Progress Check 4.3 and Task 3.c from Exercise 3, if $n \in N,$ is there any conclusion that can be made about the relationship between the sum $(1^{3} + 2^{3} + 3^{3} + \dots + n^{3})$ and the sum $(1 + 2 + 3 + \dots + n) ?$

🔗

5.

Instead of using induction, we can sometimes use previously proven results about a summation to obtain results about a different summation.

🔗

(a)

Use the result in Progress Check 4.3 to prove the following proposition: For each natural number $n,$ $3 + 6 + 9 + \dots + 3 n = \frac{3 n (n + 1)}{2} .$

🔗

(b)

Subtract $n$ from each side of the equation in Task 5.a On the left side of this equation, explain why this can be done by subtracting $1$ from each term in the summation.

🔗

(c)

Algebraically simplify the right side of the equation in Task 5.b to obtain a formula for the sum $2 + 5 + 8 + \dots + (3 n - 1) .$ Compare this to Task 3.a.

🔗

6.

Complete the following.

🔗

(a)

Calculate $1 + 3 + 5 + \dots + (2 n - 1)$ for several natural numbers $n .$

🔗

(b)

Based on your work in Task 6.a, if $n \in N,$ make a conjecture about the value of the sum $1 + 3 + 5 + \dots + (2 n - 1) = \sum_{j = 1}^{n} (2 j - 1) .$

Answer.

The conjecture is that for each $n \in N,$ $1 + 3 + 5 + \dots + (2 n - 1) = n^{2} .$

🔗

(c)

Use mathematical induction to prove your conjecture in Task 6.b.

Answer.

The key to the inductive step is that

\begin{aligned} 1 + 3 + 5 + \dots + (2 k - 1) \\ + (2 (k + 1) - 1) & = [1 + 3 + 5 + \dots + (2 k - 1)] + (2 (k + 1) - 1) \\ = k^{2} + (2 k + 1) \\ = (k + 1)^{2} \end{aligned}

🔗

7.

In Section 3.1, we defined congruence modulo $n$ for a natural number $n,$ and in Section 3.5, we used the Division Algorithm to prove that each integer is congruent, modulo $n,$ to precisely one of the integers $0, 1, 2, \dots, n - 1$ (Corollary 3.38).

🔗

(a)

Find the value of $r$ so that $4 \equiv r (\mod 3)$ and $r \in {0, 1, 2} .$

🔗

(b)

Find the value of $r$ so that $4^{2} \equiv r (\mod 3)$ and $r \in {0, 1, 2} .$

🔗

(c)

Find the value of $r$ so that $4^{3} \equiv r (\mod 3)$ and $r \in {0, 1, 2} .$

🔗

(d)

For two other values of $n,$ find the value of $r$ so that $4^{n} \equiv r (\mod 3)$ and $r \in {0, 1, 2} .$

🔗

(e)

If $n \in N,$ make a conjecture concerning the value of $r$ where $4^{n} \equiv r (\mod 3)$ and $r \in {0, 1, 2} .$ This conjecture should be written as a self-contained proposition including an appropriate quantifier.

Answer.

For each natural number $n,$ $4^{n} \equiv 1 (\mod 3) .$

🔗

(f)

Use mathematical induction to prove your conjecture.

Answer.

For each natural number $n,$ let $P (n)$ be, “ $4^{n} \equiv 1 (\mod 3) .$ ” Since $4^{1} \equiv 1 (\mod 3),$ we see that $P (1)$ is true. Now let $k \in N$ and assume that $P (k)$ is true. That is, assume that

4^{k} \equiv 1 (\mod 3) .

Multiplying both sides of this congruence by 4 gives

4^{k + 1} \equiv 4 (\mod 3) .

However, $4 \equiv 1 (\mod 3)$ and so by using the transitive property of congruence, we see that $4^{k + 1} \equiv 1 (\mod 3) .$ This proves that if $P (k)$ is true, then $P (k + 1)$ is true.

🔗

8.

Use mathematical induction to prove each of the following:

🔗

(a)

For each natural number $n,$ 3 divides $(4^{n} - 1) .$

Answer.

The key to the inductive step is that if $4^{k} = 1 + 3 m,$ then $4^{k} \cdot 4 = 4 (1 + 3 m),$ which implies that

4^{k + 1} - 1 = 3 (1 + 4 m) .

🔗

(b)

For each natural number $n,$ 6 divides $(n^{3} - n) .$

🔗

9.

In Exercise 7, we proved that for each natural number $n,$ $4^{n} \equiv 1 (\mod 3) .$ Explain how this result is related to the proposition in Task 8.a from Exercise 8.

🔗

10.

Use mathematical induction to prove that for each natural number $n,$ 3 divides $n^{3} + 23 n .$ Compare this proof to the proof from Exercise 19 in Section 3.5.

🔗

11.

Complete the following.

🔗

(a)

Calculate the value of $5^{n} - 2^{n}$ for $n = 1,$ $n = 2,$ $n = 3,$ $n = 4,$ $n = 5,$ and $n = 6 .$

🔗

(b)

Based on your work in Task 11.a, make a conjecture about the values of $5^{n} - 2^{n}$ for each natural number $n .$

🔗

(c)

Use mathematical induction to prove your conjecture in Task 11.b.

🔗

12.

Let $x$ and $y$ be distinct integers. Prove that for each natural number $n,$ $(x - y)$ divides $(x^{n} - y^{n}) .$ Explain why your conjecture in Exercise 11 is a special case of this result.

🔗

13.

Prove Item 3 of Theorem 3.34 from Section 3.4. Let $n \in N$ and let $a$ and $b$ be integers. For each $m \in N,$ if $a \equiv b (\mod n),$ then $a^{m} \equiv b^{m} (\mod n) .$

Answer.

Let $k$ be a natural number. If $a^{k} \equiv b^{k} (\mod n),$ then since we are also assuming that $a \equiv b (\mod n),$ we can use Part (2) of Theorem 3.34 to conclude that $a \cdot a^{k} \equiv b \cdot b^{k} (\mod n) .$

🔗

14.

Use mathematical induction to prove that the sum of the cubes of any three consecutive natural numbers is a multiple of 9.

Answer.

Three consecutive natural numbers may be represent by $n,$ $n + 1,$ and $n + 2,$ where $n$ is a natural number. For the inductive step, think before you try to do a lot of algebra. You should be able to complete a proof of the inductive step by expanding the cube of only one expression.

🔗

15.

Let $a$ be a real number. We will explore the derivatives of the function $f (x) = e^{a x} .$ By using the chain rule, we see

\frac{d}{d x} (e^{a x}) = a e^{a x} .

Recall that the second derivative of a function is the derivative of the derivative function. Similarly, the third derivative is the derivative of the second derivative.

🔗

(a)

What is $\frac{d^{2}}{d x^{2}} (e^{a x}),$ the second derivative of $e^{a x} ?$

🔗

(b)

What is $\frac{d^{3}}{d x^{3}} (e^{a x}),$ the third derivative of $e^{a x} ?$

🔗

(c)

Let $n$ be a natural number. Make a conjecture about the $n^{th}$ derivative of the function $f (x) = e^{a x} .$ That is, what is $\frac{d^{n}}{d x^{n}} (e^{a x}) ?$ This conjecture should be written as a self-contained proposition including an appropriate quantifier.

🔗

(d)

Use mathematical induction to prove your conjecture.

🔗

16.

In calculus, it can be shown that

\begin{aligned} \int_{}^{} \sin^{2} x d x & = \frac{x}{2} - \frac{1}{2} \sin x \cos x + c and \\ \int_{} \cos^{2} x d x & = \frac{x}{2} + \frac{1}{2} \sin x \cos x + c . \end{aligned}

Using integration by parts, it is also possible to prove that for each natural number $n,$

\begin{aligned} \int_{} \sin^{n} x d x & = - \frac{1}{n} \sin^{n - 1} x \cos x + \frac{n - 1}{n} \int \sin^{n - 2} x d x and \\ \int_{} \cos^{n} x d x & = \frac{1}{n} \cos^{n - 1} x \sin x + \frac{n - 1}{n} \int \cos^{n - 2} x d x . \end{aligned}

🔗

(a)

Determine the values of

\int_{0}^{π / 2} \sin^{2} x d x and \int_{0}^{π / 2} \sin^{4} x d x .

🔗

(b)

Use mathematical induction to prove that for each natural number $n,$

\begin{aligned} \int_{0}^{π / 2} \sin^{2 n} x d x & = \frac{1 \cdot 3 \cdot 5 \dots (2 n - 1)}{2 \cdot 4 \cdot 6 \dots (2 n)} \frac{π}{2} and \\ \int_{0}^{π / 2} \sin^{2 n + 1} x d x & = \frac{2 \cdot 4 \cdot 6 \dots (2 n)}{1 \cdot 3 \cdot 5 \dots (2 n + 1)} . \end{aligned}

These are known as the Wallis sine formulas.

🔗

(c)

Use mathematical induction to prove that

\begin{aligned} \int_{0}^{π / 2} \cos^{2 n} x d x & = \frac{1 \cdot 3 \cdot 5 \dots (2 n - 1)}{2 \cdot 4 \cdot 6 \dots (2 n)} \frac{π}{2} and \\ \int_{0}^{π / 2} \cos^{2 n + 1} x d x & = \frac{2 \cdot 4 \cdot 6 \dots (2 n)}{1 \cdot 3 \cdot 5 \dots (2 n + 1)} . \end{aligned}

These are known as the Wallis cosine formulas.

🔗

17.

Complete the following.

🔗

(a)

Why is it not possible to use mathematical induction to prove a proposition of the form

(\forall x \in Q) (P (x)),

where $P (x)$ is some predicate?

🔗

(b)

Why is it not possible to use mathematical induction to prove a proposition of the form

For each real number $x$ with $x \geq 1,$ $P (x),$ where $P (x)$ is some predicate?

🔗

18. Evaluation of Proofs.

See the instructions for Exercise 19 on from Section 3.1.

🔗

(a)

Proposition

For each natural number $n,$ $1 + 4 + 7 + \dots + (3 n - 2) = \frac{n (3 n - 1)}{2} .$

Proof

We will prove this proposition using mathematical induction. So we let $P (n)$ be the open sentence

1 + 4 + 7 + \dots + (3 n - 2) .

Using $n = 1,$ we see that $3 n - 2 = 1$ and hence, $P (1)$ is true.

We now assume that $P (k)$ is true. That is,

1 + 4 + 7 + \dots + (3 k - 2) = \frac{k (3 k - 1)}{2} .

We then see that

\begin{aligned} 1 + 4 + 7 + \dots + (3 k - 2) + (3 (k + 1) - 2) & = \frac{(k + 1) (3 k + 2)}{2} \\ \frac{k (3 k - 1)}{2} + (3 k + 1) & = \frac{(k + 1) (3 k + 2)}{2} \\ \frac{(3 k^{2} - k) + (6 k + 2)}{2} & = \frac{3 k^{2} + 5 k + 2}{2} \\ \frac{3 k^{2} + 5 k + 2}{2} & = \frac{3 k^{2} + 5 k + 2}{2} . \end{aligned}

We have thus proved that $P (k + 1)$ is true, and hence, we have proved the proposition.

🔗

(b)

Proposition

For each natural number $n,$ $1 + 4 + 7 + \dots + (3 n - 2) = \frac{n (3 n - 1)}{2} .$

Proof

We will prove this proposition using mathematical induction. So we let

P (n) = 1 + 4 + 7 + \dots + (3 n - 2) .

Using $n = 1,$ we see that $P (1) = 1$ and hence, $P (1)$ is true.

We now assume that $P (k)$ is true. That is,

1 + 4 + 7 + \dots + (3 k - 2) = \frac{k (3 k - 1)}{2} .

We then see that

\begin{aligned} P (k + 1) & = 1 + 4 + 7 + \dots + (3 k - 2) + (3 (k + 1) - 2) \\ = \frac{k (3 k - 1)}{2} + 3 (k + 1) - 2 \\ = \frac{3 k^{2} - k + 6 k + 6 - 4}{2} \\ = \frac{3 k^{2} + 5 k + 2}{2} \\ = \frac{(k + 1) (3 k + 2)}{2} . \end{aligned}

We have thus proved that $P (k + 1)$ is true, and hence, we have proved the proposition.

🔗

(c)

Proposition

All dogs are the same breed.

Proof

We will prove this proposition using mathematical induction. For each natural number $n,$ we let $P (n)$ be

Any set of $n$ dogs consists entirely of dogs of the same breed.

We will prove that for each natural number $n,$ $P (n)$ is true, which will prove that all dogs are the same breed. A set with only one dog consists entirely of dogs of the same breed and, hence, $P (1)$ is true.

So we let $k$ be a natural number and assume that $P (k)$ is true, that is, that every set of $k$ dogs consists of dogs of the same breed. Now consider a set $D$ of $k + 1$ dogs, where

D = {d_{1}, d_{2}, \dots, d_{k}, d_{k + 1}} .

If we remove the dog $d_{1}$ from the set $D,$ we then have a set $D_{1}$ of $k$ dogs, and using the assumption that $P (k)$ is true, these dogs must all be of the same breed. Similarly, if we remove $d_{k + 1}$ from the set $D,$ we again have a set $D_{2}$ of $k$ dogs, and these dogs must all be of the same breed. Since $D = D_{1} \cup D_{2},$ we have proved that all of the dogs in $D$ must be of the same breed.

This proves that if $P (k)$ is true, then $P (k + 1)$ is true and, hence, by mathematical induction, we have proved that for each natural number $n,$ any set of $n$ dogs consists entirely of dogs of the same breed.

🔗

Activity 21. The Importance of the Basis Step.

Most of the work done in constructing a proof by induction is usually in proving the inductive step. This was certainly the case in Proposition 4.2. However, the basis step is an essential part of the proof. Without it, the proof is incomplete. To see this, let $P (n)$ be

1 + 2 + \dots + n = \frac{n^{2} + n + 1}{2} .

🔗

(a)

Let $k \in N .$ Complete the following proof that if $P (k)$ is true, then $P (k + 1)$ is true. Let $k \in N .$ Assume that $P (k)$ is true. That is, assume that

\begin{matrix} (25) & 1 + 2 + \dots + k = \frac{k^{2} + k + 1}{2} . \end{matrix}

The goal is to prove that $P (k + 1)$ is true. That is, we need to prove that

\begin{matrix} (26) & 1 + 2 + \dots + k + (k + 1) = \frac{{(k + 1)}^{2} + (k + 1) + 1}{2} . \end{matrix}

To do this, we add $(k + 1)$ to both sides of equation (25). This gives

\begin{aligned} 1 + 2 + \dots + k + (k + 1) & = \frac{k^{2} + k + 1}{2} + (k + 1) \\ = \dots . \end{aligned}

🔗

(b)

Is $P (1)$ true? Is $P (2)$ true? What about $P (3)$ and $P (4) ?$ Explain how this shows that the basis step is an essential part of a proof by induction.

🔗

Activity 22. Regions of a Circle.

Place $n$ equally spaced points on a circle and connect each pair of points with the chord of the circle determined by that pair of points. See Figure 4.7.

Four circles with points on their circumference, and with lines connecting the points to divide each circle into regions. With 1 point there is 1 region, 2 points make 2 regions, 3 points make 4 regions, 4 points make 8 regions. — Figure 4.7. Regions of Circles

Count the number of distinct regions within each circle. For example, with three points on the circle, there are four distinct regions. Organize your data in a table with two columns: “Number of Points on the Circle” and “Number of Distinct Regions in the Circle.”

🔗

(a)

How many regions are there when there are four equally spaced points on the circle?

🔗

(b)

Based on the work so far, make a conjecture about how many distinct regions would you get with five equally spaced points.

🔗

(c)

Based on the work so far, make a conjecture about how many distinct regions would you get with six equally spaced points.

🔗

(d)

Figure 4.8 shows the figures associated with Task 22.b and Task 22.c Count the number of regions in each case. Are your conjectures correct or incorrect?

a circle with five points on its circumference is divided into sixteen regions. A circle with six points on its circumference is divided into thirty two regions. — Figure 4.8. Regions of Circles

🔗

(e)

Explain why this activity shows that the inductive step is an essential part of a proof by mathematical induction.

Section 4.1 The Principle of Mathematical Induction

Beginning Activity Beginning Activity 1: Exploring Statements of the Form (∀n∈N)(P(n)) A4US

1.

2.

3.

4.

(a)

(b)

(c)

5.

Beginning Activity Beginning Activity 2: A Property of the Natural Numbers A4US

Definition.

1.

2.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

3.

(a)

(b)

(c)

(d)

(e)

Subsection Inductive Sets

Statement 1.

Statement 2.

Progress Check 4.1. Inductive Sets.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Subsection The Principle of Mathematical Induction

The Principle of Mathematical Induction.

Subsection Using the Principle of Mathematical Induction

Procedure for a Proof by Mathematical Induction.

Proposition 4.2.

Proof.

Subsection Writing Guideline

Subsection Summation Notation

Progress Check 4.3. An Example of a Proof by Induction.

(a)

(b)

Proof.

Subsection Some Comments about Mathematical Induction

Proposition 4.4.

Proof.

Proposition 4.5.

Progress Check 4.6. Proof of Proposition 4.5.

(a)

(b)

(c)

Exercises Exercises

1.

(a)

(b)

(c)

(d)

2.

(a)

(b)

3.

(a)

(b)

(c)

4.

5.

(a)

(b)

(c)

6.

(a)

(b)

Beginning Activity Beginning Activity 1: Exploring Statements of the Form $(\forall n \in N) (P (n))$
A4 US

Beginning Activity Beginning Activity 2: A Property of the Natural Numbers
A4 US