How to proof that $\sum_{i=1}^{2^n} 1/i \ge 1+n/2$

Question

I had troubles trying to prove that for every $n\ge1$ $$\sum_{i=1}^{2^n}\frac1i\ge 1+\frac n2$$

Can you give me a hint about the induction proof or show me in detail how can I prove it? I would appreaciate any help. Thanks!

Answer 1

Or without any explicit induction: the sum is $$1+\Bigl(\frac12\Bigr)+\Bigl(\frac13+\frac14\Bigr)+\Bigr(\frac15+\frac16+\frac17+\frac18\Bigr)+\cdots+\Bigl(\frac1{2^{n-1}+1}+\cdots+\frac1{2^n}\Bigr)$$ which is greater than $$1+\Bigl(\frac12\Bigr)+\Bigl(\frac14+\frac14\Bigr)+\Bigr(\frac18+\frac18+\frac18+\frac18\Bigr)+\cdots+\Bigl(\frac1{2^n}+\cdots+\frac1{2^n}\Bigr)\ .$$ Now (hint) think carefully about how many pairs of brackets there are, and how many terms there are inside each pair.

Answer 2

By induction and for the inductive step we have

$$\sum_{i=1}^{2^{n+1}}\frac1i=\sum_{i=1}^{2^{n}}\frac1i+\sum_{i=2^n+1}^{2^{n+1}}\frac1i\ge1+\frac n2+\underbrace{\sum_{i=2^n+1}^{2^{n+1}}\frac1{2^{n+1}}}_{=\frac12}$$

Answer 3

$$A=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+....+\frac{1}{2^n}=\\\frac{1}{1}\\+\frac{1}{2}\\+(\frac{1}{3}+\frac{1}{4})\\+(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8})\\+...\\+(\frac{1}{2^n+1}+\frac{1}{2^n+2}+...+\frac{1}{2^n+2^n})$$now see

$$\frac{1}{1}\\+\frac{1}{2}\\+(\frac{1}{3}+\frac{1}{4})>(\frac{1}{4}+\frac{1}{4})\\+(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8})>(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8})\\+...\\+(\frac{1}{2^n+1}+\frac{1}{2^n+2}+...+\frac{1}{2^n+2^n})>(\frac{1}{2^{n+1}}+\frac{1}{2^{n+1}}+....\frac{1}{2^{n+1}})$$so $$A>1+\frac{1}{2}+2\frac{1}{4}+4\frac{1}{8}+...\\A>1+(\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}....)\\A>1+\frac{n}{2}$$

Answer 4

$$\sum_{i=1}^{2^{k+1}}\frac{1}{i} = \sum_{i=1}^{2^{k}}\frac{1}{i}+\sum_{i=2^k+1}^{2^{k+1}}\frac{1}{i} \\ = \sum_{i=1}^{2^{k}}\frac{1}{i}+\left(\frac{1}{2^k+1}+\frac{1}{2^k+1} \ldots +\frac{1}{2^{k+1}-1}+ \frac{1}{2^{k+1}}\right) \\ \geq \sum_{i=1}^{2^{k}}\frac{1}{i}+\left(\frac{1}{2^{k+1}}+\frac{1}{2^{k+1}} \ldots +\frac{1}{2^{k+1}}+ \frac{1}{2^{k+1}}\right)$$ The "greater than or equal to" is true because you are making the denominators larger. Next, you know you are adding up $2^k$ quantities of $\frac{1}{2^{k+1}}$ since $2^{k+1}-2^{k} = 2^k(2-1) = 2^k$. Hence $$\sum_{i=1}^{2^{k}}\frac{1}{i}+\left(\frac{1}{2^{k+1}}+\frac{1}{2^{k+1}} \ldots +\frac{1}{2^{k+1}}+ \frac{1}{2^{k+1}}\right) = \sum_{i=1}^{2^{k}}\frac{1}{i}+2^k\left(\frac{1}{2^{k+1}}\right) \\ = \sum_{i=1}^{2^{k}}\frac{1}{i}+\frac{1}{2}$$ Now apply the induction hypothesis and do some algebra to get your result!