Just so no one thinks I am trying to get one over on anyone, this is a homework question. I have solved all the other problems, but I don't know where to begin with this one. I am not asking for an answer, just a direction or hint (that I can understand).
Prove by induction that if $T(n) = 1 + T(\lfloor n/2 \rfloor)$, $T(0) = 0$, and $2^{r-1} \le n < 2^r$ , $r \ge 1$, then $T(n) = r$. (Hint: use induction on $r$.)
How does $T(0) = 0$? If I plug $n=0$ in, would the function not return $1$? The floor of $T(0/2)$ is still going to be $0$, so calling $T(\lfloor n/2 \rfloor)$ would return $1$ still, no? I am clearly missing something.
Additionally, the hint says to use induction on $r$, but how does that help me with $T(n)$?
Thanks for any insight provided.
A recurrence relation needs to start with some non-recursive "seed value(s)" in order to be properly defined. This is your $T(0) = 0$. (If you don't have these, then your definition is self-referetial.)
You then apply the relation using the initial value:
$$T(1) = 1 + T(\lfloor 1/2 \rfloor) = 1 + T(0) = 1 + 0 = 1$$ $$T(2) = 1 + T(\lfloor 2/2 \rfloor) = 1 + T(1) = 1 + 1 = 2$$ $$T(3) = 1 + T(\lfloor 3/2 \rfloor) = 1 + T(1) = 1 + 1 = 2$$ $$T(4) = 1 + T(\lfloor 4/2 \rfloor) = 1 + T(2) = 1 + 2 = 3$$
From above, you can see that the condition holds for a few base cases. Now you apply induction. Assume $T(n) = r$ holds for $2^{r-1} \le n < 2^r$ and prove it holds for an $m$ where $2^r \le m < 2^{r+1}$.
Your calculation will look something like this: $$T(m) = 1 + T(\lfloor m/2 \rfloor) = 1 + T(2^r / 2) = 1 + T(2^{r-1}) = 1 + T(n) = 1 + r$$
where you'll need to justify some of those equalities.