3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Do you need an exact closed for solution or just a bound on the solution? $\endgroup$ Jul 22, 2015 at 22:21
  • $\begingroup$ Have you tried splitting into cases where $n$ is even and odd? $\endgroup$
    – Chester
    Jul 22, 2015 at 22:25
  • $\begingroup$ I'm trying to get an exact closed formula for that equation. $\endgroup$
    – user256272
    Jul 22, 2015 at 22:27
  • 1
    $\begingroup$ you can deduce it to : $$\left\{\begin{matrix} k(1)=0 & \\ k(n)=n-1+k(q)+k(q) &n=2q \\ k(n)=n-1+k(q+1)+k(q) & n=2q+1 \end{matrix}\right. \\\left\{\begin{matrix} k(1)=0 & \\ k(n)=2q-1+2k(q) &n=2q \\ k(n)=2q+k(q+1)+k(q) & n=2q+1 \end{matrix}\right.$$ $\endgroup$
    – Khosrotash
    Jul 22, 2015 at 22:31

1 Answer 1

4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.