# Recurrence formality 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.

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