1
$\begingroup$

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

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

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}

$\endgroup$
  • $\begingroup$ Thank you, could you explain the right side of the condition? $\endgroup$ – imp3ll3d Sep 12 '18 at 18:20
  • $\begingroup$ welcome, which right side ? $\endgroup$ – Ahmad Bazzi Sep 12 '18 at 18:20
  • $\begingroup$ The right side that is underlined by “2^i times” $\endgroup$ – imp3ll3d Sep 12 '18 at 20:17
  • $\begingroup$ 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$ $\endgroup$ – Ahmad Bazzi Sep 12 '18 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.