6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Aug 20, 2014 at 8:14
  • $\begingroup$ @Martin Sleziak - you are correct that I meant "constantly many operations with integers" $\endgroup$
    – sevzas
    Aug 20, 2014 at 13:23

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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}$$ $\endgroup$
    – DanielV
    Aug 20, 2014 at 2:25
  • $\begingroup$ @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. $\endgroup$
    – sevzas
    Aug 20, 2014 at 13:34
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .