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!

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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?