Recurrence Relation(with Square root) I came across a very peculiar recurrence relation :


  $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)}  $


with initial values $T(0) = T(1) = 1$

Any helps on how to find it
Let $f(n)=\sqrt{T(n)}$, $f$ satisfies the linear recurrence relation $f(n)=f(n-1)+2f(n-2)$. The  characteristic polynomial is $x^2-x-2$ and it's roots are $-1,2$, so $f(n)$ is a linear combination of $(-1)^n,2^n$. After substituting the initial conditions you get $f(n)=\frac{1}{3}(-1)^n+\frac{2}{3}2^n$.