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$.

Ahmad Bazzi
  • 12,076
imp3ll3d
  • 13
  • 2
    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 01:21

1 Answers1

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}

Ahmad Bazzi
  • 12,076
  • 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