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.
For $n \ge 2$, we have $$\frac{1}{n} \le \int_{n-1}^{n} \frac{1}{x}\,dx$$ So, $$\sum_{i=1}^{2^{k}}{\frac{1}{i}} \leq 1+\int_{1}^{2^k} \frac{1}{x}\,dx=1+k \log2 \le 1+k$$ Another proof:as your progress $$\sum_{i=2^k+1}^{2^{k+1}}\frac{1}{i}=\frac{1}{1+2^k}+\frac{1}{2+2^k}+...+\frac{1}{2^k+2^k}\le\frac{2^k}{1+2^k}\le1$$