Strong Induction Can Exploit Multiple Prior Values

Subsection 8.10.3 Strong Induction Can Exploit Multiple Prior Values

So far, we’ve used strong induction to prove that every positive integer can be written as the sum of distinct powers of 2. When we did that, we exploited strong induction to do something that weak induction couldn’t straightforwardly do: While we only needed to exploit the induction hypothesis to assert the truth of P for a single value, we reached back arbitrarily far to choose that value.

In the next example, we’ll reach back in a more controlled way, but we’ll need to use the induction hypothesis to assert the truth of P for two values (in particular n and n – 1). We’ll prove a claim about the Fibonacci numbers. Because all but the first two values of this sequence are computed from the values of the previous two values, the most straightforward way to prove our claim is by strong induction.

Recall the definition of the Fibonacci numbers:

f1 = 1, (The first element is 1.)

f2 = 1, (So is the next one.)

for all k  2, fk+1 = fk + fk-1 (Other elements computed from the two previous ones.)

We want to prove the following claim about the elements of this sequence:

[1] For all n  1: f_n  (3/2)^(n-2)

The proof is by strong induction. We begin with a clear statement of P: For any n  1,

P(n)  f_n  (3/2)^(n-2)

Base cases: P(1) is true: (3/2)^(1-2) = 2/3. 1  2/3.

P(2) is true: (3/2)^(2-2) = 1. 1  1.

Induction step: We must prove that, for any n > 2, if f_k  (3/2)^(k-2)is true for all positive values of k up to and including n, then f_(n+1)  (3/2)^((n+1)-2).

The induction hypothesis is that f_k  (3/2)^(k-2) is true for all positive values of k up to and including n.

We begin by writing down what we know about fn+1:

[2] fn+1 = fn + fn-1 Definition of the sequence

[3]  (3/2)^(n-2) + (3/2)^(n-3) Using the induction hypothesis twice.

At this point, we realize that we need to manipulate the right hand side expression to make it (3/2)^(n-2). So we start trying to do that.

[4]  (3/2)(3/2)^(n-3)+ (3/2)^(n-3)

[5]  (3/2+1) (3/2)^(n-3) Factoring out (3/2)^(n-3)

[6]  (5/2) (3/2)^(n-3)

[7]  (9/4) (3/2)^(n-3) Okay because (9/4)< (5/2) . Done to get us closer to the goal.

[8]  (3/2)^2 (3/2)^(n-3) = (3/2)^(n-1) = (3/2)^((n+1)-2)

So, using the Principle of Strong Induction, we have that, for all n  1: f_n  (3/2)^(n-2) .

Exercises Exercises

Exercise Group.

Prove that, for any integer n > 1, n can be written as the product of primes. Let’s first check this claim for plausibility. We can observe:

2 = 2

5 = 5

10 = 2 ⋅ 5

12 = 2 ⋅ 2 ⋅ 3 and so forth

Note that the “product of primes” may have just a single factor (e.g., 2 or 5).

Use strong induction to prove the claim.

Note that, for the induction step: We must prove:

(for any i such that 2 ≤ i ≤ n it is the case that i can be written as the product of primes)

→

(n+1 can be written as the product of primes)

Part 1.

Base case: What base case should we use?

Answer.

Correct answer is C

Solution.

Explanation: Since 2 is the first prime, no integer less than 2 can possibly be written as the product of primes. So 2 should be the base case. By the way, you could have gotten this from the statement that we are trying to prove. We said that it should be true of every integer greater than 1.

Part 2.

Now write out a proof of the base case. When you’ve done it, click here to see ours. When clicked, should see:

2 can be written simply as 2.

Induction step: We must prove:

(for any i such that 2  i  n it is the case that i can be written as the product of primes)

\(\rightarrow \)

(n+1 can be written as the product of primes)

Let’s consider using Case Enumeration to do this. Think about it. How many (and which) cases should we use?

1
2
3
No finite number of cases will work. We need to try something else.

Answer.

Correct answer is B.

Solution.

Explanation: We’ll use two cases: n+1 is prime and n+1 is composite.

3.

Define the following sequence:

a0 = 0,

a1 = 1,

For all n ≥ 1, an+1 = 3an - 2an-1

The first several terms of the sequence are 0, 1, 3, 7, 15, 31, 63, 127.

Prove the following claim about the elements of this sequence:

[1] For all n ≥ 0: \(a_{n} = \ 2^{n} - 1\)

First, check for plausibility. Does the claim appear to be true?

Now use strong induction to prove the claim.

Begin with a clear statement of P. Write it down. Then click here to check it. When clicked, should see:

P(n)  (a_n= 2^n-1)

Base case: How many base cases do we need to prove?

Answer.

Explanation: Since there are two values that are specified before the recursive definition is given, we must prove the claim true for both of them.

4.

(Previous one, continued) Write a proof of the base case(s). Then click here to check it.: For n = 0: a0 = 0 and 20 – 1 = 1 – 1 = 0 For n = 1: a1 = 1 and 21 – 1 = 2 – 1 = 1

Answer.

Induction step: When we do a proof by strong induction, we can assume, as the induction hypothesis, that P is true for all values starting at the base case(s) and going up to n. But sometimes we don’t actually need all of them. In those cases, we may take the induction hypothesis to be just what we need. Try to write your proof of the induction step. What should we write as our induction hypothesis? When you’ve got an answer, click here to see ours. When clicked, should see: To show that P holds for n+1, we just need to know that P holds for n and n-1. So we must assume: a_n= 2^n-1 and a_(n-1)= 2^(n-1)-1 Now continue writing your proof of the induction step. If you need a hint, click here. When clicked, should see: We need to end up having proved: an+1 = 2^(n+1)-1 So start by writing something that we know about an+1. Use the recursive definition of the sequence as given above. Then see if you can do the algebra to transform the right hand side into the expression that we need. If you need another hint, click here. When clicked, should see: We start by writing: [1] an+1 = 3an-2an-1 Definition of the sequence Now, can you use the induction hypothesis to rewrite the right hand side in a useful way? When you’ve finished writing your proof, click here to see ours. When clicked, should see: The proof is by strong induction. P(n)  a_n= 2^n-1 Base case: For n = 0: a0 = 0 and 20 – 1 = 1 – 1 = 0 For n = 1: a1 = 1 and 21 – 1 = 2 – 1 = 1 Induction step: Assume: a_n= 2^n-1 and a_(n-1)= 2^(n-1)-1 [1] an+1 = 3an - 2an-1 Definition of the sequence [2] = 3(2n - 1) – 2(2n-1 - 1) Induction hypothesis [3] = 32n - 3 - 22n-1 + 2 [4] = 32n - 3 - 2n + 2 [5] = 22n - 1 [6] = 2n+1 - 1