If $F(n) = 2F(\lfloor\frac{n}{2}\rfloor)$, how do we prove that $F(n) = 2^{\lfloor\log_2(n)\rfloor}$?

Question

Let $F(n) = 2F(\lfloor\frac{n}{2}\rfloor)$

The final case is $F(1) = 1$.

How do we prove that $F(n) = 2^{\lfloor\log_2(n)\rfloor}$?

If $n$ happens to be a power of $2$ then $F(n) = n$ but when it's not a power of $2$ I am not sure what the standard method is for handling floor cases because it doesn't seem cleanly simple anywhere. I can show that:

$F(n) = 2^1F(\lfloor\frac{n}{2^1}\rfloor) = 2^2F(\lfloor\frac{n}{2^2}\rfloor) = 2^3F(\lfloor\frac{n}{2^3}\rfloor) = 2^kF(\lfloor\frac{n}{2^k}\rfloor)$

and $k$ ends when $\lfloor\frac{n}{2^k}\rfloor = 1$ which makes $F(1) = 1$ so the answer is clearly $2^{k}$ for some special $k$ but I don't know how to get the $k$.

So maybe my real question is $\lfloor\frac{n}{2^k}\rfloor = 1$, how do we solve for $k$?

Answer 1

Note that $$\left\lfloor \frac{n}{2^k}\right\rfloor = 1\ \Leftrightarrow 1\ \leq \frac{n}{2^k} < 2 \ \Leftrightarrow\ \frac{n}{2} < 2^k \leq n\ \Leftrightarrow\ \log_2 n - 1 < k \leq \log_2 n $$ Therefore, $$ k = \lfloor \log_2 n\rfloor $$ since $k$ is an integer.

Answer 2

Hint: It might be useful to think of $n$ in binary. Check this example:

Let $n = 110101100$, then \begin{align*} F(n) &= 10 F(11010110) \\ &= 100 F(1101011) \\ &= 1000F(110101) \\ &= 10000F(11010) \\ &= 100000F(1101) \\ &= 1000000F(110) \\ &= 10000000F(11) \\&= 100000000F(1) \\ &= 100000000. \end{align*}

$F$ converts every $1$ after the leftmost one, to a $0$.