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
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI 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$.