Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove by induction that sum(1/2^i)<1 i =1 to n

  1. Oct 8, 2008 #1
    1. The problem statement, all variables and given/known data
    prove by mathematical induction that it is true:


    [tex]\frac{1}{2}[/tex]+[tex]\frac{1}{2^{2}}[/tex]+[tex]\frac{1}{2^{3}}[/tex]+....+[tex]\frac{1}{2^{n}}[/tex] < 1
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Oct 9, 2008 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Well, where's your attempt?
     
  4. Oct 9, 2008 #3
    Is this prove by induction: like first proving that the statement is true for n=1

    then prove its true for n+1?
     
  5. Oct 9, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Change the induction hypothesis to sum(i=1,n)(1/2^i)=1-1/2^n. That will prove what you want and will make your life a lot easier.
     
  6. Oct 9, 2008 #5

    Mark44

    Staff: Mentor

    Not quite. First, assume that the statement is true for n = k. Then if the statement is true for n = k, show that it must also be true for n = k + 1.

    In the context of the OP's problem,
    a) assume the statement is true for n = k. IOW, that
    [tex]\frac{1}{2}[/tex] + [tex]\frac{1}{{2}^2}[/tex] + .... + [tex]\frac{1}{{2}^k}[/tex] < 1

    b) Now prove that
    [tex]\frac{1}{2}[/tex] + [tex]\frac{1}{{2}^2}[/tex] + .... + [tex]\frac{1}{{2}^k}[/tex] + [tex]\frac{1}{{2}^k+1}[/tex]< 1

    It's not immediately obvious what you need to do to carry out the proof, unless you can come up with a different expression for the sum of the k terms, the expression on the left in a).


    As a hint, look at the sequence of sums for
    1/2
    1/2 + 1/4
    1/2 + 1/4 + 1/8

    and so on, and see if you can discover a pattern that you can extend to the sum with k terms in it. If you can do that, you can prove the inequality marked (*).
    Mark
     
  7. Oct 9, 2008 #6

    Mark44

    Staff: Mentor

    Not quite. First, assume that the statement is true for n = k. Then if the statement is true for n = k, show that it must also be true for n = k + 1.

    In the context of the OP's problem,
    a) assume the statement is true for n = k. IOW, that
    [tex]\frac{1}{2}[/tex] + [tex]\frac{1}{{2}^2}[/tex] + .... + [tex]\frac{1}{{2}^k}[/tex] < 1

    b) Now prove that
    [tex]\frac{1}{2}[/tex] + [tex]\frac{1}{{2}^2}[/tex] + .... + [tex]\frac{1}{{2}^k}[/tex] + [tex]\frac{1}{{2}^k+1}[/tex]< 1

    It's not immediately obvious what you need to do to carry out the proof, unless you can come up with a different expression for the sum of the k terms, the expression on the left in a).


    As a hint, look at the sequence of sums for
    1/2
    1/2 + 1/4
    1/2 + 1/4 + 1/8

    and so on, and see if you can discover a pattern that you can extend to the sum with k terms in it. If you can do that, you can prove the inequality in b).
    Mark
     
  8. Oct 9, 2008 #7
    But isn't he supposed to prove by induction? And that's the general definition of induction that I know of. But I do see where you're coming from though.
     
  9. Oct 9, 2008 #8

    Mark44

    Staff: Mentor

    What I have described in a) and b) is how you do a proof by induction. The part at the end was just some advice on proving the statement in b).
    Mark
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook