Recurrence formality question

Question

I have tried to solve this recurrence relation using induction. $$T(n) = T(\lfloor \log_2 n \rfloor) +1$$ It is clear that I should get something similar to $\log *n$, but I don't know how to formalize this kind of questions. Thank you for your kind help.

Answer 1

That $\lfloor \log_2 n \rfloor$ suggests you should plug in powers of $2$ and see if something interesting happens: (Assume $T(1)$ is given) \begin{align} T(2) &= T(\lfloor \log_2 2 \rfloor) +1 \\ &= T(1) +1; \\ T(4) &= T(\lfloor \log_2 4 \rfloor) +1 \\ &= T(2) +1 \\ &= T(1) +2; \\ T(8) &= T(\lfloor \log_2 8 \rfloor) +1 \\ &= T(3) +1 \\ &= T(1) +3; \\ T(16) &= T(\lfloor \log_2 16 \rfloor) +1 \\ &= T(4) +1 \\ &= T(1) +4; \end{align} and so on. Then, you notice that $T(2^m) = T(1) +m$; you may prove it by induction (the inductive step will make use of the recurrence relation.)