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...