Proof by induction $\sum_{k=1}^{2^n} \frac1k \ge 1 + \frac{n}2 $

Question

Show that for all $n \in N , n \ge 1$ :

$\sum_{k=1}^{2^n} \frac1k \ge 1 + \frac{n}2 $

Here is what I got:

I. $A(1)$: $\sum_{k=1}^{2} \frac1k = 1.5 \ge 1.5 \;\; \implies A(1) \text{ is correct} $

II. $A(n)$ is correct: $\sum_{k=1}^{2^n} \frac1k \ge 1 + \frac{n}2 $

III. Is $A(n+1)$ correct? $\sum_{k=1}^{2^n+1} \frac1k \ge 1 + \frac{n+1}2 $

IV. Now I need the proof but I don't get the solution for it. Trying for hours - so hope someone can give me an answer with a reasonable explanation. Thank you very much!

Answer 1

Hint: It is sufficient to show that \begin{align*} \sum_{k = 2^n + 1}^{2^{n + 1}} \frac{1}{k} \geq \frac{1}{2}. \end{align*} Note that each summand is not less than $\frac{1}{2^{n + 1}}$ and how many summands are there?

Answer 2

Base case:

Let $n=1$. Then $\sum_{k=1}^{2^1} \frac{1}{k} \geq 1 + \frac{1}{2}$ by evaluation / inspection.

Induction step (examining the $n+1$ case against the $n$ case):

$(\sum_{k=1}^{2^{n+1}} \frac{1}{k}) - (\sum_{k=1}^{2^n} \frac{1}{k}) = \sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k}$

$(1+\frac{n+1}{2}) - (1+\frac{n}{2}) = \frac{1}{2}$

We only need to prove that $(\sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k}) \geq \frac{1}{2}$.

Note that there are $2^n$ terms in the lefthand summation, where all values of $\frac{1}{k}$ are $\geq \frac{1}{2^{n+1}}$.

Therefore $(\sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k}) \geq (2^n)(\frac{1}{2^{n+1}}) \geq \frac{1}{2}$.

Answer 3

Non-inductive justification for future viewers: We know from calculus that $H_n > \ln n$ for $n\geq1$ (where $H_n$ is the $n$th harmonic number). Thus, this is trying to prove that $H_{2^n} \geq 1 + \frac{n}{2}$.

Applying our inequality: $H_{2^n} \geq \ln(2^n) = n\ln(2)$. Now, $n\ln(2)\geq1+\frac n 2$ for $n\geq\frac{2}{2\ln 2 - 1}\approx 5.17$. So, this is justification enough for $n\geq 6$. The cases $n=0,\ldots,5$ may be exhaustively checked.

Why would this approach ever be useful? Knowing that you can often "replace" $H_n$ with $\ln n$ is a nice trick for quickly determining if a statement is true or false for the long-run behavior of the inequality. For instance, if the problem started "prove or disprove" instead of "prove." Also, in some fields, we primarily care about what happens when $n$ is large (asymptotic behavior); that is, we wouldn't care that this approach doesn't prove the result for small values of $n$.