Recurrence Relation from Old Exam I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? 
$$T(n)  = \begin{cases}  n,\quad &\text{        if n=1 or n=0 }\\
\sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n   ,\quad   &\text{   if n>1} \end{cases}$$

Let $S(n)=T^2(n)$  Then the recurrence is $S(n)=\frac 12(S(n-1)+S(n-2))+n$ gives $S(n)=\frac 13n^2+\frac {15}{27}n+\frac 2{27}-\frac 2{27\cdot 2^n}$
