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!

Proof by induction

  1. Aug 23, 2014 #1
    1. The problem statement, all variables and given/known data

    Prove this by induction

    n
    ∑(1/√n) > 2(√(n+1) -1)
    i=1


    3. The attempt at a solution

    I have tried for several hours, with no real progress. When i assume that it works for n=k, and then try to prove for n=k+1 i get 2(√(k+2)-1)... i don't know how to partition this expression... can someone point me in the right direction....
     
  2. jcsd
  3. Aug 23, 2014 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Are you absolutely required to use induction? If not, there is a quick proof using elementary calculus (specifically, definite integration).
     
  4. Aug 23, 2014 #3
    The task is part of the induction chapter in the textbook.
     
  5. Aug 23, 2014 #4
    Are you sure that the left-hand side of the inequality is...

    [itex] \sum_{k=1}^{n} \frac 1{\sqrt {n}}[/itex], rather than [itex] \sum_{k=1}^{n} \frac 1{\sqrt {k}}[/itex] ?
     
  6. Aug 23, 2014 #5
    woops!, i can correct it...
     
  7. Aug 23, 2014 #6
    m
    ∑(1/√n) > 2(√(n+1) -1)
    n=1
     
  8. Aug 23, 2014 #7
    Again, the problem for me lies in that i can't partition(divide in to a sum) the expression on the right...
     
  9. Aug 23, 2014 #8
    Um, what is m?
     
  10. Aug 23, 2014 #9
    So sorry, I'm not so good at the different placements for the different sum-limits/-startpoints. I first introduced "k" when i assumed that the inequality actually was valid, and then i set n=k+1 and tried to prove it...

    This should be right;
    n
    ∑(1/√i) > 2(√(n+1) -1)
    i=1
     
  11. Aug 23, 2014 #10
    forget m :)
     
  12. Aug 23, 2014 #11
    I think you meant to write...

    [itex] \sum_{n=1}^{m} \frac 1{\sqrt{n}} > \frac 2{\sqrt{m+1}} -1 [/itex].

    If this is the case, here's a way to start the inductive step:

    [itex]\sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = ( \sum_{n=1}^{m} \frac 1{\sqrt{n}}) + \frac 1{\sqrt{m+1}} [/itex]
     
  13. Aug 23, 2014 #12
    no, it is 2(√(n+1) -1) = 2√(n+1) -2
     
  14. Aug 23, 2014 #13
    Let me know if you'd like more hints, but I'm pretty sure you can finish the problem from here ;)
     
    Last edited by a moderator: Aug 24, 2014
  15. Aug 23, 2014 #14

    Oh... the right hand side is a product. Oops.

    That's ok. The steps in the proof won't change much.
     
  16. Aug 23, 2014 #15
    [itex]\sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = ( \sum_{n=1}^{m} \frac 1{\sqrt{n}}) + \frac 1{\sqrt{m+1}} [/itex]
     
  17. Aug 23, 2014 #16
    Starting from the Left-hand side of the inequality you wish to prove (P(m+1)),

    [itex] \sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = \sum_{n=1}^{m} \frac 1{\sqrt{n}} + \frac 1{\sqrt{m+1}} [/itex].

    Recall that you assumed P(m) to be true, that is

    [itex] \sum_{n=1}^{m} \frac 1{\sqrt{n}} > 2 \cdot ((\sqrt{m+1}) -1) [/itex],

    So recognizing this, you have...

    [itex] \sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = \sum_{n=1}^{m} \frac 1{\sqrt{n}} + \frac 1{\sqrt{m+1}} > 2 \cdot ((\sqrt{m+1}) -1) + \frac 1{\sqrt{m+1}} [/itex].
     
  18. Aug 23, 2014 #17
    If i contract the right side i get: (2m +3 -2√(m+1))/√(m+1)

    Don't see how this is gonna help.. :)
     
  19. Aug 23, 2014 #18
    dont i have to show that (2m +3 -2√(m+1))/√(m+1) can be written as 2(√(m+2) -1) to prove it...?

    or maybe not since its an inequality...?
     
    Last edited: Aug 23, 2014
  20. Aug 23, 2014 #19
    If you plug in some numbers you'll see...

    [itex]2 \cdot (\sqrt{m+1} - 1) + \frac 1{\sqrt{m+1}} \neq 2 \cdot (\sqrt {(m+1)+1} - 1) [/itex].

    You're next step should be to show that...

    [itex]2 \cdot (\sqrt{m+1} - 1) + \frac 1{\sqrt{m+1}} > 2 \cdot (\sqrt {(m+1)+1} - 1) [/itex].
     
  21. Aug 23, 2014 #20

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

     
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: Proof by induction
  1. Inductive proof (Replies: 9)

  2. Proof by induction (Replies: 2)

  3. Proof by induction (Replies: 9)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...