Sunday, 29 November 2015

discrete mathematics - Proof by induction of summation inequality: 1+1/2+1/3+1/4+1/5++1/2nleqn+1

I have been working on this problem for literally hours, and I can't come up with anything. Please help. I feel like I am about to go insane.




For all n N, we have 1+12+13+14+15++12nn+1



I know that I am supposed to use a proof by induction. Here is progress so far:



1) Let P(n) be 2ni=01i



2) Base case: n=1



2ni=11i=11+12=32,322




So P(1) is true.



3) Inductive hypothesis:
Suppose that P(k) is true for an arbitrary integer k 1



4) Inductive step:
We want to prove that P(k + 1) is true or, 2k+1i=11ik+2



By inductive hypothesis,




2k+1i=11i=2ki=11i+2k+1i=2k+11ik+1+2k+1i=2k+11i



I know that I'm supposed to split the expression into two summations, but now I am completely stuck and don't know what to do from here. I got one hint that the fact ab+c<ab is relevant, but I don't know how to get there from here.

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}...