= Solution
A stronger exact formula makes the <induction> explicit:
$$
\boxed{S_n=1+m\bigl(1+\lfloor\log_2n\rfloor\bigr),\qquad n\geq1.}
$$
For $n=1$, the recurrence gives $S_1=S_0+m=1+m$. For $n\geq2$, set $j=\lfloor n/2\rfloor$, so $1\leq j<n$. In the relevant binary interval, $\lfloor\log_2j\rfloor=\lfloor\log_2n\rfloor-1$. The <strong induction> hypothesis gives
$$
S_n=S_j+m=1+m\bigl(1+\lfloor\log_2j\rfloor\bigr)+m
=1+m\bigl(1+\lfloor\log_2n\rfloor\bigr).
$$
For $n\geq2$, $S_n\leq1+m+m\log_2n\leq(1+2m)\log_2n$. Hence $S_n=O(\log_2n)$. This is an <integer-halving recurrence with constant toll>; the separately defined $n=0$ case does not require evaluating $\log0$.
Back to article page
