Return to the Purplemath home page

 The Purplemath Forums
Helping students gain understanding
and self-confidence in algebra


powered by FreeFind

 

Return to the Lessons Index  | Do the Lessons in Order  |  Get "Purplemath on CD" for offline use  |  Print-friendly page



Induction Proofs: Worked examples (page 3 of 3)

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


  • (*)  For n > 1,  2 + 22 + 23 + 24 + ... + 2n = 2n+1 2

    Let n = 1. Then:

      2 + 22 + 23 + 24 + ... + 2n = 21 = 2

    ...and:

      2n+1 2 = 21+1 2 = 22 2 = 4 2 = 2

    So (*) works for n = 1.

    Assume, for n = k, that (*) holds; that is, that

         2 + 22 + 23 + 24 + ... + 2k = 2k+1 2

    Let n = k + 1.

      2 + 22 + 23 + 24 + ... + 2k + 2k+1
       
         = [2 + 22 + 23 + 24 + ... + 2k] + 2k+1

       
         = [2k+1 2] + 2k+1

           = 22k+1 2
       
           = 212k+1 2

           = 2k+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, 12 + 23 + 34 + ... + (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 12 = 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

      12 + 23 + 34 + ... + (k)(k+1) = (k)(k+1)(k+2)/3

    Let n = k + 1. The left-hand side of (*) then gives us:

      12 + 23 + 34 + ... + (k)(k+1) + (k+1)((k+1)+1)
           = [12 + 23 + 34 + ... + (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 < 2n.
  • This one doesn't start at n = 1, and involves an inequality instead of an equation. (If you graph 4x and 2x 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 = 45 = 20, and 2n = 25 = 32.

    Since 20 < 32, then (*) holds at n = 5.

    Assume, for n = k, that (*) holds; that is, assume that 4k < 2k

    Let n = k + 1.

      The left-hand side of (*) gives us 4(k + 1) = 4k + 4, and, by assumption,

           [4k] + 4 < [2k] + 4

      Since k > 5, then 4 < 32 < 2k. Then we get

           2k + 4 < 2k + 2k = 22k = 212k = 2k+1

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

    Then (*) holds for all n > 5.

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

    Let n = 1.

      Then the expression 8n 3n evaluates to 81 31 = 8 3 = 5, which is clearly divisible by 5.

    Assume, for n = k, that (*) holds; that is, that 8k 3k is divisible by 5.

    Let n = k + 1.

    Then:

      8k+1 3k+1 = 8k+1 38k + 38k 3k+1

           = 8k(8 3) + 3(8k 3k) = 8k(5) + 3(8k 3k)

    The first term in 8k(5) + 3(8k 3k) 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, 8k(5) + 3(8k 3k) = 8k+1 3k+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

Cite this article as:

Stapel, Elizabeth. "Induction Proofs: Worked Examples." Purplemath. Available from
    http://www.purplemath.com/modules/inductn3.htm. Accessed
 

 



Purplemath:
  Linking to this site
  Printing pages
  School licensing


Reviews of
Internet Sites:
   Free Help
   Practice
   Et Cetera

The "Homework
   Guidelines"

Study Skills Survey

Tutoring from Purplemath
Find a local math tutor


This lesson may be printed out for your personal use.

Content copyright protected by Copyscape website plagiarism search

  Copyright 2000-2012  Elizabeth Stapel   |   About   |   Terms of Use

 

 Feedback   |   Error?