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}$$
 A: Hint:  Let $a(n)=T^2(n)$.  Then the recurrence relation becomes
$$a(n)={1\over2}a(n-1)+{1\over2}a(n-2)+n$$
with $a(0)=0$ and $a(n)=1$.  Now try finding $c$ and $C$ for which there's an inductive proof that $cn^2\lt a(n)\lt Cn^2$ for sufficiently large $n$.  
Added later (at OP's request):  I'll do one inequality, which hopefully will show you how to do the other.
We'd like to find a constant $C$ such that $a(n-1)\lt C(n-1)^2$ and $a(n-2)\lt C(n-2)^2$ together imply $a(n)\lt Cn^2$.  If we just plug the assumed inequalities into what we know, we have
$$\begin{align}
a(n)&={1\over2}a(n-1)+{1\over2}a(n-2)+n\\
&\lt {1\over2}C(n-1)^2+{1\over2}C(n-2)^2+n\\
&={1\over2}C\big(n^2-2n+1+n^2-4n+4\big)+n\\
&=Cn^2+(1-3C)n+{5\over2}C
\end{align}$$
Keep in mind that this is all "scratch" work:  We're not writing up a proof at this point, nor are we trying to find the exact value of $C$ that gives the inequality, we're just trying to spot a value that will make things work.
The key is in the coefficient $(1-3C)$ in the last line.  If $C$ is big, that coefficient is negative, which will make the term $(1-3C)n$ hugely negative if $n$ is "sufficiently" large.  So let's pick a convenient value and see what happens.  Let's try $C=2$.
If you redo the derivation above with $C=2$, you wind up with
$$a(n)\lt 2n^2-5n+5\lt 2n^2\quad\text{if }n\ge2$$
since $5-5n$ is negative for $n\ge2$.  
Note that any $C$ greater than ${1\over3}$ will make $1-3C$ negative, so you don't have to choose $C=2$.  It just happens to be convenient.  Something similar should happen when you look at the other inequality, $cn^2\lt a(n)$.  Give it a try!
A: 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}$
