# recursion and inductive proof

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(⌊𝑛/2⌋), T(0) = 0$, and $2^{r-1} \leq 𝑛 < 2^𝑟 , r ≥ 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(⌊𝑛/2⌋) 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.

• Yeah the problem must be stated incorrectly. $T(n) = 1 + T(\lfloor n/2\rfloor)$ must hold only for $n \geq 1$. – Ashvin Swaminathan Jul 25 '16 at 1:38
• The question is not well phrased, they should have put $T(0)=0$ first, or last, but not in between. The recurrence, they say explicitly, holds when $2^{r-1}\le n$, $r\ge 1$, so it does not hold at $n=0$. – André Nicolas Jul 25 '16 at 1:38
• T (0)=0 is the definition. – fleablood Jul 25 '16 at 1:42
• Right, T (0)=0 is the definition. Thanks for pointing that out, I don't know what I was thinking. – thePetester Jul 25 '16 at 9:06

We must prove the following statement for every positive integer $r$:

if $2^{r-1}\leq n\leq 2^r$ then $f(n)=r$.

It is clearly true when $r=1$ since Only $1$ satisfies $2^0\leq n< 2^1$ and $T(1)=T(0)+1=1$.

So suppose it is true for $r$, we must prove it is true for $r+1$.

So take $2^{r}\leq n< 2^{r+1}$. Then $2^{r-1}\leq \lfloor n/2 \rfloor < 2^r$.

By the inductive hypothesis $T(\lfloor n/2 \rfloor)=r$ and so $T(n)=r+1$ as desired.

• Thanks! I am not sure why I can blow through most of these questions and then something like this just stops me dead in my tracks. – thePetester Jul 25 '16 at 9:55
• probably just lack of practice, it can be hard to rigorously justify statements when you haven't seen how to do it for similar problems. – Jorge Fernández Hidalgo Jul 25 '16 at 14:46