TITLE: 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 [5 upvotes]: 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

REPLY [1 votes]: 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\}.$
{"set_name": "stack_exchange", "score": 5, "question_id": 1082307}