# Solving the recurrence $T(n) = T\left(\left\lceil \frac{n}{2} \right\rceil\right) + T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + 1$

I have this recurrence relation:

$$T(n) = T\left(\left\lceil \frac{n}{2} \right\rceil\right) + T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + 1$$

and I should solve it with $$n = 2^m$$

\begin{align} T(2^m) &= T\left(\left\lceil \frac{2^m}{2} \right\rceil\right) + T\left(\left\lfloor \frac{2^m}{2} \right\rfloor\right) + 1 \\[6pt] &= T\left(\left\lceil 2^{m-1} \right\rceil\right) + T\left(\left\lfloor 2^{m-1} \right\rfloor\right) + 1 \\[4pt] &=2\cdot T(2^{m-1}) + 1 \end{align}

but now I am stuck. How can I get rid of $$T(2^{m-1})$$?

• Repeat the process until you get to T(0) and T(1). Jan 11 '20 at 13:25
• u mean i should solve $T(2^{m-1})$, but if do that i will get $T(2^{m-2})$ and so on Jan 11 '20 at 13:31

Let $$T(2^m)+1=a_m$$ Then $$a_m = 2a_{m-1}$$ Hence, it forms a geometric progression. So the general term is $$a_m=2^ma_0$$ $$\implies T(2^m)=2^mT(1)+2^m-1$$ Hope you can proceed now.
Once you have got $$T(2^m)=2.T(2^{m-1})+1$$ Let $$T(2^m)=2^m.a_m$$ put in above we get $$2^m.a_m=2^m.a_{m-1}+1$$ $$\therefore a_m-a_{m-1}=2^{-m}$$ $$.$$ Put values of m = m, m-1 , m-2 ,...,1 and add all we get $$a_m-a_0=\sum_{m=1}^{m} 2^{-m}$$ Where a_0=T(1)=k (say) $$a_m=k+(1-2^{-m})$$ $$2^mT(2^m)=k+1-2^{-m}$$ $$T(2^m)=(T(1)+1).2^{-m}-1$$