Closed form of $T(n)=T(\lceil n/2 \rceil)+T(\lfloor n/2 \rfloor)+2$

Question

How in God's name could I find a closed form of $T(n)=T(\lceil n/2 \rceil)+T(\lfloor n/2 \rfloor)+2$?

I'm looking at the first numbers in sequence and I just don't see any relation...

Answer 1

$$\begin{align} T(2) &= 2T(1)+2\\ T(3) &= T(2) + T(1) + 2 = 3T(1)+4\\ T(4) &= 2T(2) + 2 = 4T(1)+6\\ T(5) &= T(3) + T(2) + 2 = 5T(1) + 8\\ T(6) &= 2T(3) + 2 = 6T(1) + 10\\ T(7) &= T(4) + T(3) + 2 = 7T(1) + 12 \end{align}$$

I see a pattern.

Answer 2

The answer is $T(n)=nT(1)+2(n-1)$.