Sunday 29 November 2015

discrete mathematics - Proof by induction of summation inequality: $1 + 1/2+ 1/3+ 1/4+1/5+⋯+ 1/2^n leq n + 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 $\in$ N, we have $$1 + \frac{1}{2}+ \frac{1}{3}+ \frac{1}{4}+\frac{1}{5} +⋯+ \frac{1}{2^n} ≤ n + 1$$



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



1) Let P(n) be $$\sum_{i=0}^{2^n} \frac{1}{i} $$



2) Base case: $n = 1$



$$\sum_{i=1}^{2^n} \frac{1}{i} = \frac{1}{1}+ \frac{1}{2} = \frac{3}{2}, \frac{3}{2} ≤ 2 $$




So P(1) is true.



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



4) Inductive step:
We want to prove that P(k + 1) is true or, $$\sum_{i=1}^{2^{k+1}} \frac{1}{i} ≤ k + 2$$



By inductive hypothesis,




$$\sum_{i=1}^{2^{k+1}} \frac{1}{i} = \sum_{i=1}^{2^k} \frac{1}{i} + \sum_{i=2^k+1}^{2^{k+1}}\frac{1}{i} ≤ k + 1 + \sum_{i=2^k+1}^{2^{k+1}}\frac{1}{i}$$



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 $\frac{a}{b + c} < \frac{a}{b}$ is relevant, but I don't know how to get there from here.

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...