Given the following recurrence relation :
$f(n) = 5f(n-1) - 2f(n-2)$ where $f(0) = 0, f(1) = 1$
I need to find out if an integer $F_n$ is present in the sequence in $O(1)$ time and space.
Solving the equation, there are two distinct real roots.
$\phi = \frac{5 + \sqrt17}2$
$\psi = \frac{5 - \sqrt17}2$
Therefore, $F_n = \frac{\phi^n - \psi^n}{\sqrt17}$
Similar to Binet's rearranged formula, I want to solve for $n$ in terms of $F_n$.
Since, $\psi = \frac{2}{\phi}$
$\sqrt17F_n = \phi^n - \frac{2^n}{\phi^n}$
$Or,$
$\phi^{2n} - \sqrt17F_n\phi^n-2^n = 0$
Here I'm not able to find out a solution to express $n$ purely in terms of $F_n$ so that I can calculate the perfect square just like in Binet's formula.
from Hot Weekly Questions - Mathematics Stack Exchange
Rohit Roy Chowdhury
Post a Comment