Prove inequality for a sum to $2^{n+1}$

Question

Problem:I realize I made a mistake on one of the last questions I posted.Here is the problem:

Prove for all $n \in \mathbb{N}$

$\sum\limits_{k=1}^{2^{n+1}} \frac{1}{k} > \frac{n}{2}$

Attempt: I'm having trouble recognizing the pattern for the general term of the inequality, can someone help me?

trying cases

for $n=1$ then $\sum\limits_{k=1}^{2^{1+1}} \frac{1}{k}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}>\frac{1}{4}+\frac{1}{4}$

for $n=2$ then $\sum\limits_{k=1}^{2^{2+1}}\frac {1}{k}=\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}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}$

Can someone tell me if this is the correct pattern to use in the proof?Would this be a proof by induction or a direct proof?

Direct proof attempt

$\sum\limits_{k=1}^{2^{n+1}} \frac{1}{k}>\frac{n2^{n}}{2^{n+1}}=\frac{n}{2}$

Answer 1

Note that\begin{align}\left(\sum_{k=1}^{2^{n+2}}\frac1k\right)-\left(\sum_{k=1}^{2^{n+1}}\frac1k\right)&=\sum_{k=2^{n+1}+1}^{2^{n+2}}\frac1k\\&>\overbrace{\frac1{2^{n+2}}+\frac1{2^{n+2}}+\cdots+\frac1{2^{n+2}}}^{2^{n+1}\text{ times}}\\&=\frac{2^{n+1}}{2^{n+2}}\\&=\frac12.\end{align}Can you take it from here?

Answer 2

Induction will work. Although, the observation made by José shows why induction works.

Suppose that $n\in\mathbb N$. For the base case when $n=1$ we have

$$\sum\limits_{k=1}^{2^2} \frac{1}{k}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}>\frac{1}{2}$$

then for the induction hypothesis we will assume that

$$\sum\limits_{k=1}^{2^{n+1}} \frac{1}{k} > \frac{n}{2}$$

for all $k\in\mathbb N$. So, for the induction step we need to show that

$$\sum\limits_{k=1}^{2^{n+2}} \frac{1}{k} > \frac{n+1}{2}$$

Starting from the LHS

\begin{align}\sum\limits_{k=1}^{2^{n+2}} \frac{1}{k}&=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots + \frac{1}{2^{n+1}}+\frac{1}{2^{n+1}+1}+\dots+\frac{1}{2^{n+2}}\\&= \sum\limits_{k=1}^{2^{n+1}} \frac{1}{k}+\frac{1}{2^{n+1}+1}+\dots+\frac{1}{2^{n+2}} \\& >\frac{n}{2}+\frac{1}{2^{n+1}+1}+\dots+\frac{1}{2^{n+2}}\\&>\frac{n}{2}+\overbrace{\frac1{2^{n+2}}+\frac1{2^{n+2}}+\cdots+\frac1{2^{n+2}}}^{2^{n+1}\text{ times}}\\&=\frac{n}{2}+\frac{2^{n+1}}{2^{n+2}}\\&=\frac{n}{2} + \frac{1}{2}\\&=\frac{n+1}{2} \end{align}

Answer 3

$\int_k^{k+1} \frac 1 t dt <\frac 1 k$. Summing over $k$ we see that the given sum exceeds $\int_1^{2^{n+1}+1} \frac 1 t dt=\ln (2^{n+1}+1) >ln (2^{n+1})=(n+1)ln 2>nln 2 >\frac n 2$ since $e <4$.