Prove $H_{2^m} \leq 1 + m$, where $H_n = \sum\limits_{k=1}^n \frac{1}{k}$

Question

I really I am not seeing how to continue my approach, which is this.

1. Base case:

$m = 1$, so we have $H_2 \leq 2$, where $H_2 = \sum\limits_{k=1}^2 \frac{1}{k} = \frac{1}{1} + \frac{1}{2} = \frac{3}{2}$

So our base case is proved, since $\frac{3}{2}$ is less than $2$.

2. Induction hypothesis:

Let $m$ be arbitrary. Let's assume $H_{2^m} \leq 1 + m$ is true.

3. Induction step:

Let's prove that $H_{2^{m+1}} \leq 1 + (m + 1)$ is also true.

$H_{2^{m+1}}$ means that instead of going until ${\frac{1}{2^m}}$, we continue until $\frac{1}{2^{m+1}}$.

We know how to sum until ${\frac{1}{2^m}}$, so $H_{2^{m+1}}$ = $H_{2^m}$ + TOTAL - $H_{2^m}$

Now, unfortunately, I am not seeing how can I go ahead proving using this approach...

Answer 1

Hint
$\frac{1}{2^m+1}+\frac{1}{2^m+2}+\ldots +\frac{1}{2^{m+1}}<\frac{1}{2^{m}}+\frac{1}{2^{m}}+\ldots +\frac{1}{2^{m}}=2^m\cdot \frac{1}{2^m}=1$
This is the induction step that is missing

Answer 2

Hint:
$$H_{2^{m+1}}=H_{2^m}+\dfrac{1}{2^m + 1}+\dfrac{1}{2^m + 2}+ \ldots +\dfrac{1}{2^{m + 1}-1}+\dfrac{1}{2^{m + 1}}$$

Answer 3

Note that

$$H_{2^{m+1}}-H_{2^m}=\sum_{n=2^{m}+1}^{2^{m+1}}\frac{1}{n}$$

In this sum each term is less than $\frac{1}{2^{m}}$ and you have $2^{m}$ terms, so:

$$\sum_{n=2^{m}+1}^{2^{m+1}}\frac{1}{n} \leq 2^{m} \cdot \frac{1}{2^m}\leq 1$$

Answer 4

Hint: $$H_{2^{m+1}} = H_{2^{m}}+\sum_{i = 2^m+1}^{2^{m+1}}\frac{1}{i}$$ Now you have an equality involving $H_{2^{m+1}}$ and $H_{2^{m}}$, so you can apply the induction hypothesis and tangle with the quantity $$\sum_{i = 2^m+1}^{2^{m+1}}\frac{1}{i}$$ to get your result.