Prove by induction that $\sum_{i=1}^{2^n} \frac{1}{i} \ge 1+\frac{n}{2}, \forall n \in \mathbb N$

Question

As the title says I need to prove the following by induction: $$\sum_{i=1}^{2^n} \frac{1}{i} \ge 1+\frac{n}{2}, \forall n \in \mathbb N$$

When trying to prove that P(n+1) is true if P(n) is, then I get that:

$$\sum_{i=1}^{2^{n+1}} \frac{1}{i} = (\sum_{i=1}^{2^n} \frac{1}{i} ) +(\sum_{i=1}^{2^n} \frac{1}{2^n+i} ) \ge 1+\frac{n}{2} + (\sum_{i=1}^{2^n} \frac{1}{2^n+i} )$$ using the inductive hypothesis. And for P(n+1) to be true it would be sufficient to prove that $$1+\frac{n}{2} + (\sum_{i=1}^{2^n} \frac{1}{2^n+i} ) \ge 1+\frac{n+1}{2}$$ or rewriting $$\sum_{i=1}^{2^n} \frac{1}{2^n+i} \ge \frac{1}{2} $$ and here I'm a bit stuck

Thank you for your help!

When I try to prove that P(n+1) is true assuming P(n) is I get to the expression: $\sum_{i=1}^{2^n} \frac{1}{2^n +i} \ge \frac{1}{2}$ and here I'm having trouble trying to bound this sum. — Kat, Jul 07 '16 at 05:44
Each term in the sum is at least $\frac{1}{2^{n+1}}$, and there are $2^n$ of them... — carmichael561, Jul 07 '16 at 05:45
This might be helpful: https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Divergence — Joey Zou, Jul 07 '16 at 05:47
Thanks @Joey Zou this is very useful, but I still have to prove it using induction :s — Kat, Jul 07 '16 at 05:53
The inductive step is in there as well--it's just not explicitly stated. — Joey Zou, Jul 07 '16 at 05:54
Note that if $i\leq2^n$ then $\frac1{2^n+i}\geq\frac1{2^{n+1}}$. — stewbasic, Jul 07 '16 at 06:21
you're right @stewbasic and so: $\sum_{i=1}^{2^n} \frac{1}{2^n+i} \ge \sum_{i=1}^{2^n} \frac{1}{2^{n+1}}= \frac{2^n}{2^{n+1}}= \frac{1}{2} $ and we're done :D — Kat, Jul 07 '16 at 06:30

score 4 · Accepted Answer · answered Jul 07 '16 at 20:16

Providing this to make the inductive argument more explicit (some of the details were discussed in the comments): \begin{align} \sum_{i=1}^{2^{k+1}}\frac{1}{i}&= \sum_{i=1}^{2^k}\frac{1}{i}+\sum_{i=1}^{2^k}\frac{1}{2^k+i}\tag{rewrite the sum}\\[1em] &\geq 1+\frac{k}{2}+\sum_{i=1}^{2^k}\frac{1}{2^k+i}\tag{by inductive hypothesis}\\[1em] &\geq 1+\frac{k}{2}+\sum_{i=1}^{2^k}\frac{1}{2^{k+1}}\tag{since $i\leq2^n$}\\[1em] &= 1+\frac{k}{2}+2^k\left(\frac{1}{2^{k+1}}\right)\tag{simplify}\\[1em] &= 1+\frac{k}{2}+\frac{1}{2}\tag{simplify}\\[1em] &= 1+\frac{k+1}{2}\tag{simplify}. \end{align}

score 0 · Answer 2 · edited Apr 13 '17 at 12:21

0

See Inequality of finite harmonic series

Also proving $\sum_{i=1}^{2^n} \frac{1}{i} \ge 1+\frac{n}{2}, \forall n \in \mathbb N$ clear shows that $1+\frac{n}{2} + (\sum_{i=1}^{2^n} \frac{1}{2^n+i} ) \ge 1+\frac{n+1}{2}$ is true since adding $1$ to the LHS and $\frac{1}{2}$ to the RHS holds the inequality.

edited Apr 13 '17 at 12:21

Community

1

answered Jul 07 '16 at 12:14

user5486241

1

Prove by induction that $\sum_{i=1}^{2^n} \frac{1}{i} \ge 1+\frac{n}{2}, \forall n \in \mathbb N$

2 Answers2

Linked