Induction Proofs: Worked examples (page 3 of 3) Sections: Introduction, Examples of where induction fails, Worked examples
Let n = 1. Then: 2 + 2^{2} + 2^{3} + 2^{4} + ... + 2^{n} = 2^{1} = 2 ...and: 2^{n+1} – 2 = 2^{1+1} – 2 = 2^{2} – 2 = 4 – 2 = 2 So (*) works for n = 1. Assume, for n = k, that (*) holds; that is, that 2 + 2^{2} + 2^{3} + 2^{4} + ... + 2^{k} = 2^{k+1} – 2 Let n = k + 1. 2 + 2^{2}
+ 2^{3} + 2^{4} + ... + 2^{k} + 2^{k+1}
^{
} = [2 + 2^{2} + 2^{3} + 2^{4}
+ ... + 2^{k}] + 2^{k+1}
^{
} = [2^{k+1} – 2] + 2^{k+1}
^{}
= 2×2^{k+1} – 2 Then (*) works for n = k + 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" part, so you can replace it with whatever assumption you made about n = k in the previous step. Then you manipulate and simplify, and try to rearrange things to get the righthand side of the formula in terms of k + 1.
Let n = 1. Copyright © Elizabeth Stapel 20002011 All Rights Reserved Then the lefthand
side of (*)
is 1×2
= 2 So (*) holds for n = 1. Assume, for n = k, that (*) holds; that is, assume that 1×2 + 2×3 + 3×4 + ... + (k)(k+1) = (k)(k+1)(k+2)/3 Let n = k + 1. The lefthand side of (*) then gives us: 1×2 + 2×3
+ 3×4 + ... + (k)(k+1) + (k+1)((k+1)+1)
...which is the righthand side of (*). Then (*) works for all n > 1.
This one doesn't start at n = 1, and involves an inequality instead of an equation. (If you graph 4x and 2^{x} on the same axes, you'll see why we have to start at n = 5, instead of the customary n = 1.) Let n = 5. Then 4n = 4×5 = 20, and 2^{n} = 2^{5} = 32. Since 20 < 32, then (*) holds at n = 5. Assume, for n = k, that (*) holds; that is, assume that 4k < 2^{k} Let n = k + 1. The lefthand side of (*) gives us 4(k + 1) = 4k + 4, and, by assumption, [4k] + 4 < [2^{k}] + 4 Since k > 5, then 4 < 32 < 2^{k}. Then we get 2^{k} + 4 < 2^{k} + 2^{k} = 2×2^{k} = 2^{1}×2^{k} = 2^{k+1} Then 4(k+1) < 2^{k+1}, and (*) holds for n = k + 1. Then (*) holds for all n > 5.
Let n = 1. Then the expression 8^{n} – 3^{n} evaluates to 8^{1} – 3^{1} = 8 – 3 = 5, which is clearly divisible by 5. Assume, for n = k, that (*) holds; that is, that 8^{k} – 3^{k} is divisible by 5. Let n = k + 1. Then: 8^{k+1} – 3^{k+1} = 8^{k+1} – 3×8^{k} + 3×8^{k} – 3^{k+1} = 8^{k}(8 – 3) + 3(8^{k} – 3^{k}) = 8^{k}(5) + 3(8^{k} – 3^{k}) The first term in 8^{k}(5) + 3(8^{k} – 3^{k}) has 5 as a factor (explicitly), and the second term is divisible by 5 (by assumption). Since we can factor a 5 out of both terms, then the entire expression, 8^{k}(5) + 3(8^{k} – 3^{k}) = 8^{k+1} – 3^{k+1}, must be divisible by 5. Then (*) holds for n = k + 1, and thus for all n > 1. << Previous Top  1  2  3  Return to Index



Copyright © 20002012 Elizabeth Stapel  About  Terms of Use 




