Showing that $\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$ for all $n\geq 1$

Question

Show that $$\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$$ for all $n\geq 1$

I need this in order to complete my proof that $1 + \frac{n}{2} \leq H_{2^n}$, but I don't have any ideas.

I know it is true at least for the first $20$ cases, but I can't prove it. Any suggestions?

Answer 1

Hint for every $1\leq k\leq 2^n$ $$\frac{1}{2^n+k}\geq \frac{1}{2^{n+1}} $$

do every term in your sum is greater then $\frac{1}{2^{n+1}} $ and in the sum there is $2^n$ terms so your sum is greater then $2^n$ times $\frac{1}{2^{n+1}} $ $\cdots$

Answer 2

Hint: how many summands are there? What is the smallest summand?

Answer 3

$$\sum_{k=1}^{2^n} \frac{1}{2^n+k} \geq \sum_{k=1}^{2^n} \frac{1}{2^n+2^n} =\sum_{k=1}^{2^n} \frac{1}{2^{n+1}}$$ the rightmost sum equals $\frac{1}{2}$, in fact we have a strict inequality.

Answer 4

First, see that this sum has $2^n$ terms. Then, $\forall k\in \{1,\dots,2^n\}$, you have $\frac{1}{2^n+k}\geq\frac{1}{2^{n+1}}$.

Summing these inequalities, you get the result.

Answer 5

This answer addresses this part (really the main part) of your question:

I need this in order to complete my proof that $1 + \frac{n}{2} \leq H_{2^n}$, but don't have any ideas.

Consider the following exercise, the solution of which answers your question directly (skip ahead to the "induction proof" part of this answer for a proof of your claim without the fluff):

Exercise: Prove by induction that for any $n\in\mathbb{Z}^+$, there exists an $m$ so that $H_m\geq n$. Conclude that as $m\to\infty$, $H_m\to\infty$.

Proof. In order to see that the harmonic series diverges, it is enough to show that, for any $n\in\mathbb{Z}^+$, there exists an $m$ such that $H_m\geq n$. To see this, partition the series into groups, with each group totaling at least $1/2$ as follows: $$ 1+\frac{1}{2}+\underbrace{\frac{1}{3}+\frac{1}{4}}_{\geq 1/2}+\underbrace{\frac{1}{5}+\cdots+\frac{1}{8}}_{\geq 1/2}+\underbrace{\frac{1}{9}+\cdots+\frac{1}{16}}_{\geq 1/2}+\cdots. $$ Now, the number of groups may be made as large as necessary. More formally, for each $k\geq 1$, $$ \sum_{i=2^k+1}^{2^{k+1}}\frac{1}{i}\geq\sum_{i=2^k+1}^{2^{k+1}}\frac{1}{2^{k+1}}=(2^{k+1}-2^k)\frac{1}{2^{k+1}}=\frac{1}{2}.\tag{1} $$ Claim: For each $p\geq 0$, $$ S(p) : H_{2^p}\geq 1+\frac{p}{2}. $$ By proving this claim, which is your overall goal anyway, we will have proved what is desired in the exercise above, since for every $n$, choose $p$ so large that $1+\frac{p}{2}\geq n$, and then use $m=2^p$.

Below is an inductive proof of the claim above:

---

Induction Proof

Claim: For each $p\geq 0$, $S(p) : H_{2^p}\geq 1+\frac{p}{2}$.

Base step: When $p=0$, $H_1\geq 1$, and this confirms that $S(0)$ is true.

Induction step: Fix some $\ell\geq0$, and assume that $$ S(\ell) : H_{2^\ell}\geq 1+\frac{\ell}{2} $$ is true. To be shown is that $S(\ell+1)$ follows where $$ S(\ell+1) : H_{2^{\ell+1}}\geq 1+\frac{\ell+1}{2}. $$ Beginning with the left-hand side of $S(\ell+1)$, \begin{align} H_{2^{\ell+1}} &= H_{2^\ell}+\sum_{i=2^\ell+1}^{2^{\ell+1}}\frac{1}{i}\\[1em] &\geq H_{2^\ell}+\frac{1}{2}\tag{by $(1)$}\\[1em] &\geq 1+\frac{\ell}{2}+\frac{1}{2}\tag{by $S(\ell)$}\\[1em] &= 1+\frac{\ell+1}{2}, \end{align} we end up at the right-hand side of $S(\ell+1)$, completing the inductive step.

By mathematical induction, for every $p\geq 0$, the statement $S(p)$ is true. $\Box$

Thus, for every $n$, there exists an $m$ so that $H_m\geq n$. That is, $\lim_{m\to\infty}H_m=\infty$.

---

Note: If desired, you may also prove that, for $n\geq 1$, $H_{2^n}\leq 1+n$, an observation that allows you to conclude that (in light of the claim we just proved) $$ 1+\frac{n}{2}\leq H_{2^n}\leq 1+n. $$