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$.
Base case $(i=1)$ is obvious. Assume the following is true \begin{equation} S_{2^{i}} = \sum\limits_{k=1}^{2^i} \frac{1}{k} < i + 1 \end{equation} Notice that \begin{equation} 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} \end{equation} The sum \begin{equation} \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 \end{equation} So \begin{equation} S_{2^{i+1}}<i+1 +1 = i+2 \end{equation}