How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$ I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve:
$$\begin{aligned}
T(1) &= 0 \\
T(2) &= 1 \\
T(n) & = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2 \qquad(\text{for each $n\ge2$})
\end{aligned}$$
Without the ceiling and floor I know that the solution is $T(n) = 3n/2 -2$ if $n$ is the power of 2, but how can I solve it with them? (and for every $n$, not just $n$ that is the power of 2).
Thanks a lot.

Lemma. $T(n+1)-T(n)=\begin{cases}2&\text{if $2\cdot 2^k\le T(n)<3\cdot 2^k$ for some $k\in\mathbb Z$}\\1&\text{otherwise}\end{cases}$
Proof. This is directly verified for $n\le 3$.
For larger $n$, we have
$$T(n+1)-T(n)=T(\lceil\frac{n+1}2\rceil)+T(\lfloor\frac{n+1}2\rfloor)-T(\lceil\frac{n}2\rceil) -T(\lfloor\frac{n}2\rfloor)$$
If $n=2m$ is even, this is $T(m+1)-T(m)$. And if $n=2m+1$ is odd, it is $T(m+1)-T(m)$ again. As in both cases, $n$ has the same two leading digits as $m$, the claim follows by induction. $_\square$
Corollary. Let $n=2^k+r$ with $0\le r<2^k$. Then
$$T(n)=\begin{cases}3\cdot2^{k-1}+2r&\text{if $r<2^{k-1} $}\\
2^{k+1}+r&\text{if $r\ge 2^{k-1} $}\end{cases} $$
Proof. By induction using the lemma. $_\square$
Especially, $T(n)/n$ oscillates as also found by achille hui, taking the value $3/2$ for $r=0$ and $5/3$ for $r=2^{k-1}$
