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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.