Question

Prove that $H_{2^{\star }}\le 1+n$ where n is a nonnegative integer.

Short answer

$H_{2^{\star }}\le 1+n$ is a non negative integer.

Step-by-step solution

Step: 1

If n=0,

$\begin{array}{r}{H}_{2^0}\le 1+0\\ 1\le 0\end{array}$

it is true for n=0.

Step: 2

Let P(k) be true.

$H_{2^{\mathrm{\prime }}}\le 1+k$

We need to prove that P(k+1) is true.

Step: 3

$\begin{array}{r}{H}_{2^{+1}}=1+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{2^k}+\frac{1}{2^k+1}+\dots +\frac{1}{2^{k+1}}\\ \le k+1+\frac{1}{2^k+1}+\dots \frac{1}{2^{k+1}}\\ \le k+1+\frac{1}{2^k+1}+\dots +\frac{1}{2^{k+1}}\\ =k+1+2^k\cdot \frac{1}{2^k+1}\\ \le k+1+1\\ \le k+2\end{array}$

It is true for P (k+1) is true