Proof that recursion $U_0 = 0$, $U_n= 1 + U_\left \lfloor n/2 \right \rfloor$, is solved by $U_n = \left \lfloor \log_2(n) \right \rfloor + 1$

Question

We have:

$$U_0 = 0\\U_n= 1 + U_\left \lfloor n/2 \right \rfloor$$

I found this closed form :

$$U_n = \left \lfloor log_2(n) \right \rfloor + 1$$

Proof : Base case : U1 = log2(1) + 1 = 1

We assume induction hypothesis : $P(n)= \left \lfloor log_2(n) \right \rfloor + 1$ and try to show $P(n+1)= \left \lfloor log_2(n+1) \right \rfloor + 1$.

I'm wondering if we can do this :

$$P(n+1) = \left \lfloor log_2(n+1) \right \rfloor + 1\\ = \left \lfloor log_2(n) +log_2(1 + 1/n) \right \rfloor + 1\\$$

Using : $ \left \lfloor x + n \right \rfloor = \left \lfloor x \right \rfloor + n\\$ will be relevent to find P(n+1) ?

How to have $\left \lfloor log_2(n+1) \right \rfloor$ and what to do with $ log_2(1 + 1/n)$ ??

Answer 1

First, you definitely have to leave out the $n=0$ case because $U_0=1$ whereas $\lfloor\log_2(0)\rfloor +1$ is not defined.

Secondly, you must use strong induction, i.e., to show $P(n)$, use $P(\lfloor n/2\rfloor)$ instead of $P(n-1)$.