# Prove using induction that the $(2^{i})^{th}$ partial sum is less than $i + 1$ for $i \ge 1$

I have been working on the following proof for the last two hours and can't seem to solve it. I've tried finding an "intermediate" condition and a few other things but I can't seem to wrap my head around this. I'd be grateful if someone could show me how to solve this or point me in the right direction. I am new to induction and proofs so I find this problem challenging. Thank you.

Let $$S_{k}=1 + \frac{1}{2} + \frac{1}{3} + ...+ \frac{1}{k}$$ be the $k$th partial sum. Prove, using induction, that $$S_{2^i}<i+1$$ for all $i \ge 1$.

• Write out an expression for $S_{2^{i+1}}-S_{2^i}$. What is the largest term? How many terms are there? – David Sep 12 '18 at 1:21

Base case $(i=1)$ is obvious. Assume the following is true $$S_{2^{i}} = \sum\limits_{k=1}^{2^i} \frac{1}{k} < i + 1$$ Notice that $$S_{2^{i+1}} = \sum\limits_{k=1}^{2^{i+1}} \frac{1}{k} = \sum\limits_{k=1}^{2^{i}} \frac{1}{k} + \sum\limits_{k=2^{i}+1}^{2^{i+1}} \frac{1}{k} = \underbrace{\sum\limits_{k=1}^{2^{i}} \frac{1}{k}}_{< i + 1} + \sum\limits_{k=2^{i}+1}^{2^{i}+2^i} \frac{1}{k}$$ The sum $$\sum\limits_{k=2^{i}+1}^{2^{i}+2^i} \frac{1}{k} = \frac{1}{2^{i} + 1} + \ldots + \frac{1}{2^i + 2^i} < \underbrace{\frac{1}{2^{i} + 1} + \ldots + \frac{1}{2^{i} + 1}}_{2^i \text{ times}} = \frac{2^i}{2^i + 1} < 1$$ So $$S_{2^{i+1}}<i+1 +1 = i+2$$

• Thank you, could you explain the right side of the condition? – imp3ll3d Sep 12 '18 at 18:20
• welcome, which right side ? – Ahmad Bazzi Sep 12 '18 at 18:20
• The right side that is underlined by “2^i times” – imp3ll3d Sep 12 '18 at 20:17
• Yeah so each term $\frac{1}{2^i + 1} < \frac{1}{2^i + 1}$, $\frac{1}{2^i + 2} < \frac{1}{2^i + 1}$ ... $\frac{1}{2^i + 2^i} < \frac{1}{2^i + 1}$ So all your terms (which are in total $2^i$) are less than the same number $\frac{1}{2^i + 1}$. Adding them up, the total sum should be less than $\frac{1}{2^i + 1}\times 2^i$ – Ahmad Bazzi Sep 12 '18 at 20:24