Check if an integer is present in a linear recurrence 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.
 A: Notice how small $\psi \approx 0.44$ is. So in the expression
$$F_n = \frac{\phi^n - \psi^n}{\sqrt{17}}$$
$\phi^n$ is doing all of the work. After all, $0 \leq \psi^n \leq \left ( \frac{1}{2} \right )^n$.
So at least eventually, $F_n = \left \lceil \frac{\phi^n}{\sqrt{17}} \right \rceil$. Some quick computation will show whether this is always true, or if you'll need to have finitely many special cases. Of course, you can handle finitely many special cases without breaking $O(1)$ time/space.
This makes your job substantially easier. As now $F_n \approx \frac{\phi^n}{\sqrt{17}}$, and so some quick algebra gives
$$n \approx \log_\phi \left ( \sqrt{17} F_n \right ).$$
So given any $k$, we have a possible value of $n$. Namely, look at $m$ the nearest integer to $\log_\phi \left ( \sqrt{17} k \right )$. Then we can ask if $F_m$ really does equal $k$.
Both of these steps can be done in $O(1)$ space and time (at least if we use the common lie that real-valued arithmetic is constant time), as desired.
(Caveat Lector: I didn't check if you found these $\phi$ and $\psi$ correctly. So the specifics might change based on that. The idea should still work, though).

I hope this helps ^_^
