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
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Consider denoting $f(n)=\sqrt{T(n)}$, and solving the linear recurrence relation for $f(n)$. $\endgroup$– ArielSep 2, 2015 at 14:19
-
$\begingroup$ let me try that $\endgroup$– Kishan KumarSep 2, 2015 at 14:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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$.
