1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction Proof

  1. May 1, 2013 #1
    To prove: (1 + 2 + 4 + . . . + [itex]2^{n}[/itex]) + 1 = [itex]2^{n+1}[/itex] , ∀n ≥ 0 .
    Basis Step n = 0: LEFT HAND SIDE: ([itex]2^{0}[/itex])+ 1 = 1 + 1 = 2 RIGHT HAND SIDE [itex]2^{0}[/itex] + 1 = 2
    Inductive Step: Assume (1 + 2 + 4 + . . . + [itex]2^{k}[/itex]) + 1 = [itex]2^{k+1}[/itex]
    Then (1 + 2 + 4 + . . . + [itex]2^{k}[/itex] + [itex]2^{k+1}[/itex]) + 1 = [itex]2^{k+1}[/itex] + [itex]2^{k+1}[/itex] + 1 = [itex]2^{k+2}[/itex] + 1.

    Is this proof right? This is a proof given to one of the example problems in the book. To me it seems wrong. If it is right then can someone explain how the +1 came to be at the end ( [itex]2^{k+2}[/itex] + 1).




    Isn't the above proof should be like this?

    so (1 + 2 + 4 + . . . + [itex]2^{k}[/itex] + [itex]2^{k+1}[/itex]) + 1 = [itex]2^{k+1}[/itex] + [itex]2^{k+1}[/itex] = [itex]2^{k+2}[/itex]

    Because (1 + 2 + 4 + . . . + [itex]2^{k}[/itex] + [itex]2^{k+1}[/itex]) + 1 can be rewritten as

    [(1 + 2 + 4 + . . . + [itex]2^{k}[/itex]) + 1] + [itex]2^{k+1}[/itex] by commutative property of addition.


    From the inductive step we assumed that (1 + 2 + 4 + . . . + [itex]2^{k}[/itex]) + 1 = [itex]2^{k+1}[/itex]

    [(1 + 2 + 4 + . . . + [itex]2^{k}[/itex]) + 1] + [itex]2^{k+1}[/itex] = [itex]2^{k+1}[/itex] + [itex]2^{k+1}[/itex] = [itex]2^{k+2}[/itex]
     
    Last edited: May 1, 2013
  2. jcsd
  3. May 1, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Indeed. The second version is good, the first has some wrong "+1".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Induction Proof
  1. Proof by induction (Replies: 6)

  2. Proof by induction (Replies: 8)

  3. Proof by induction (Replies: 0)

  4. Proof by Induction (Replies: 9)

  5. Induction Proof (Replies: 5)

Loading...