1. Not finding help here? Sign up for a free 30min 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: 1+2+2^2+2^3+ +2^n-1=2^n-1

  1. Sep 5, 2012 #1
    1. The problem statement, all variables and given/known data[/b]
    Use mathematical induction to prove the following statements are true for all integers n≥1
    1+2+2^2+2^3+...+2^n-1=2^n-1



    Attempt at a solution:


    For n=1

    1+2^(1-1)=2^1-1
    1=1
    ∴ it is true.


    Let Sn=Sk
    If it is true for k, it must also be true for k+1

    1+2+2^2+2^3+...+2^k+2^k+1-1=(2^k+1)-1

    This is the part I have a slight confusion at, I keep getting something left over and the sides don't equal each other :(
     
  2. jcsd
  3. Sep 5, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Use brackets: you have written
    1+2+2^2+2^3+...+2^n-1=2^n-1 , which is plainly impossible, because it would require that we have 1+2+2^2+2^3+... = 0 (in order to have 2^n-1=2^n-1 on both sides). If you mean 2^(n-1), then that is what you need to say.

    RGV
     
  4. Sep 6, 2012 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You want to prove that if, for some k, [itex]2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}= 2^k-1[/itex] then [itex]2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}+ 2^k= 2^{k+1}-1[/itex].
    (What you wrote, 1+ 2^1+ ...+ 2^n-1= 2^n-1 is, as Ray Vickson said, clearly impossible because you have "2^n- 1" on both sides but with additional positive terms on the left. Of course, you meant 2^(n-1) on the left and (2^n)- 1 on the right. Those are very different and you can't ask people to guess what you mean.)

    To go from k to k+1, obviously you are adding [itex]2^k[/itex] to the sum on the left so do it on the right:
    [tex]2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}+ 2^k= (2^k- 1)+ 2^k[/tex]

    What do you get when you combine those two "[itex]2^k[/itex]" terms on the right?
     
    Last edited: Sep 7, 2012
  5. Sep 6, 2012 #4
    I figured it out, thanks!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook