Use the mathematical Induction show that $H_{2^n}\le n+1$

Question

Use the mathematical Induction show that $H_{2^n}\le n+1$

here $H$ is harmonic numbers ie. $H_n=1+\frac{1}{2}+\frac{1}{3}+.....\frac{1}{2^n}$

my idea

so for $n=0$ L.H.S=R.H.S

Suppose this is true for $n$

we prove for $n+1$

So $H_{2^{n+1}}=1+\frac{1}{2}+\frac{1}{3}+...\frac{1}{2^n}+\frac{1}{2^n+1}+....\frac{1}{2^{n+1}}\\ =H_{2^n}+\frac{1}{2^n+1}+.......\frac{1}{2^{n+1}}$

How to continue from here

Answer 1

We have already assumed that $$H_n=1+\frac{1}{2}+\frac{1}{3}+.....\frac{1}{2^n}\le n+1$$

We need to prove that:

$$H_{n+1}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{2^n}+\frac{1}{2^n+1}+...+\frac{1}{2^n+2^n}\le n+2$$

This is true because $$\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}\text{(there are $2^n$ numbers)}$$

$$\Rightarrow \frac{1}{2^n+1}+\frac{1}{2^n+2}+...+\frac{1}{2^n+2^n}<\frac{2^n}{2^n+1}<1$$

Combined with: $$H_n=1+\frac{1}{2}+\frac{1}{3}+.....\frac{1}{2^n}\le n+1$$ to finish the proof.

Answer 2

Rephrasing a bit:

1) $n=0$, ok.

2) Hypothesis: $H_{2^n} \le n+1$.

3)Step: $n+1$:

$H_{2^{n+1}} =$

$H_{2^n} + \dfrac{1}{2^n +1}+.....\dfrac{1}{2^{n+1}} =$

$H_{2^n} + \dfrac{1}{2^n+1}+...\dfrac{1}{2^n+ 2^n} \lt$

$H_{2^n} + 2^n \dfrac{1}{2^n+1} \lt $

$H_{2^n} +1 \lt (n+1) +1$, where

in the second last line $\dfrac{2^n}{2^n+1} <1$,

and in the last line the hypothesis has been used.

Answer 3

$$H_n = \sum_{k=1}^n \frac{1}{k}.$$ Then $$\begin{align*} H_{2^{n+1}} &= \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} \\ &= H_{2^n} + \sum_{j=1}^{2^{n+1} - 2^n} \frac{1}{2^n + j} \\ &\overset{\text{i.h.}}{\le} (n+1) + \sum_{j=1}^{2^n} \frac{1}{2^n + j} \\ &< (n+1) + \sum_{j=1}^{2^n} \frac{1}{2^n} \\ &= (n+1) + 2^n \cdot \frac{1}{2^n} \\ &= (n+1) + 1 \\ &= n+2, \end{align*}$$ where the inequality with "i.h." indicates the step where the induction hypothesis was used.