Examples of Induction Proofs
Purplemath
On the previous two pages, we learned the basic structure of induction proofs, did a proper proof, and failed twice to prove things via induction that weren't true anyway. (Sometimes failure is good!)
But the inductive step (that is, the step where you use the assumption step) in these proofs can be a little hard to grasp at first, so I'd like to show you some more examples.
I won't be doing as much commentary on these proofs; I'll mostly just be showing the method of attack. (Again, I will be using (*), or "star", to name the formula under consideration; "LHS" will be used to refer to the left-hand side of the formula under consideration, and "RHS" will be used to refer to the right-hand side of the formula.)
- (*) Prove: For n ≥ 1, 2 + 22 + 23 + 24 + ... + 2n = 2n+1 − 2
Let n = 1. Then the left-hand side (LHS) is:
2 + 22 + 23 + 24 + ... + 2n = 21 = 2
...and the right-hand side (RHS) is:
2n+1 − 2 = 21+1 − 2 = 22 − 2 = 4 − 2 = 2
The LHS equals the RHS, so (*) works for n = 1.
Assume, for n = k, that (*) holds; that is, assume that:
2 + 22 + 23 + 24 + ... + 2k = 2k+1 − 2
Let n = k + 1. Then the LHS of (*) gives us:
The RHS of (*) gives us:
The LHS equals the RHS, so (*) works for n = k + 1. Therefore, (*) works for all n ≥ 1.
Note this common technique: In the "n = k + 1" step, it is usually a good first step to write out the whole formula in terms of k + 1, and then break off the "n = k", so you can replace it with whatever assumption you made about n = k in the assumption step. Then you manipulate and simplify, and try to rearrange things to get the RHS of the formula to match what you got for the LHS.
If your proof never uses the equation from the assumption step, then you're safe in assuming that you're doing something wrong.
- (*) Prove: For n ≥ 1, 1×2 + 2×3 + 3×4 + … + (n)(n+1) =
Let n = 1. Then the LHS of (*) is 1×2 = 2. For the RHS, we get:
The LHS equals the RHS, so (*) holds for n = 1.
Assume that, for n = k, (*) holds; that is, assume the following to be true:
1×2 + 2×3 + 3×4 + ... + (k)(k+1) =
Let n = k + 1. The left-hand side of (*) then gives us:
The RHS of (*) is:
The LHS equals the RHS, so (*) holds for all n ≥ 1.
- (*) Prove: For n ≥ 5, 4n < 2n.
This one doesn't start at n = 1, and it involves an inequality instead of an equation. (If you graph y = 4x and y = 2x on the same axes, you'll see why we have to start at n = 5, instead of the customary n = 1.) So the base case is:
Let n = 5. The LHS of (*) is 4(5) = 20. The RHS is:
2k = 25 = 32
Since 20 < 32, then (*) holds at n = 5.
Assume, for n = k, that (*) holds; that is, assume the following:
4k < 2k
Let n = k + 1. The LHS of (*) gives us:
4(k + 1) = 4k + 4 (I)
Splitting off the portion of the RHS of Equation (I) that matches the assumption step, and then applying the assumption step, we get:
[4k] + 4 < [2k] + 4 (II)
Since k ≥ 5, then 4 < 32 ≤ 2k. Then, applying this inequality to the RHS of Equaiton (II) and simplifying, we get
2k + 4 < 2k + 2k = 2×2k = 21×2k = 2k+1 (III)
We established, in Equation (I), that the LHS of Equation (I) is less than the RHS of Equation (II) — which is also the LHS of Equation (III). Following this through to the last expression in Equation (III), we get:
4(k+1) < 2k+1
Thus, (*) holds for n = k + 1, so (*) holds for all n ≥ 5.
"Where the heck," I hear you asking, "did you come up with these steps?!?" That's a reasonable question.
The above proof was not obvious to, or easy for, me. It took me a while, fiddling with numbers, inequalities, exponents, etc, to stumble upon something that worked.
This will often be the hardest part of an inductive proof: figuring out the "magic" that makes the induction step go where you want it to. There is no formula; there is no trick. It just takes some time, some scratch-paper, and some willingness to, well, try stuff.
Whatever you do, don't give up on yourself. You're clever; you can do this!
- (*) Prove: For all n ≥ 1, 8n − 3n is divisible by 5.
Let n = 1. Then we have:
8n − 3n = 81 − 31 = 8 − 3 = 5
Obviously, 5 is divisible by 5, so (*) holds for n = 1.
Assume, for n = k, that (*) holds; that is, assume that the following is true:
8k − 3k = 5t
...for some whole number t; in other words, that the difference evaluates to some multiple of 5, and is thus divisible by 5.
Let n = k + 1.
Then we have the following:
Since we can factor a 5 out front, then the entire expression must be divisible by 5; (*) holds for n = k + 1, and thus for all n ≥ 1.
I can hear you thinking, "Aw, c'mon! How the heck?!?" Yes, that "subtract and add the same thing in the middle" thing seems quite bogus. It very rarely comes up, and it's almost never mentioned in the lecture or the textbook. But there are times when simply nothing else will do. So study this last example, and keep its existence in the back of your head. Ya never know when you might need it.
© 2024 Purplemath, Inc. All right reserved. Web Design by 