3
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you go from $\log_2 n - 1 < k \leq \log_2 n$ to $k = \lfloor \log_2(n) \rfloor$? $\endgroup$ – user437320 Apr 16 '17 at 15:56
  • $\begingroup$ @user437320 If $\log_2 n$ is an integer, then $k = \log_2 n = \lfloor \log_2 n \rfloor$; If $\log_2 n$ is not an integer, then $k = \lfloor \log_2 n \rfloor$. $\endgroup$ – PSPACEhard Apr 16 '17 at 15:58
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.