Proving inequality $\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + ... + + \frac{1}{2^{n}-1} < n$

Question

Prove the inequality $\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + ... + + \frac{1}{2^{n}-1} < n$ where $n\in\mathbb{N}\backslash\{0,1\}$

My work

At first I tried to prove first half by induction

$\frac{n}2+\frac{1}2<1+\frac{1}2+\dots+\frac{1}{2^{n+1}-1}$

Which is $\displaystyle\frac{1}2+\sum_{k=0}^{2^n-1}\frac{1}k<\sum_{k=0}^{2^{n+1}-1}\frac{1}k$

And then I got this $\displaystyle\sum_{k=0}^{2^{n+1}-1}\frac{1}k-\sum_{k=0}^{2^n-1}\frac{1}k=\sum_{k=0}^{2n}\frac{1}{2^n+k}$

And now I see no way to go on $\displaystyle\sum_{k=0}^{2n}\frac{1}{2^n+k}>\frac{1}2$ where $(n>1,n\in\mathbb{N},h=\overline{0,2n})$

My math background is too low so I'm not able to prove this last inequality I've got, maybe someone knows how to?(maybe using limit's definition?) But I think there should be more simplicated solution, which I cannot find for almost 4 hours now. Thank you

Answer 1

By induction.

Basis: $1<1+\frac{1}{2}+\frac{1}{3}<2.$

Inductive step: Assume the statement holds for $n=k$. Then we show this implies the truthfulness of $$\frac{k+1}{2}<1+\frac{1}{2}+\ldots+\frac{1}{2^{k+1}-1}<k+1,$$ that is $$ \left\{ \begin{array}{c} \frac{k}{2}<1+\sum_{i=3}^{2^{k+1}-1}\frac{1}{i} \\ k>\sum_{i=2}^{2^{k+1}-1}\frac{1}{i} \end{array} \right. .$$

Hence, given our initial assumption, if we prove $$ \left\{ \begin{array}{c} \sum_{i=1}^{2^{k}-1}\frac{1}{i}<1+\sum_{i=3}^{2^{k+1}-1}\frac{1}{i} \\ \sum_{i=1}^{2^{k}-1}\frac{1}{i}>\sum_{i=2}^{2^{k+1}-1}\frac{1}{i} \end{array} \right. \leftrightarrow \left\{ \begin{array}{c} \frac{1}{2}<\sum_{i=2^k}^{2^{k+1}-1}\frac{1}{i} \ \ \ \ \ \ (1)\\ 1>\sum_{i=2^k}^{2^{k+1}-1}\frac{1}{i} \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2) \end{array} \right. $$ we are done. Since $\sum_{i=2^k}^{2^{k+1}-1}\frac{1}{i}$ obviously decreases as $k$ increases, $(2)$ holds for all $k\ge2$ as we can check that $$1>\sum_{i=4}^7\frac{1}{i}=\frac{319}{420}. $$

As for $(1)$, it is true because the sum approaches $\log 2>\frac{1}{2}$ from above. Indeed we have $$\lim_{k\to\infty}\sum_{i=2^k}^{2^{k+1}-1}\frac{1}{i}=\lim_{k\to\infty}\sum_{i=1}^{2^{k+1}-1}\frac{1}{i}-\lim_{k\to\infty}\sum_{i=1}^{2^{k}-1}\frac{1}{i}=\lim_{k\to\infty}\sum_{i=1}^{2^{k+1}}\frac{1}{i}-\lim_{k\to\infty}\sum_{i=1}^{2^{k}}\frac{1}{i}=\\\lim_{k\to\infty}(k+1)\log2-\lim_{k\to\infty}k\log2=\log2,$$ where we used $\displaystyle\lim_{n\to\infty}\frac{\sum_{i=1}^n\frac{1}{i}}{\log n}=1.$ Thus we conclude the statement holds for all $n\in\mathbb{N}\backslash\{0;1\}.$

Answer 2

Since $\frac{1}{n}\geq \log\left(1+\frac{1}{n}\right)$, it follows that: $$\sum_{n=1}^{2^N-1}\frac{1}{n}\geq\sum_{n=1}^{2^N-1}\left(\log(n+1)-\log(n)\right) = \log 2^N = N \log 2.$$ On the other hand, $\frac{1}{n}-\log\left(1+\frac{1}{n}\right)\leq\frac{1}{2n^2}$ gives: $$\sum_{n=1}^{2^N-1}\frac{1}{n}\leq N \log 2+\frac{1}{2}\sum_{n=1}^{+\infty}\frac{1}{n^2}= N\log 2+\frac{\pi^2}{12}.$$

Answer 3

To prove the first inequality, group them $$1+(\frac12)+(\frac13+\frac14)+(\frac15+\frac16+\frac17+\frac18)+...$$
so each group goes from one power of two to the next. Show that each group's sum is more than $1/2$.
To prove the second, group them $$1 + (\frac12+\frac13)+(\frac14+\frac15+\frac16+\frac17)+...$$
again, each group goes from one power of two to the next. Each group's sum is less than $1$.