Subsection 8.9.1 Proving Claims about Inequalities
Induction can be used to prove claims about inequalities, as well as equalities. Let’s consider an interesting one (here we’ve used another common way of writing a universal claim):
For n ≥ 4, n2 ≤ 2n
This claim is significant. It says that, after a few small special cases, the value of the exponential function, 2n, is always greater than or equal to the value of the quadratic function, n2.
Prove by induction: For n 4, n2 2n
Define: P(n) n2 2n
Base case: P(4) is true since: 42 = 16 16 = 2n
Inductive step: Prove that, for n 4, (n2 2n) ((n+1)2 2n+1)
Inductive hypothesis: n2 2n
How should we start? Notice that we want to show that (n+1)2 has some property (namely that it’s less than or equal to 2n+1). So let’s start with (n+1)2, do some algebra, and see if we can derive what we need.
[1] (n+1)2 = n2 + 2n + 1
[2] n2 + 2n + n Since n is at least 4 and thus > 1
[3] n2 + 3n
[4] n2 + nn Since n is at least 4 and thus > 3
[5] 2n2
[5] 2 2n The inductive hypothesis says that n2 2n.
But 2 2n = 2n+1. So:
[6] (n+1)2 2n+1
Thus, by the principle of Mathematical Induction, we have proved our claim.
Notice that, in this example, the base case was 4 (not 0 or 1). That isn’t uncommon. Often interesting properties don’t appear until after a small number of special cases.
Exercises Exercises
1.
Consider this claim:
For n ≥ 0, n < 2n
Notice that this is yet another claim about a relationship between one function and another. For all positive integers, 2n is greater than n itself.
We first check for plausibility. Do it for n = 0, 1, 2, and 5.
You’ll find that the claim appears to be true. Now prove it.
(n = 0) 0 < 20 = 1
(n = 1) 1 < 21 = 2
(n = 2) 2 < 22 = 4
(n = 5) 5 < 25 = 32
The claim appears to be true. Now we need to prove it. We’ll use induction to do so. Generally an induction proof requires three steps:
Write an explicit statement of the predicate, which we’ll call P(n).
(Base Case) Prove that P(n) holds for some base case b.
(Induction Step) Prove that, for all integers n ≥ b, P(n) P(n+1).
(Step 1) Fill in the ÿblank here:
P(n)
Click here to see the answer before you continue. If clicked, should see:
P(n) n < 2n
You should now do steps 2 and 3.
(Step 2, Base Case) Show that P(0) is true. Click here if you’d like to see a solution before you go on to step 3. (Hint: We’ve actually already done it.) If clicked, should see:
Base case: 0 is the base case. 0 < 20 = 1
(Step 3, Inductive Step) The first thing to do here is to write out the claim that we’re trying to prove. It looks like the general claim shown as step 3 above, but we need to fill it in for the specific P(n) we are trying to prove. Do it. Then click here to check it before going on. When clicked, should see:
Prove: For n 0, (n < 2n) ((n+1) < 2n+1)
Next, let’s be explicit. Write down the inductive hypothesis. Click here to check it before going on. When clicked, should see:
n < 2n
Now see if you can complete the proof. Click here if you’d like a hint. If clicked, should see:
This claim is so simple that it may be hard to see how to start. But even in this easy case, a good strategy is to write down something that is guaranteed to be true about n+1. Then try to work with that to derive the claim, about it, that we are trying to prove. So write down:
[1] n+1 = n+1
Can you use the inductive hypothesis to transform that into an inequality?
If you’d like another hint, click here. If clicked, should see:
We already have:
[1] n+1 = n+1
The induction hypothesis tells us that n < 2n. So we can use that to rewrite n on the right hand side. That gives us:
[2] n+1 < 2n+1
If you’d like another hint, click here. When clicked, should see:
So far, we’ve got:
[1] n+1 = n+1
[2] n+1 < 2n+1 Using the induction hypothesis
We need to get the right hand side to be 2n+1. We could do that if we could first get it to be 2n + 2n, since that’s 22n, which is 2n+1. Can you transform the 1 on the right hand side of [2] into 2n? Remember that we’re working with inequalities, not equalities, so you have more flexibility.
When you’re ready, click here to see our proof. When clicked, should see:
The proof of the claim is by induction on n:
Base case: 0 is the base case. 0 < 20 = 1
Inductive Step: Prove: For n 0, (n < 2n) ((n+1) < 2n+1)
[1] n+1 = n+1
[2] n+1 < 2n+1 Using the induction hypothesis
[3] < 2n + 2n Since for n 0, 1 2n
[4] < 2 2n
[5] < 2n+1
Thus, by the Principle of Mathematical Induction: For n 0, n < 2n
2.
Consider this claim:
For n ≥ 4, n! > 2n
Notice that this is yet another claim about a relationship between one function and another. Except for a few small special cases, n! is always greater than the exponential function 2n.
We first check for plausibility. Do it for n = 4, 5, and 6.
You’ll find that the claim appears to be true. Now prove it.