1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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. Sep 10, 2009 #1
    1. The problem statement, all variables and given/known data

    Show the sequence {X_n} defined by X_1 = 1, X_n+1 = X_n + 1/X_n for n > 1 obeys the inequality X_n > sqrt(n) for all n >= 2.

    2. Relevant equations

    3. The attempt at a solution

    For n = 2, 2 > sqrt(2) and for n = 3, 2.5 > sqrt(2.5). So it holds so far. What to do here after initial step for the inductive step is confusing me. I've never seen an induction proof with an inequality before today and the ones I've looked at online are not helpful at all.

    Any help is appreciated. Thank you.
  2. jcsd
  3. Sep 10, 2009 #2


    User Avatar
    Homework Helper

    Well what I do in induction questions with inequalities, I just try to make up the formula for xN+1 after assuming true for n=N.

    So I'd invert both sides and then go from there.
  4. Sep 10, 2009 #3


    Staff: Mentor

    You haven't said exactly what you have done for the induction hypothesis and induction step, so here's what's left to do.
    Assume that xk > [itex]\sqrt{k}[/itex] is true.
    Show that xk + 1 > [tex]\sqrt{k + 1}[/tex]. Be sure to use the given information that xk + 1 = xk + 1/xk.
  5. Sep 10, 2009 #4
    See, it's the recursive formula that is kind of tripping me up because I am not sure where to use it. Do I simply sub it in for Xk when trying to show xk + 1 > [tex]\sqrt{k + 1}[/tex] and then work from there?
  6. Sep 10, 2009 #5


    Staff: Mentor

    You know that xk + 1 = xk + 1/xk. Your induction hypothesis gives you something you can replace xk with.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook