Discrete math, Showing a recursive equation as equivalent to a non recursive equation.

Question

I'm having trouble with this:

Show that this recursive function:

$L(n) = \{0 : n = 1\ ,\ \lfloor(L(n/2))\rfloor +1 : n \gt 1\}$

is equivalent to this non-recursive equation:

$L(n) = \lfloor log2(n)\rfloor$

I know that this should be simple, but in the time I've been working on this I just can't seem to find a place to start on this. If someone could give me a starting point, it would be extremely helpful.

Answer 1

One approach is this: Let $K(n) = \text{floor}(\log_2(n))$, and then show that $K$ satisfies the recursion that defines $L$. Since there's a unique function satisfying that recursion, you can conclude that $K = L$.

To show that $K$ satisfies the recursion, first show that $K(1) = 0$; that should be easy.

Now let $n > 1$, and compare $K(n)$ to $\text{floor} (K (n/2)) + 1$ by writing both of these out. I suggest that you look at the cases where $n$ is even ($n = 2p$ for soem integer $p$) and when $n$ is odd $(n = 2p + 1)$.