Prove the following fact about a recurrence relation

Question

Consider the following recursive relation: $$T(1)=1$$ $$T(n)=2T\left(\left\lfloor \frac n 2\right\rfloor\right)\text{ for }n\geq 2$$ It is required to show that $$T(n)=2^{\lfloor \log_2 n\rfloor}$$ I tried to solve this problem by considering two cases $n=2^b$, where $b\geq 1$ and $n=a\cdot 2^b$, where $a$ is an odd number. In the first case observe that $$T(2^b)=2\cdot T(2^{b-1})$$ $$=2^2\cdot T(2^{b-2})$$ $$...$$ $$T(2^b)=2^b$$ Also observe that $$2^{\lfloor \log_2 2^b\rfloor}=2^b$$ so we are done for case 1. I am facing difficulty in proving for case 2, when $n=a\cdot 2^b$. Any hints/suggestions will be much appreciated.

Answer 1

If $b$ is the largest integer such that $2^b$ divides $n$ with remainder $\geq 0$ then $$b=\lfloor{\log_2n\rfloor}.$$ Also $$\left\lfloor\frac 1 2\left\lfloor \frac n 2\right\rfloor\right\rfloor=\left\lfloor\frac {n} {2^2}\right\rfloor$$ for integer $n$. So $$T(n)=2T\left(\left\lfloor \frac n 2\right\rfloor\right)=2^2T\left(\left\lfloor \frac {n} {2^2}\right\rfloor\right)=\cdots=2^bT(1)=2^b$$

Answer 2

Take the binary logarithm of the recurrence: $$T'(1)=0\qquad T'(n)=1+T'(\lfloor n/2\rfloor)$$ The function $n\mapsto\lfloor n/2\rfloor$ is a right shift by one bit. It follows that if $n$ has $k+1=\lfloor\log_2n\rfloor+1$ bits, $k$ applications of the function are required to reach 1. Therefore $T'(n)=\lfloor\log_2n\rfloor$ and $T(n)=2^{\lfloor\log_2n\rfloor}$.