Saturday, 25 January 2014

inequality - Proving sumnj=1frac1sqrtj>sqrtn with induction



Problem: Prove with induction that nj=11j>n for every natural number n2.



Attempt at proof: Basic step: For n=2 we have 1+12>2 which is correct.



Induction step: Suppose the assertion holds for some natural number n, with n>2. Then we now want to prove that it also holds for n+1, i.e. that n+1j=11j>n+1

Now we have that n+1j=11j=nj=11j+1n+1>n+1n+1 or nj=11j+1n+1>nn+1+1n+1



Now I'm stuck, and I don't know how to get n+1 on the right hand side. Help would be appreciated.


Answer



As Daniel Fischer points out in the comments, since you have
n+1j=11j>n+1n+1
it is enough to show
n+1n+1n+1
or equivalently 1n+1n+1n. A way to show this final inequality is to recall the identity (ab)(a+b)=a2b2 and multiply both sides by n+1+n, i.e. to use the identity with a=n+1 and b=n: what happens to the LHS? To the RHS?


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...