Proof by Induction

  • #1

Homework Statement



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.

Homework Equations



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.
 

Answers and Replies

  • #2
rock.freak667
Homework Helper
6,223
31
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.
 
  • #3
35,213
7,018
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.
 
  • #4
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.

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?
 
  • #5
35,213
7,018
You know that xk + 1 = xk + 1/xk. Your induction hypothesis gives you something you can replace xk with.
 

Related Threads on Proof by Induction

  • Last Post
Replies
6
Views
883
  • Last Post
Replies
4
Views
887
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
961
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
944
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
779
Top