Proof by Induction

Section 4.5 Proof by Induction

Objectives

After completing this section, you should be able to do the following.

🔗

Identify the parts of a proof by mathematical induction and how they relate to the statement being proved.
Prove statements using mathematical induction.
Explain why a proof by mathematical induction is valid.

🔗

Subsection Section Preview

Investigate!

What is the unit digit (the right-most digit) of

6^{n} ?

Does the answer depend on

n ?

🔗

Mathematical induction is a powerful proof technique that can be used to prove statements are true for a sequence of statements, as long as that sequence of statements has some starting place. For example, if we are trying to say something about the unit digit of

6^{n},

we are making that claim for

n = 1,

then

n = 2,

then

n = 3,

and so on.

🔗

Induction is closely related to recursive definitions; the main idea in a proof by induction is to explain how you can get from one statement in the sequence to the next.

🔗

Worksheet Preview Activity
A4 US

1.

Suppose that

6^{472}

had a 2 for its unit digit. That is, suppose

6^{472} = 19, 381, 6 \dots \dots 2 .

What would the unit digit of

6^{473}

be?

🔗

Hint.

6^{473} = 6 \cdot 6^{472} .

🔗

2.

What is the unit digit of

6^{2},

6^{3},

and of

6^{4} ?

🔗

The unit’s digit of

6^{2}

is .

🔗

The unit’s digit of

6^{3}

is .

🔗

The unit’s digit of

6^{4}

is .

🔗

3.

Which of the following are true? Select all that apply.

🔗

If the unit’s digit of $6^{k}$ is a 6, then the unit’s digit of $6^{k + 1}$ is a 6.
If the unit’s digit of $6^{k}$ is a 2, then the unit’s digit of $6^{k + 1}$ is a 2.
The unit’s digit of $6^{472}$ is a 2.
The unit’s digit of $6^{472}$ is a 6.

🔗

4.

Explain your answer to the previous question.

🔗

Subsection Recursive Reasoning

We have seen that describing a sequence recursively can often be easier than describing the sequence with a closed formula. We will now see how using similar recursive reasoning can help us prove statements using a proof technique called mathematical induction. This style of proof is especially useful when the different instances of the statement (for different values of

n,

say) are related recursively.

🔗

For example, suppose we wanted to prove a fact about all the terms in a sequence for which we have a recursive definition. Consider the sequence

(a_{n})_{n \geq 0}

defined recursively by

a_{n} = 3 a_{n - 1} - 2

with

a_{0} = 5 .

Could we prove that every term in this sequence is odd?

🔗

Let’s start by writing out the first few terms of the sequence:

🔗

5, 13, 37, 109, \dots .

So far, all these numbers look odd. Will the next number be odd? Of course, we could just compute it using the recurrence relation. We would take

3 \cdot 109 - 2 .

We don’t actually care which odd number this is, just that it is, in fact, odd. We know it will be odd because the product of two odd numbers is odd, and subtracting 2 from an odd number results in an odd number.

🔗

Great, so

a_{4}

is odd. Will

a_{5}

be odd too? Yes, use the same argument as above:

a_{5} = 3 a_{4} - 2 .

We just convinced ourselves that

a_{4}

is odd (without finding its actual value), so

3 a_{4}

is odd, and 2 less than it will be odd too.

🔗

What about

a_{6} ?

Do the same thing. In fact, why are we using any particular number as the index? If it is the same argument each time, we should be able to just give this argument once and say it always works.

🔗

Suppose we have found that

a_{k}

is odd (where

k

is some arbitrary natural number). From this, we can find that

a_{k + 1}

is odd, since

a_{k + 1} = 3 a_{k} - 2,

and

3

times the odd number

a_{k}

will be odd, and subtracting 2 will result in an odd number. Yay. Let’s put this all together as a proof.

🔗

Proof.

We claim that for any

n \geq 0,

the number

a_{n}

is odd, where

a_{n} = 3 a_{n - 1} - 2

and

a_{0} = 5 .

🔗

When

n = 0,

the claim is true, since

a_{0} = 5

is an odd number.

🔗

Further, we can prove that every larger

n

has

a_{n}

odd because as long as

a_{k}

is odd, so is

a_{k + 1}

(since

a_{k + 1} = 3 a_{k} - 2,

and 3 times an odd number minus 2 is always odd).

🔗

Therefore

a_{n}

is odd for all

n \geq 0 .

🔗

Soon we will give a more rigid structure for proofs by induction, but the basic idea is exactly what we have above.

🔗

Subsection Formalizing Proofs

Induction can prove many statements that hold for all natural numbers, not just statements about sequences. In particular, induction should be used when there is some way to go from one case to the next – when you can see how to always “do one more.”

🔗

Thinking about how we write statements in logical symbols, we will use induction to prove statements of the form

🔗

\forall n P (n),

where the domain of discourse (the values of

n

we quantify over) has some least element. Say that domain of discourse is the natural numbers. We are then proving this sequence of statements:

🔗

P (0), P (1), P (2), P (3), \dots .

The way we do this with induction is to prove a base case, that

P (0)

is true (or

P (a)

where

a

is the least element of our domain of discourse). Next, we prove the inductive case, that

P (k) \to P (k + 1)

for all

k \geq 0

(or

k \geq a

🔗

Together, these are enough to prove

P (n)

is true for all

n .

How do we know? That is, why is this style of proof valid? Well, let’s convince ourselves that

P (3)

is true. We know

P (0)

is true. And because we know that

P (0) \to P (1),

we then also know that

P (1)

is true. Because

P (1) \to P (2),

we then get that

P (2)

is true. Finally, because

P (2) \to P (3),

we have that

P (3) .

There is nothing special about 3 here. We could have gone up as far as we like, to any $n$ value!

🔗

Think of a row of dominoes set up standing on their edges. We want to argue that in a minute, all the dominoes will have fallen. For this to happen, you will need to push the first domino. That is the base case. It will also have to be that the dominoes are close enough together that when any particular domino falls, it will cause the next domino to fall. That is the inductive case. If both of these conditions are met – you push the first domino over, and each domino will cause the next to fall – then all the dominoes will fall.

🔗

Induction is powerful! Think how much easier it is to knock over dominoes when you don’t have to push over each domino yourself. You just start the chain reaction and then rely on the relative nearness of the dominoes to take care of the rest.

🔗

When writing a proof by induction, we will follow a standard style. Writing in this style allows us to keep our ideas organized and might even help us formulate the proof.

🔗

Here is the general structure of a proof by mathematical induction:

🔗

Induction Proof Structure.

Start by saying what the statement is that you want to prove: “Let

P (n)

be the statement….” To prove that

P (n)

is true for all

n \geq 0,

you must prove two facts:

🔗

Base case: Prove that $P (0)$ is true. You do this directly. This is often easy.
Inductive case: Prove that $P (k) \to P (k + 1)$ for all $k \geq 0 .$ That is, prove that for any $k \geq 0$ if $P (k)$ is true, then $P (k + 1)$ is true as well. This is the proof of an if … then … statement, so you can assume $P (k)$ is true ( $P (k)$ is called the inductive hypothesis). You must then explain why $P (k + 1)$ is also true, given that assumption.

🔗

Assuming you are successful on both parts above, you can conclude, “Therefore by the principle of mathematical induction, the statement

P (n)

is true for all

n \geq 0 .

”

🔗

Sometimes the statement

P (n)

will only be true for values of

n \geq 4,

for example, or some other value. In such cases, replace all the 0’s above with 4’s (or the other value).

🔗

Before attempting to prove a statement by mathematical induction, first think about why the statement is true using inductive reasoning. Explain why induction is the right thing to do, and roughly why the inductive case will work. Then, sit down and write out a careful, formal proof using the structure above.

🔗

Subsection Examples

Here are some examples of proof by mathematical induction.

🔗

Example 4.5.1.

Prove for each natural number

n \geq 1

that

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

🔗

Solution.

First, let’s think inductively about this equation. In fact, we know this is true for other reasons (reverse and add comes to mind). But why might induction be applicable? The left-hand side adds up the numbers from 1 to

n .

If we know how to do that, adding just one more term (

n + 1

) would not be that hard. For example, if

n = 100,

suppose we know that the sum of the first 100 numbers is

5050

(so

1 + 2 + 3 + \dots + 100 = 5050,

which is true). Now to find the sum of the first 101 numbers, it makes more sense to just add 101 to 5050, instead of computing the entire sum again. We would have

1 + 2 + 3 + \dots + 100 + 101 = 5050 + 101 = 5151 .

In fact, it would always be easy to add just one more term. This is why we should use induction.

Now the formal proof:

Proof.

Let

P (n)

be the statement

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

We will show that

P (n)

is true for all natural numbers

n \geq 1 .

Base case:

P (1)

is the statement

1 = \frac{1 (1 + 1)}{2}

which is clearly true.

Inductive case: Let

k \geq 1

be a natural number. Assume (for induction) that

P (k)

is true. That means

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

We will prove that

P (k + 1)

is true as well. That is, we must prove that

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

To prove this equation, start by adding

k + 1

to both sides of the inductive hypothesis:

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

Now, simplifying the right side we get:

\begin{aligned} \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} \\ = \frac{(k + 2) (k + 1)}{2} . \end{aligned}

Thus

P (k + 1)

is true, so by the principle of mathematical induction,

P (n)

is true for all natural numbers

n \geq 1 .

🔗

Note that in the part of the proof where we proved

P (k + 1)

from

P (k),

we used the equation

P (k) .

This was the inductive hypothesis. Seeing how to use the inductive hypotheses is usually straightforward when proving a fact about a sum like this. In other proofs, it can be less obvious where it fits in.

🔗

Example 4.5.2.

Prove that for all

n \in N,

6^{n} - 1

is a multiple of 5.

🔗

Solution.

Again, start by understanding the dynamics of the problem. What does increasing

n

do? Let’s try with a few examples. If

n = 1,

then yes,

6^{1} - 1 = 5

is a multiple of 5. What does incrementing

n

to 2 look like? We get

6^{2} - 1 = 35,

which again is a multiple of 5. Next,

n = 3 :

But instead of just finding

6^{3} - 1,

what did the increase in

n

do? We will still subtract 1, but now we are multiplying by another 6 first. Viewed another way, we are multiplying a number that is one more than a multiple of 5 by 6 (because

6^{2} - 1

is a multiple of 5, so

6^{2}

is one more than a multiple of 5). What do numbers that are one more than a multiple of 5 look like? They must have last digit 1 or 6. What happens when you multiply such a number by 6? It depends on the number, but in any case, the last digit of the new number must be a 6. And then if you subtract 1, you get last digit 5, so a multiple of 5.

The point is, every time we multiply by just one more six, we still get a number with last digit 6, so subtracting 1 gives us a multiple of 5. Now the formal proof:

Proof.

Let

P (n)

be the statement, “

6^{n} - 1

is a multiple of 5.” We will prove that

P (n)

is true for all

n \in N .

Base case:

P (0)

is true:

6^{0} - 1 = 0,

which is a multiple of 5.

Inductive case: Let

k

be an arbitrary natural number. Assume, for induction, that

P (k)

is true. That is,

6^{k} - 1

is a multiple of

5 .

Then

6^{k} - 1 = 5 j

for some integer

j .

This means that

6^{k} = 5 j + 1 .

Multiply both sides by

6 :

6^{k + 1} = 6 (5 j + 1) = 30 j + 6 .

But we want to know about

6^{k + 1} - 1,

so subtract 1 from both sides:

6^{k + 1} - 1 = 30 j + 5 .

Of course

30 j + 5 = 5 (6 j + 1),

so is a multiple of 5.

Therefore

6^{k + 1} - 1

is a multiple of 5, or in other words,

P (k + 1)

is true. Thus, by the principle of mathematical induction

P (n)

is true for all

n \in N .

🔗

We had to be a little bit clever (i.e., use some algebra) to locate the

6^{k} - 1

inside of

6^{k + 1} - 1

before we could apply the inductive hypothesis. This is what can make inductive proofs challenging.

🔗

In the two examples above, we started with

n = 1

n = 0 .

We can start later if we need to.

🔗

Example 4.5.3.

Prove that

n^{2} < 2^{n}

for all integers

n \geq 5 .

🔗

Solution.

First, the idea of the argument. What happens when we increase

n

by 1? On the left-hand side, we increase the base of the square and go to the next square number. On the right-hand side, we increase the power of 2. This means we double the number. So the question is, how does doubling a number relate to increasing to the next square? Think about what the difference of two consecutive squares looks like. We have

(n + 1)^{2} - n^{2} .

This factors:

(n + 1)^{2} - n^{2} = (n + 1 - n) (n + 1 + n) = 2 n + 1 .

But doubling the right-hand side increases it by

2^{n},

since

2^{n + 1} = 2^{n} + 2^{n} .

When

n

is large enough,

2^{n} > 2 n + 1 .

What we are saying here is that each time

n

increases, the left-hand side grows by less than the right-hand side. So if the left-hand side starts smaller (as it does when

n = 5

), it will never catch up. Now the formal proof:

Proof.

Let

P (n)

be the statement

n^{2} < 2^{n} .

We will prove

P (n)

is true for all integers

n \geq 5 .

Base case:

P (5)

is the statement

5^{2} < 2^{5} .

Since

5^{2} = 25

and

2^{5} = 32,

we see that

P (5)

is indeed true.

Inductive case: Let

k \geq 5

be an arbitrary integer. Assume, for induction, that

P (k)

is true. That is, assume

k^{2} < 2^{k} .

We will prove that

P (k + 1)

is true, i.e.,

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

To prove such an inequality, start with the left-hand side and work towards the right-hand side:

\begin{aligned} (k + 1)^{2} & = k^{2} + 2 k + 1 \\ < 2^{k} + 2 k + 1 & \dots by the inductive hypothesis. \\ < 2^{k} + 2^{k} & \dots since 2 k + 1 < 2^{k} for k \geq 5. \\ = 2^{k + 1} . \end{aligned}

Following the equalities and inequalities through, we get

(k + 1)^{2} < 2^{k + 1},

in other words,

P (k + 1) .

Therefore by the principle of mathematical induction,

P (n)

is true for all

n \geq 5 .

🔗

The previous example might remind you of the racetrack principle from calculus, which says that if

f (a) < g (a),

and

f^{'} (x) < g^{'} (x)

for

x > a,

then

f (x) < g (x)

for

x > a .

Same idea: the larger function is increasing more than the smaller function, so the larger function will stay larger. In discrete math, we don’t have derivatives, so we look at differences. Thus induction is the way to go.

🔗

A Warning.

With great power, comes great responsibility. Induction isn’t magic. It seems very powerful to be able to assume

P (k)

is true. After all, we are trying to prove

P (n)

is true, and the only difference is in the variable:

k

vs.

n .

Are we assuming that what we want to prove is true? Not really. We assume

P (k)

is true only for the sake of proving that

P (k + 1)

is true.

🔗

Still you might start to believe that you can prove anything with induction. Consider this incorrect “proof” that every Canadian has the same eye color: Let

P (n)

be the statement that any

n

Canadians have the same eye color.

P (1)

is true, since everyone has the same eye color as themselves. Now assume

P (k)

is true. That is, assume that in any group of

k

Canadians, everyone has the same eye color. Now consider an arbitrary group of

k + 1

Canadians. The first

k

of these must all have the same eye color, since

P (k)

is true. Also, the last

k

of these must have the same eye color, since

P (k)

is true. So in fact, everyone in the group must have the same eye color. Thus

P (k + 1)

is true. So by the principle of mathematical induction,

P (n)

is true for all

n .

🔗

Clearly something went wrong. The problem is that the proof that

P (k)

implies

P (k + 1)

assumes that

k \geq 2 .

We have only shown

P (1)

is true. In fact,

P (2)

is false. Try this: read through the previous paragraph again, substituting

1

for each

k .

Can you spot the error in that argument?

🔗

Reading Questions Reading Questions

1.

Suppose you wanted to prove, using mathematical induction, that

1 + 3 + 5 + \dots + 2 n - 1 = n^{2}

for all values of

n \geq 1 .

Which of the following would be an appropriate first line of the proof? Select all that apply.

🔗

Let $P (n)$ be the statement “ $1 + 3 + 5 + \dots + 2 n - 1 = n^{2} .$ ”
Correct. Note in particular, we do not include the “for all $n \geq 1$ ” as part of the definition of $P (n) .$
For each $n \geq 1,$ let $P (n)$ be the statement, “the sum of the first $n$ odd numbers is $n^{2} .$ ”
This is correct. Note that saying that we define $P (n)$ for each $n \geq 1$ is different from saying that $P (n)$ includes “...for all $n \geq 1 .$ ”
Assume $1 + 3 + \dots + 2 n - 1 = n^{2}$ for all $n \geq 1 .$
This is what you are trying to prove, so you cannot assume it. Later in the proof (in the inductive case) we will assume that $P (k)$ is true for some arbitrary $k,$ but this is not assuming it is true for all $n$ at once.
Let $P (n)$ be the statement, “ $1 + 3 + \dots + 2 n - 1 = n^{2}$ for all $n \geq 1 .$ ”
This doesn’t make sense: what would $P (3)$ be? That $1 + 3 + 5 = 3^{2}$ for all $3 \geq 1 ??$
Since $P (1) = 1 = 1^{2},$ the base case is true.
Two problems here: first, you need to say what $P (n)$ is. Second, $P (1)$ is a statement, so it cannot be equal to the number 1.

🔗

2.

Suppose you wanted to prove that

P (n, 3) \geq (\binom{n}{3})

for all

n \geq 4 .

Write the first line of a proof by induction.

🔗

3.

What questions do you have? Write at least one question about the content of this section that you or a classmate might be curious about after reading this section.

🔗

Exercises Practice Problems

1.

Suppose you are trying to prove, by mathematical induction, that a statement

P (n)

is true for all

n \geq 0 .

What would you attempt to prove in the induction step of the proof? (Select all that apply.)

🔗

That assuming $P (k)$ is true for an arbitrary $k \geq 0,$ we can prove that $P (k + 1)$ is true.
That $P (k)$ implies $P (k + 1)$ for all $k \geq 0 .$
That assuming $P (k + 1)$ is true for an arbitrary $k \geq 0,$ we can prove that $P (k)$ is true.
That $P (k + 1)$ implies $P (k)$ for all $k \geq 0 .$
That $P (k)$ implies $P (k + 1)$ for at least one $k \geq 0 .$

🔗

2.

Suppose you wanted to prove the following statement:

🔗

2 + 4 + 6 + \dots + 2 n = n (n + 1) for all n \geq 1 .

What would the first line of a proof by induction be?

🔗

Let $P (n)$ be the statement “ $2 + 4 + 6 + \dots + 2 n = n (n + 1) .$ ”
Let $P (n)$ be the statement “ $2 + 4 + 6 + \dots + 2 n = n (n - 1)$ for all $n \geq 1 .$ ”
Assume $P (n)$ is true for all $n \geq 1 .$
Let $P (n) = 2 + 4 + 6 + \dots + 2 n .$
Suppose $P (n) = n (n + 1)$ for all $n \geq 1 .$

🔗

3.

Suppose you were proving the following statement by mathematical induction:

🔗

2 + 4 + 6 + \dots + 2 n = n (n + 1) for all n \geq 1 .

What would you need to show to establish the base case?

🔗

Show that $P (1)$ is true. That is, show that $2 = 1 (1 + 1) .$
Show that $P (2)$ is true. That is, show that $2 + 4 = 2 (2 + 1) .$
Even though the sum starts with $2,$ we need to consider the smallest $n$ for which the statement $P (n)$ is true.
Show that $P (1)$ and $P (2)$ are both true.
Show that $P (1)$ implies $P (2) .$
Nothing, since the sum already has more than $n = 1$ terms.

🔗

4.

Suppose you were proving the following statement by mathematical induction:

🔗

2 + 4 + 6 + \dots + 2 n = n (n + 1) for all n \geq 1 .

What would the first line of the inductive case be?

🔗

Assume $P (k)$ is true for some arbitrary $k \geq 1,$ that is, assume $2 + 4 + 6 + \dots + 2 k = k (k + 1) .$
Assume $P (k)$ is true for all $k \geq 1,$ that is, assume $2 + 4 + 6 + \dots + 2 k = k (k + 1) .$
Assume $P (k)$ and $P (k)$ are both true for an arbitrary $k \geq 1;$ that is, assume $2 + 4 + 6 + \dots + 2 k = k (k + 1)$ and $2 + 4 + 6 + \dots + 2 k + 2 k + 2) = (k + 1) (k + 2) .$
Assume $P (k)$ implies $P (k + 1)$ for an arbitrary $k \geq 1 .$
Assume $P (k)$ is true for some large $k \geq 1;$ say, assume $2 + 4 + 6 + \dots + 432 = 216 (217) .$

🔗

5.

Arrange some of the statements below to create a correct proof by induction that the recurrence relation

a_{n} = 5 a_{n - 1} + 4,

with initial condition

a_{0} = 0

has closed formula

a_{n} = 5^{n} - 1 .

Let \(P(n)\) be the statement, “\(a_n = 5^n - 1\)”.
---
Note that \(a_0 = 5^0 - 1 = 0\text{,}\) so \(P(0)\) is true.
---
Now assume that \(P(k)\) is true for an arbitrary integer \(k \ge 0\text{.}\)

---
Then \(a_k = 5^k - 1\text{.}\)

---
By the recurrence relation, we have \(a_{k+1} = 5 a_k + 4 = 5 (5^k -1) + 4\text{.}\)

---
This simplifies to \(a_{k+1} = 5^{k+1} - 5 + 4 = 5^{k+1} - 1\text{,}\) so \(P(k+1)\) is true.
---
Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 0\text{.}\)

---
Now assume that \(P(k+1)\) is true for an arbitrary integer \(k \ge 0\text{.}\)
 #distractor
---
Then \(a_{k+1} = 5a_k+4\text{,}\) so \(P(k+1)\) is true.
 #distractor

🔗

6.

Arrange some of the statements below to create a correct proof by induction that for all

n \geq 1,

the number

14^{n} - 1

is a multiple of

13 .

Let \(P(n)\) be the statement, “\(14^n - 1\) is a multiple of \(13\text{.}\)”
---
Note that \(14^1 - 1 = 13\text{,}\) so this is definitely a multiple of \(13\text{.}\)

---
Now assume that \(P(k)\) is true for an arbitrary integers \(k \ge 1\text{.}\)

---
Then \(14^k - 1 = 13\cdot j\) for some integer \(j\text{.}\)

---
Since \(14^{k+1} - 1 = 14(14^k - 1) + 14 - 1 = 14(13\cdot j) + 13\text{,}\) we see that \(14^{k+1} - 1\) is a multiple of \(13\text{.}\)

---
Thus \(P(k+1)\) is true.
---
Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\)

---
Note that \(14^2 - 1 = (14-1)(14+1)\) by difference of squares, so this is a multiple of 13. #distractor
---
Now assume that \(P(n)\) is true for all \(n \ge 1\text{.}\)
 #distractor
---
Thus \(14^k = \frac{14^{k+1} - 1}{14}\text{,}\) which must also be a multiple of 13.
 #distractor

🔗

7.

Arrange some of the statements below to create a correct proof by induction that for all

n \geq 1,

1 + 1 + 2 + 3 + 5 + \dots + F_{n} = F_{n + 2} - 1,

where

F_{n}

is the

n

th Fibonacci number.

Let \(P(n)\) be the statement, “\(1+1+2+3+5+\cdots + F_n = F_{n+2} - 1\text{.}\)”
---
For the base case, note that \(P(1)\) and \(P(2)\) are true, because \(1 = 2-1\) and \(1+1 = 3-1\text{.}\)

---
Now assume that \(P(k)\) is true for an arbitrary integer \(k \ge 2\text{.}\)

---
That is, assume \(1+1+2+3 + 5+F_k = F_{k+2} - 1\text{.}\)

---
Then adding \(F_{k+1}\) to both sides, we get \(1+1+2+3+5+\cdots + F_k + F_{k+1} = F_{k+1} + F_{k+2} - 1\text{.}\)

---
By the definition of Fibonacci numbers, \(F_{k+1} + F_{k+2} = F_{k+3}\text{,}\) so the right-hand side simplifies to \(F_{k+3} - 1\text{.}\)

---
Thus \(P(k+1)\) is true, and therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\)

---
For the base case, note that \(1+1+2 = 4 = F_{5}-1\text{.}\)
 #distractor
---
Then by the inductive hypothesis, \(1+1+2+3+\cdots+F_{k+1} = F_{k+2} - 1\text{.}\)
 #distractor
---
Subtracting \(F_{k+1}\) from both sides gives us \(P(k)\text{,}\) which we also assumed to be true.
 #distractor

🔗

Exercises Additional Exercises

1.

On the way to the market, you exchange your cow for some magic dark chocolate espresso beans. These beans have the property that every night at midnight, each bean splits into two, effectively doubling your collection. You decide to take advantage of this, and each morning (around 8 am) you eat 5 beans.

🔗

Explain why it is true that if at noon on day $n$ you have a number of beans ending in a 5, then at noon on day $n + 1$ you will still have a number of beans ending in a 5.
Why is the previous fact not enough to conclude that you will always have a number of beans ending in a 5? What additional fact would you need?
Assuming you have the additional fact in part (b), and have successfully proved the fact in part (a), how do you know that you will always have a number of beans ending in a 5? Illustrate what is going on by carefully explaining how the two facts above prove that you will have a number of beans ending in a 5 on day 4 specifically. In other words, explain why induction works in this context.

🔗

2.

Use induction to prove for all

n \in N

that

\sum_{k = 0}^{n} 2^{k} = 2^{n + 1} - 1 .

🔗

3.

Prove that

7^{n} - 1

is a multiple of 6 for all

n \in N .

🔗

4.

Prove that

1 + 3 + 5 + \dots + (2 n - 1) = n^{2}

for all

n \geq 1 .

🔗

5.

Prove that

F_{0} + F_{2} + F_{4} + \dots + F_{2 n} = F_{2 n + 1} - 1

where

F_{n}

is the

n

th Fibonacci number.

🔗

6.

Prove that

2^{n} < n!

for all

n \geq 4 .

(Recall,

n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n .

)

🔗

7.

Prove, by mathematical induction, that

F_{0} + F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1,

where

F_{n}

is the

n

th Fibonacci number (

F_{0} = 0,

F_{1} = 1

and

F_{n} = F_{n - 1} + F_{n - 2}

🔗

8.

Zombie Euler and Zombie Cauchy, two famous zombie mathematicians, have just signed up for Myspace accounts. After one day, Zombie Cauchy has more followers than Zombie Euler. Each day after that, the number of new followers of Zombie Cauchy is exactly the same as the number of new followers of Zombie Euler (and neither lose any followers). Explain how a proof by mathematical induction can show that on every day after the first day, Zombie Cauchy will have more followers than Zombie Euler. That is, explain what the base case and inductive case are, and why they together prove that Zombie Cauchy will have more followers on the 4th day.

🔗

9.

Find the largest number of points that it is impossible for a football team to get exactly, using just 3-point field goals and 7-point touchdowns (ignore the possibilities of safeties, missed extra points, and two-point conversions). Prove your answer is correct by mathematical induction.

🔗

Hint.

It is not possible to score exactly 11 points. Can you prove that you can score

n

points for any

n \geq 12 ?

🔗

10.

Prove that the sum of

n

squares can be found as follows

🔗

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

🔗

11.

Prove that the sum of the interior angles of a convex

n

-gon is

(n - 2) \cdot 180^{\circ} .

(A convex

n

-gon is a polygon with

n

sides for which each interior angle is less than

180^{\circ} .

)

🔗

Hint.

Start with

(k + 1)

-gon, and divide it up into a

k

-gon and a triangle.

🔗

12.

What is wrong with the following “proof” of the “fact” that

n + 3 = n + 7

for all values of

n

(besides of course that the thing it is claiming to prove is false)?

🔗

Proof.

Let

P (n)

be the statement that

n + 3 = n + 7 .

We will prove that

P (n)

is true for all

n \in N .

Assume, for induction, that

P (k)

is true. That is,

k + 3 = k + 7 .

We must show that

P (k + 1)

is true. Now since

k + 3 = k + 7,

add 1 to both sides. This gives

k + 3 + 1 = k + 7 + 1 .

Regrouping

(k + 1) + 3 = (k + 1) + 7 .

But this is simply

P (k + 1) .

Thus by the principle of mathematical induction

P (n)

is true for all

n \in N .

🔗

13.

The proof in the previous problem does not work. But if we modify the “fact,” we can get a working proof. Prove that

n + 3 < n + 7

for all values of

n \in N .

You can do this proof with algebra (without induction), but the goal of this exercise is to write out a valid induction proof.

🔗

14.

Find the flaw in the following “proof” of the “fact” that

n < 100

for every

n \in N .

🔗

Proof.

Let

P (n)

be the statement

n < 100 .

We will prove

P (n)

is true for all

n \in N .

First we establish the base case: when

n = 0,

P (n)

is true, because

0 < 100 .

Now for the inductive step, assume

P (k)

is true. That is,

k < 100 .

Now if

k < 100,

then

k

is some number, like 80. Of course

80 + 1 = 81

which is still less than 100. So

k + 1 < 100

as well. But this is what

P (k + 1)

claims, so we have shown that

P (k) \to P (k + 1) .

Thus by the principle of mathematical induction,

P (n)

is true for all

n \in N .

🔗

15.

While the above proof does not work (it better not since the statement it is trying to prove is false!) we can prove something similar. Prove that there is a strictly increasing sequence

a_{1}, a_{2}, a_{3}, \dots

of numbers (not necessarily integers) such that

a_{n} < 100

for all

n \in N .

(By strictly increasing we mean

a_{n} < a_{n + 1}

for all

n .

So each term must be larger than the last.)

🔗

Hint.

For the inductive step, you can assume you have a strictly increasing sequence up to

a_{k}

where

a_{k} < 100 .

Now you just need to find the next term

a_{k + 1}

so that

a_{k} < a_{k + 1} < 100 .

What should

a_{k + 1}

be?

🔗

16.

What is wrong with the following “proof” of the “fact” that for all

n \in N,

the number

n^{2} + n

is odd?

🔗

Proof.

Let

P (n)

be the statement “

n^{2} + n

is odd.” We will prove that

P (n)

is true for all

n \in N .

Suppose, for induction, that

P (k)

is true, that is, that

k^{2} + k

is odd. Now consider the statement

P (k + 1) .

Now

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

By the inductive hypothesis,

k^{2} + k

is odd, and of course

2 k + 2

is even. An odd plus an even is always odd, so therefore

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

is odd. Therefore by the principle of mathematical induction,

P (n)

is true for all

n \in N .

🔗

17.

Now give a valid proof (by induction, even though you might be able to do so without using induction) of the statement, “For all

n \in N,

the number

n^{2} + n

is even.”

🔗

Hint.

For the inductive case, you will need to show that

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

is even. Factor this out, and locate the part of it that is

k^{2} + k .

What have you assumed about that quantity?

🔗

18.

Prove that there is a sequence of positive real numbers

a_{0}, a_{1}, a_{2}, \dots

such that the partial sum

a_{0} + a_{1} + a_{2} + \dots + a_{n}

is strictly less than

2

for all

n \in N .

Hint: Think about how you could define what

a_{k + 1}

is to make the induction argument work.

🔗

Hint.

This is similar to Exercise 15, although there you were showing that a sequence had all its terms less than some value, and here you are showing that the sum is less than some value. But the partial sums forms a sequence, so this is actually very similar.

🔗

19.

Use induction to prove that if

n

people all shake hands with each other, that the total number of handshakes is

\frac{n (n - 1)}{2} .

🔗

Hint.

We have already proved this without using induction, but looking at it inductively sheds light onto the problem (and is fun).

The question you need to answer to complete the inductive step is, how many new handshakes take place when a person

k + 1

enters the room? Why does adding this give you the correct formula?

🔗

20.

Use induction to prove that

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n} .

That is, the sum of the

n

th row of Pascal’s triangle is

2^{n} .

🔗

Hint.

Here’s the idea: Since every entry in Pascal’s triangle is the sum of the two entries above it, we can get the

k + 1

st row by adding up all the pairs of entry from the

k

th row. But doing this uses each entry on the

k

th row twice. Thus each time we drop to the next row, we double the total. Of course, row 0 has sum

1 = 2^{0}

(the base case). Now try to make this precise with a formal induction proof. You will use the fact that

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

for the inductive case.

🔗

21.

Use induction to prove

(\binom{4}{0}) + (\binom{5}{1}) + (\binom{6}{2}) + \dots + (\binom{4 + n}{n}) = (\binom{5 + n}{n}) .

(This is an example of the hockey stick theorem.)

🔗

Hint.

To see why this works, try it on a copy of Pascal’s triangle. We are adding up the entries along a diagonal, starting with the 1 on the left-hand side of the 4th row. Suppose we add up the first 5 entries on this diagonal. The claim is that the sum is the entry below and to the left of the last of these 5 entries. Note that if this is true, and we instead add up the first 6 entries, we will need to add the entry one spot to the right of the previous sum. But these two together give the entry below them, which is below and left of the last of the 6 entries on the diagonal. If you follow that, you can see what is going on. But it is not a great proof. A formal induction proof is needed.

🔗

22.

Use the product rule for logarithms (

\log (a b) = \log (a) + \log (b)

) to prove, by induction on

n,

that

\log (a^{n}) = n \log (a),

for all natural numbers

n \geq 2 .

🔗

23.

Let

f_{1}, f_{2}, \dots, f_{n}

be differentiable functions. Prove, using induction, that

🔗

(f_{1} + f_{2} + \dots + f_{n})^{'} = f_{1}^{'} + f_{2}^{'} + \dots + f_{n}^{'} .

🔗

You may assume

(f + g)^{'} = f^{'} + g^{'}

for any differentiable functions

f

and

g .

🔗

Hint.

You are allowed to assume the base case. For the inductive case, group all but the last function together as one sum of functions, and then apply the usual sum of derivatives rule, and then the inductive hypothesis.

🔗

24.

Suppose

f_{1}, f_{2}, \dots, f_{n}

are differentiable functions. Use mathematical induction to prove the generalized product rule:

🔗

(f_{1} f_{2} f_{3} \dots f_{n})^{'} = f_{1}^{'} f_{2} f_{3} \dots f_{n} + f_{1} f_{2}^{'} f_{3} \dots f_{n} + f_{1} f_{2} f_{3}^{'} \dots f_{n} + \dots + f_{1} f_{2} f_{3} \dots f_{n}^{'} .

🔗

You may assume the product rule for two functions is true.

🔗

Hint.

For the inductive step, we know by the product rule for two functions that

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

Then use the inductive hypothesis on the first summand, and distribute.

🔗

25.

In Exercises we proved that the following is a valid deduction rule:

🔗

	$P \to Q$
	$Q \to R$
$∴$	$P \to R$

Now use mathematical induction to prove you can chain together any number of statements like this. That is, prove for any

n

that the following is a valid deduction rule:

🔗

	$P_{1} \to P_{2}$
	$P_{2} \to P_{3}$
	$⋮$
	$P_{n - 1} \to P_{n}$
$∴$	$P_{1} \to P_{n} .$

Hint.

You can inductively assume that from the first

n - 2

implications you can deduce

P_{1} \to P_{n - 1} .

Then you can use a truth table to verify that this simplified deduction rule is valid.

🔗

You have attempted 1 of 8 activities on this page.

🔗

Prev Top Next

Section 4.5 Proof by Induction

Objectives

Subsection Section Preview

Investigate!

Worksheet Preview Activity A4US

1.

2.

3.

4.

Subsection Recursive Reasoning

Proof.

Subsection Formalizing Proofs

Induction Proof Structure.

Subsection Examples

Example 4.5.1.

Proof.

Example 4.5.2.

Proof.

Example 4.5.3.

Proof.

A Warning.

Reading Questions Reading Questions

1.

2.

3.

Exercises Practice Problems

1.

2.

3.

4.

5.

6.

7.

Exercises Additional Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

Proof.

13.

14.

Proof.

15.

16.

Proof.

17.

18.

19.

20.

21.

22.

23.

24.

25.

Worksheet Preview Activity
A4 US