The $n$’th Harmonic number The $n$’th Harmonic number is defined as follows: $$H_n = 1 + \frac12 + \frac13 +\ldots + \frac1n$$ for $n\geq 1$.
a) Show that for all $n≥0$: $H_{2^n} \geq 1+\frac n2$.
b) Show that for all $n≥0$: $H_{2^n} \leq 1+n$.
 A: (a). Base case:
for $n = 0,$ we have $H_{2^n}= H_1 = 1,$ and $1 + 0/2 = 1.$
Induction Step:
Let's assume $k \geq 0$ is an arbitrary number, and it holds for $k$:
$H_{2^k} \geq 1+ k/2.$
Then we prove it for $k+1$:
$$\begin{eqnarray}
H_{2^{k+1}} & = & H_{2^k} + \underbrace{\frac{1}{2^k+1} + \ldots +
                                              \frac{1}{2^{k+1}}}_{\text{($2^k$ terms)}} \\
         & \geq &1 + k/2 + \underbrace{\frac{1}{2^k+1} + \ldots +
                                              \frac{1}{2^{k+1}}}_{\text{($2^k$ terms)}} \\
         & \geq & 1 + k/2 + \underbrace{\frac{1}{2^{k+1}} + \ldots +
                                              \frac{1}{2^{k+1}}}_{\text{($2^k$ terms)}} \\
         & = & 1 + k/2 + \frac{2^k}{2^{k+1}} \\
         & = & 1 + k/2 +1/2 \\
         & = & 1+ (k+1)/2
\end{eqnarray}$$
so, it holds for $k+1.$ Therefore, by induction we proved it is true for all $n \geq 0.$
A: (b) Assume it is true for $k.$ We want to prove that it's true for $k+1.$ First note that, $H_{2^{k+1}} = H_{2^k} +\frac{1}{2^k+1} +….+ \frac{1}{2^{k+1}}.$ Now, for each $k \in \mathbb N, 2^k < 2^k+1, 2^k<2^k+2, \cdots, 2^k<2^{k+1}.$ So $\frac{1}{2^k+1} +….+ \frac{1}{2^{k+1}} \leq 1.$
