$t(\lfloor\frac{n}{2}\rfloor)+t(\lceil\frac{n}{2}\rceil)+n=n(\lfloor\log n\rfloor+3)-2^{\lfloor\log n\rfloor +1}$

Question

Given the following recurrence relation:

$t(1) = 1$

$t(n) = t(\lfloor \frac{n}{2} \rfloor) + t(\lceil \frac{n}{2} \rceil) + n$

How would a proof for the solution $t(n) = n (\lfloor \log n \rfloor + 3) - 2^{\lfloor \log n \rfloor + 1}$ look?

I suppose this should be proven by induction.

The base case would be $t(1) = 1 = 3 - 2 = 1 \cdot (\log 1 + 3) - 2^{\log 1 + 1}$

Next consider two cases. The case $n$ is even and $n$ is odd...

Is that correct? And if yes, how would you choose $n$? $n=2k$ and $n=2k+1$?

Answer 1

Hint:

If you take the $2k$ and $2k+1$ approach, your recurrence becomes $$t(2k)=2t(k)+2k$$ $$t(2k+1)=t(k)+t(k+1)+2k+1$$

while your inductive hypothesis becomes $$t(2k)=2k(\lfloor\log k\rfloor+4)-2^{\lfloor\log k\rfloor +2}$$ $$t(2k+1)=(2k+1)(\lfloor\log k\rfloor+4)-2^{\lfloor\log k\rfloor +2}$$

and the inductive step looks reasonably simple, with some care needed when $k$ is one less than a power of two. I might start by checking the cases when $k=1$, i.e. $n=2,3$