= Integer-halving recurrence with constant toll
{title2=$S_n=a+m(1+\lfloor\log_2n\rfloor),\quad n\geq1$}
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_2n\rfloor$ such steps. The formula follows by <strong induction>, using $\lfloor\log_2\lfloor n/2\rfloor\rfloor=\lfloor\log_2n\rfloor-1$ for $n\geq2$ 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.
Back to article page
