I have a recurrence equation that would be very easy to solve (without ceil and floor functions) but I can't solve them exactly including floor and ceil.
\begin{align}
k (1) &= 0\\
k(n) &= n-1 + k\left(\left\lceil\frac{n}{2}\right\rceil\right) + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right) \qquad n \in \mathbb{N}_+
\end{align}
How can I solve such an equation?
Best Answer
SKETCH: It’s often useful to gather some numerical data:
$$\begin{array}{rcc} n:&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18\\ k(n):&0&1&3&5&8&11&14&17&21&25&29&33&37&41&45&49&54&59\\ k(n)-k(n-1):&&1&2&2&3&3&3&3&4&4&4&4&4&4&4&4&5&5 \end{array}$$
Notice that the gaps in the bottom line are a single $1$, two $2$s, four $3$s, and eight $4$s. This suggests that if $2^{m-1}<n\le 2^m$, then $k(n)-k(n-1)=m$. Assuming this to be the case, we must have
$$k(2^m)=\sum_{\ell=1}^m\ell2^{\ell-1}=(m-1)2^m+1\;.$$
This can now be proved by induction on $m$, since $k(2n)=2n-1+2k(n)$. Now let $n=2^m+r$, where $0\le r<2^m$. Then the obvious conjecture is that
$$k(n)=k(2^m)+(m+1)r=(m-1)2^m+1+(m+1)r\;,$$
which again can be verified by induction, though the argument is a bit messier.
Note that $m=\lfloor\lg n\rfloor$, and $r=n-2^m$, so $m$ and $r$ are both readily obtained from $n$.