Given $n$ and $\newcommand{\Fib}{\mathrm{Fib}} \Fib(n)$, is it possible to calculate the previous number in the Fibonacci sequence - $\Fib(n-1)$ using integer math in constant time? In other words, I believe I'm looking for a closed form formula.
For example: Given $n=10$ and $\Fib(10)=55$, I'd like to determine that $\Fib(9)=34$ without using $\Fib(7) + \Fib(8)$.
On
Hint $\rm\ n\:$ is a Fibonacci number iff the interval $\rm\ [\phi\ n - 1/n,\ \phi\ n + 1/n]\ $ contains a positive integer (the next Fibonacci number for $\rm\ n > 1)$. This follows from basic properties of continued fractions.
For example, $\rm\ 2 \to [2.7,\ 3.7],\ \ 3\to [4.5,\ 5.2],\ \ 5 \to [7.9,\ 8.3]\ \ldots$
For a proof see e.g. $ $ T. Komatsu: The interval associated with a fibonacci number. $\ $
On
This is a dissenting note on some of these answers. I am purposly making this an answer, though it really is an anti-answer.
The problem with any answer that uses $\phi$ is that, as $n$ gets larger, $\phi$ has to be computed with increasingly great precision. This will not take constant time, either for the computation of $\phi$ or the multiplication by $\phi$.
By Binet's Formula, we know that $F_n = \dfrac{1}{\sqrt{5}}\left(\phi^n-(-\phi)^{-n}\right) \approx \dfrac{1}{\sqrt{5}}\phi^n$ where $\phi = \dfrac{1+\sqrt{5}}{2}$.
Using this formula, we can get that $F_{n-1}$ is the nearest integer to $\dfrac{1}{\phi} F_n$ for large $n$
More rigorously, we have $F_{n-1} - \dfrac{1}{\phi} F_n = \dfrac{1}{\sqrt{5}}\left(\phi^{n-1}-(-\phi)^{-(n-1)}\right) - \dfrac{1}{\phi\sqrt{5}}\left(\phi^n-(-\phi)^{-n}\right)$ $= -\dfrac{(-\phi)^{-(n-1)}}{\sqrt{5}} - \dfrac{(-\phi)^{-(n+1)}}{\sqrt{5}}$ $= \dfrac{(-\phi)^{-n}}{\sqrt{5}}\left(\phi + \phi^{-1}\right) = (-\phi)^{-n}$.
Thus, for $n \ge 2$, we have $\left|F_{n-1} - \dfrac{1}{\phi} F_n \right| = \phi^{-n} < \frac{1}{2}$, and so, $F_{n-1}$ is the nearest integer to $\dfrac{1}{\phi}F_n$.
Dividing $F_n$ by $\phi$ and rounding the result to the nearest integer shouldn't be too computational.