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