If $n>1$ is a power of $2$, show that $H_n \le 1 + \lceil{\log_2(n)}\rceil$ where $H_n$ denotes the $n^{th}$ harmonic number

Question

If $n$ is a power of $2$ and $n\gt1$. Using the fact that $$H_n \le H_{n/2} + 1$$ to show that $$H_n <= 1 + \lceil{\log_2{n}}\rceil$$ First of all, for k > 1 $$n = 2^k $$ $$H_{2^k} \le H_{2^k-1} + 1$$ and $$H_{2^k} \le 1 + \lceil{\log_2(2^k)}\rceil$$ $$= 1 + k$$ since k is an integer$$\lceil{k}\rceil = k$$

After preforming these substituions I have hit a wall.

Answer 1

$$H_1 = 1.$$

$$H_2 = 1 + 1/2 < 1+1,$$

$$H_4 = 1 + (1/2 + 1/3)+ 1/4 < 1+1 + 1,$$

$$H_8 = 1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + 1/8 < 1 + 3.$$

I hope the pattern is obvious now.