Integer-halving recurrence with constant toll ($S_n=a+m(1+\lfloor {\log }_{2}n\rfloor ),n\ge 1$)

If $S_0=a$ and $S_n=S_{\lfloor n/2\rfloor }+m$ for positive integers $n$, each halving removes one binary digit until zero is reached. There are $1+\lfloor {\log }_{2}n\rfloor$ such steps. The formula follows by strong induction, using $\lfloor {\log }_2\lfloor n/2\rfloor \rfloor =\lfloor {\log }_{2}n\rfloor -1$ for $n\ge 2$ and checking $n=1$ separately. With fixed positive $m$, this is $\Theta (\log n)$ as $n\to \infty$; the zero case retains its separately defined value.