Induction Proofs: Worked examples (page 3 of 3)

Sections: Introduction, Examples of where induction fails, Worked examples

• (*)  For n > 1,  2 + 2² + 2³ + 2⁴ + ... + 2ⁿ = 2ⁿ⁺¹ – 2

Let n = 1. Then:

2 + 2² + 2³ + 2⁴ + ... + 2ⁿ = 2¹ = 2

...and:

2ⁿ⁺¹ – 2 = 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⁴ + ... + 2^k = 2^k+1 – 2

Let n = k + 1.

2 + 2² + 2³ + 2⁴ + ... + 2^k + 2^k+1
     = [2 + 2² + 2³ + 2⁴ + ... + 2^k] + 2^k+1
     = [2^k+1 – 2] + 2^k+1
     = 2×2^k+1 – 2  
     = 2¹×2^k+1 – 2
     = 2^k+1+1 – 2  
     = 2^(k+1)+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 right-hand side of the formula in terms of k + 1.

• (*)  For n > 1, 1×2 + 2×3 + 3×4 + ... + (n)(n+1) = (n)(n+1)(n+2)/3

Let n = 1.   Copyright © Elizabeth Stapel 2000-2011 All Rights Reserved

Then the left-hand side of (*) is 1×2 = 2
and the right-hand side of (*) is (1)(2)(3)/3 = 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 left-hand side of (*) then gives us:

1×2 + 2×3 + 3×4 + ... + (k)(k+1) + (k+1)((k+1)+1)
     = [1×2 + 2×3 + 3×4 + ... + (k)(k+1)] + (k+1)((k+1)+1)
     = [(k)(k+1)(k+2)/3] + (k+1)((k+1)+1)
     = (k)(k+1)(k+2)/3 + (k+1)(k+2)
     = (k)(k+1)(k+2)/3 + 3(k+1)(k+2)/3
     = (k+3)(k+1)(k+2)/3
     = (k+1)(k+2)(k+3)/3
     = (k+1)((k+1)+1)((k+1)+2)/3

...which is the right-hand side of (*). Then (*) works for all n > 1.

• (*)  For n > 5, 4n < 2ⁿ.

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ⁿ = 2⁵ = 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 left-hand 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¹×2^k = 2^k+1

Then 4(k+1) < 2^k+1, and (*) holds for n = k + 1.

Then (*) holds for all n > 5.

• (*)  For all n > 1, 8ⁿ – 3ⁿ is divisible by 5.

Let n = 1.

Then the expression 8ⁿ – 3ⁿ evaluates to 8¹ – 3¹ = 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 © 2000-2012  Elizabeth Stapel   |   About   |   Terms of Use

Contact Us