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!

Prove 2^0+ +2^n=2^{n+1}-1

  1. Jul 6, 2014 #1
    [tex]2^0+2^1+2^2+...+2^n=2^{n+1}-1;n \ge 0[/tex]

    [tex]P(0)[/tex] [tex]2^0=2^{0+1}-1 \rightarrow 1=1[/tex]

    [tex]P(k) = 2^{k+1}-1[/tex]


    [tex]1+2+2^2+2^k+2^{k+1}=2^{k+1}-1+2^{k+1}[/tex]

    [tex]2^{k+2}-1 = 2^{k+1}-1+2^{k+1}[/tex]

    [tex] = 2^{k+1}(1+1)-1 [/tex]

    [tex] = 2^{k+1}(2)-1 [/tex]

    [tex] = 2^{k+1+1}-1 [/tex]

    [tex] = 2^{k+2}-1 [/tex]

    ??
     
  2. jcsd
  3. Jul 6, 2014 #2

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Your solution is fine, but your presentation is hard to follow. As you know, you need to prove that ##2^0=2^1-1## and then that if ##1+\cdots+2^{k}=2^{k+1}-1## then ##2^0+\cdots+2^{k+1}=2^{k+2}-1##. To prove the former, I would just write ##2^0=1=2^1-1##. The calculation that proves the latter is much easier to follow in this form:
    $$2^0+\cdots+2^{k+1}=(2^0+\cdots+2^k)+2^{k+1} =(2^{k+1}-1)+2^{k+1} =2\cdot 2^{k+1}-1=2^{k+2}-1.$$ Next time use the template. The moderators may delete your post if you don't.
     
    Last edited: Jul 6, 2014
  4. Jul 12, 2014 #3
    You can also prove this without induction.

    Proposition: ##x^n - 1 = (x - 1)(1 + x + ... + x^{n-1})##.

    The above is easily shown by distributing the entire ##(1 + x + ... + x^{n-1})## on the right hand side to yield: ##(x + x^2 + .... + x^n) - (1 + x + ... + x^{n-1})##.

    Now if you plug in 2 for x, you get what you were looking to prove.
     
  5. Jul 12, 2014 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Or, alternatively$$
    s = 2^0+2^1+...+2^n$$ $$
    2s=2^1+2^2+...+2^n+2^{n+1}$$Subtract the first from the second:$$
    s=-2^0+2^{n+1} =2^{n+1}-1$$It's just the old geometric series trick.
     
  6. Jul 12, 2014 #5
    I think what you are struggling with is a way of thinking about the algebra logic.

    You assume P(k) in the induction. (Make certain to state this as an assumption.) You want to show P(k+1) holds by starting with the left-hand side and using the P(k) assumption. I'm writing ??? to indicate that I stop and think, what type of relation can I make from the known information.

    ##2^0 + 2^1 + \cdots + 2^k + 2^{k+1} = ???## Given LHS.
    ##= (2^0 + 2^1 + \cdots + 2^k) + 2^{k+1} = ???## Recognize P(k)
    ##= (2^{k+1} -1) + 2^{k+1} = ???## Substitute P(k).
    ##=2(2^{k+1}) -1 = ??? ## Regrouping.
    ##=2^{(k+1)+1} - 1## Determined RHS.

    Your solution has a lot of extraneous information, so I think you are trying to "balance" an equation. You really just have to set up a series of relations.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove 2^0+ +2^n=2^{n+1}-1
  1. Prove 2^(-n) converges (Replies: 7)

  2. Prove n^3 <= 2^n (Replies: 9)

  3. 2^n < (n+2)! (Replies: 3)

Loading...