Fibonacci sequence: Given $n$ and $\mathrm{Fib}(n)$, is it possible to calculate $\mathrm{Fib}(n-1)$?

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

• Even output of $F_{n-1}$ cannot be done in constant time. (The length of binary representation of $F_{n-1}$ is linear in $n$.) But based on the wording in original post I would guess that you mean using constantly many operations with integers. Commented Aug 20, 2014 at 8:14
• @Martin Sleziak - you are correct that I meant "constantly many operations with integers" Commented Aug 20, 2014 at 13:23

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.

• Here is a table that shows the pattern:$$\begin{array} {c|c|c} n & a_n & a_n / a_{n-1} \\ \hline 0 & 0 & \\ \hline 1 & 1 & \\ \hline 2 & 1 & 1.0000 \\ \hline 3 & 2 & 2.0000 \\ \hline 4 & 3 & 1.5000 \\ \hline 5 & 5 & 1.6667 \\ \hline 6 & 8 & 1.6000 \\ \hline 7 & 13 & 1.6250 \\ \hline 8 & 21 & 1.6154 \\ \hline 9 & 34 & 1.6190 \\ \hline 10 & 55 & 1.6176 \\ \hline 11 & 89 & 1.6182 \\ \hline 12 & 144 & 1.6180 \\ \hline 13 & 233 & 1.6181 \\ \hline 14 & 377 & 1.6180 \\ \hline \end{array}$$ Commented Aug 20, 2014 at 2:25
• @DanielV - agreed, this will work but as marty cohen points out in his anti-answer below, for large values of n simply rounding to the nearest integer will not necessarily yield the correct answer. Commented Aug 20, 2014 at 13:34

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

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