# The solution to the recurrence equation $T(n) = 2 T\left(\frac{n}{2}\right) + 2$

I got stuck at the solution to the recurrence equation $T(n) = 2 T\left(\frac{n}{2}\right) + 2$.

Please give me a detailed explanation or references with detailed steps?

Sorry, I missed something.

If $n = 2$, then $T(n) = 1$; else if $n > 2$, then $T(n) = 2T\left(\frac{n}{2}\right) + 2$;

And a solution is suggested as: $$T(n) = \frac{3n}{2} - 2$$

-
You might want to look at the answers to some of the numerous very similar questions already on the site. – Did Jun 16 '12 at 10:44
What is $T$ ? if it is a sequence what about the case $n$ is odd ? – Mohamed Jun 16 '12 at 10:54
@did But I think they're really wrong problems. $T(n)=2T(n/2)+2$ only constrains when $\log_2(x/y)\in\mathbb{Z}$. Perhaps $T(\lfloor n/2\rfloor)$ or $T(\lceil n/2\rceil)$ is right, or $T(x)$ is bounded when $0\le x<1$. – Frank Science Jun 16 '12 at 11:32
@Frank This initial conditions point has been made ad nauseam in previous posts. // The irony here is that introducing $T(n)=nS(n)-2$ yields readily $S(n)=S(n/2)$. – Did Jun 16 '12 at 11:35
@user900168: This new version still leaves infinitely many arbitrary choices. (And thus infinitely many solutions.) – Dejan Govc Jun 16 '12 at 11:44

As others have stated, you need to make additional assumptions to find a unique solution. I will assume that you want to find an approximate equivalent to some discrete relation defined over the integers, and therefore you are looking for a simple function defined over reals that satisfies this continuous relation.

For this purpose, a natural constraint is to require that $T$ is a polynomial defined over the reals. Let $a_k x^k$ be the leading coefficient of $T$ ($k\ge 1$). Then we must have: $$a_k=2a_k/2^k$$ hence $k=1$ because $a_k\ne 0$. So $T(n)=an+b$, and the relation $$an+b=2\left(a\tfrac n 2+b\right)+2$$ is satisfied iff $b=-2$.

And because $T(2)=1$, $a=3/2$, giving the equation you were looking for.

-
Thank you very much – user900168 Jun 17 '12 at 16:33

The recurrence equation tells us nothing about the relation between odd terms. Since the even terms are completely determined by the choice of the odd terms, we can choose odd terms arbitrarily. Then we can calculate the even terms from the recurrence as follows, for $m$ odd:

\begin{align}a_{2^n m} &= 2a_{2^{n-1}m}+2=\\&=2^2a_{2^{n-2}m}+2^2+2=\\&=\cdots=\\&=2^na_m+2^m+2^{m-1}+\cdots+2=\\&=2^n a_m + 2^{m+1}-2\end{align}

All solutions are of this form. To justify the calculation rigorously, use mathematical induction.

-

First we need to check if $f(n)\in\mathcal{O}(n^{log_{b}{(a)}-\epsilon})$, for some $\epsilon\gt0$:

Using the Master Theorem, with $a=2$, $b=2$, $f(n)=2$, $log_{2}{2}=1$:

$$2\in\mathcal{O}(n^{1-\epsilon})$$

Choosing $\epsilon=1$, we get:

$$2\in\mathcal{O}(1)$$

Which holds, so using the Master Theorem, we can determine that:

$$T(n)\in\mathcal{\Theta}(n)$$

Bear in mind that a solution is not possible as we do not have any information about the starting point of the sequence, so we can only determine the growth of the sequence.

-