Solving recurrence relation If I have the following recurrence relation, 
$$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n $$
How would I show that $T(n)\le cn\lg(n)+dn $
 for some reals $c$ and $d$?
 A: Note that $\lceil n/2 \rceil = \lfloor (n+1)/2\rfloor$. It follows that 
$$\begin{align*}T(n+1) - T(n) 
&= T(⌊(n+1)/2⌋)+T(\lceil (n+1)/2\rceil) - T(\lfloor n/2 \rfloor)- T(\lceil n/2\rceil) + 1\\
&= T(\lceil (n+1)/2\rceil) - T(\lfloor n/2 \rfloor) + 1\\
&= T(\lfloor n/2 \rfloor + 1) - T(\lfloor n/2 \rfloor) + 1
\end{align*}$$
Therefore, 
$$\Delta T(n) = 1 + \Delta T(\lfloor n / 2 \rfloor)$$
where $\Delta$ is the forward difference operator. We recognize that this is satisfied by the number of bits required to express $n$ in binary. Thus
$$\Delta T(n) = \lceil \lg (n + 1) \rceil$$
Thus
$$T(n) = T(1) + \sum_{k=1}^{n-1}  \lceil \lg (k + 1) \rceil = T(1) + \sum_{k=2}^{n}  \lceil \lg k \rceil$$
To solve this equation, let $m = \lceil \lg n \rceil$. Then
$$\begin{align*}
T(n) + (2^m - n) m &= T(1) + \sum_{k=2}^{2^m}  \lceil \lg k \rceil \\
&= T(1) + \sum_{j=2}^m j2^{j-1} = T(1) + 2^m(m - 1)
\end{align*}$$
Thus 
$$T(n) = n \lceil \lg n \rceil - \lceil \lg n \rceil + T(1)$$
I think you can take it from here.
