0
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Consider denoting $f(n)=\sqrt{T(n)}$, and solving the linear recurrence relation for $f(n)$. $\endgroup$
    – Ariel
    Sep 2, 2015 at 14:19
  • $\begingroup$ let me try that $\endgroup$ Sep 2, 2015 at 14:22

1 Answer 1

6
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.