35
$\begingroup$

The Fibonacci sequence is $0, 1, 1, 2, 3, 5, 8, 13, 21, 34,\ldots$, where each term after the first two is the sum of the two previous terms.

Can we find the next Fibonacci number if we are given any Fibonacci number?

For example, if $n = 8$ then the answer should be $13$ because $13$ is the next Fibonacci number after $8$.

$\endgroup$
  • 8
    $\begingroup$ Only if you exclude 1, since it would return two unique and valid answers $\endgroup$ – Stian Yttervik Oct 13 at 20:37
  • 2
    $\begingroup$ The obvious answer, although not very satisfying, is "calculate the Fibonacci sequence until you reach the number you were given, then go one more". I suggested an edit to exclude that, since I don't think it's what OP was looking for, but apparently the reviewers felt differently. $\endgroup$ – Geoffrey Brent Oct 15 at 3:34
  • $\begingroup$ There is an explicit formula for F(n) that makes the given info about a value of F(n-1) unnecessary. But Matt Daly's answer is spot on as to the right idea, although there is an issue about rounding vs. floor vs. ceiling vs. precision... $\endgroup$ – Dr Mike Ecker Oct 15 at 18:59
59
$\begingroup$

The ratio of any two consecutive entries in the Fibonacci sequence rapidly approaches $\varphi=\frac{1+\sqrt5}2$. So if you multiply your number by $\frac{1+\sqrt5}2$ and round to the nearest integer, you will get the next term unless you're at the very beginning of the sequence.

$\endgroup$
  • 29
    $\begingroup$ @sr123 He did say "round to the nearest integer". That's not what ceil does, so of course you don't get the correct result. From checking the first few values, actually rounding will get you correct results unless you're starting from 0 or from 1. $\endgroup$ – HTNW Oct 12 at 22:58
  • 5
    $\begingroup$ Trying to do this in floating point is a bad idea; Fibonacci numbers quickly grow beyond the ability of floating point to accurately represent, so your computation will suffer from rounding error. $\endgroup$ – user2357112 supports Monica Oct 13 at 6:52
  • 21
    $\begingroup$ This is a math site, not a computer site, and we work with abstract real number arithmetic here, not floating point. However, anyone actually trying to compute a Fibonacci number by multiplying another Fibonacci number by $(1+\sqrt{5})/2$ is probably going to use a computer, and representation issues will be important. $\endgroup$ – user2357112 supports Monica Oct 13 at 12:26
  • 3
    $\begingroup$ It seems that floating-point precision first causes this to break down at the 79th Fibonacci number; at least in Python (64-bit floats), round((1 + sqrt(5))/2 * 8944394323791464) is 14472334024676222, while the 79th term is 14472334024676221. Using an arbitrary-precision float type, such as gmpy2.mpfr with precision set large enough, can go farther (e.g. precision=1000 works until the 1444th term; precision=2000 works for 2884 terms.) $\endgroup$ – Nick Matteo Oct 13 at 20:44
  • 1
    $\begingroup$ @NickMatteo, yep, 64-bit IEEE (double) floats have an effective mantissa of 53 bits, so the maximum exact integer that fits is 9007199254740992, a bit more than F(78), but less than F(79). (of course the size of the mantissa would also affect the accuracy of sqrt(5) itself) $\endgroup$ – ilkkachu Oct 13 at 21:32
81
$\begingroup$

Given a Fibonacci number $n$, let $m$ be the next Fibonacci number. The Fibonacci sequence has the property that for any three consecutive elements $r,s,t$, we have $rt=s^2\pm 1$ (proof is by induction, which you might like to try $-$ the choice of signs alternates). And we know that the previous Fibonacci number is $m-n$. So we have $$m(m-n)=n^2\pm 1$$ This is a quadratic equation in $m$, with solutions $m=\frac12(n\pm\sqrt{5n^2\pm 4})$. We know that $m\ge n$, so $m$ must equal $\frac12(n+\sqrt{5n^2\pm 4})$. And we can choose between $+4$ and $-4$ because only one of $\sqrt{5n^2+4}$ and $\sqrt{5n^2-4}$ can be an integer (with the single exception of $n=1$).

So the answer is whichever one of $\frac12(n+\sqrt{5n^2+4})$ and $\frac12(n+\sqrt{5n^2-4})$ is an integer.

Note that the single exception $n=1$ occurs twice in the Fibonacci sequence, so there are indeed two possible answers in this case.

$\endgroup$
  • 10
    $\begingroup$ This is the best answer. $\endgroup$ – Misha Lavrov Oct 14 at 1:29
  • $\begingroup$ Good answer - the induction proof and the two square roots not both being integers follows straightforwardly. $\endgroup$ – Ross Ure Anderson Oct 16 at 17:35
  • $\begingroup$ Using this development, the difference $m-\phi n$ is asymptotic to $2/\sqrt5n$, and this justifies the rounding method. $\endgroup$ – Yves Daoust Oct 17 at 18:43
21
$\begingroup$

$n\in\mathbb{N}$ is a Fibonacci number iff $5n^2-4$ or $5n^2+4$ is a square. In the former case $n=F_{2k+1}$ while in the latter case $n=F_{2k}$. Assuming $n\geq 2$, in the former case $F_{2k+2}=\lfloor \varphi n \rfloor$ and in the latter case $F_{2k+1}=\lceil \varphi n\rceil $, with $\varphi=\frac{1+\sqrt{5}}{2}$.

Example: if $n=8$ we have that $5\cdot 8^2+4=18^2$, hence $n$ is a Fibonacci number with even index and the next Fibonacci number is $\lceil 8\varphi \rceil =13$.

$\endgroup$
  • 6
    $\begingroup$ If you've gone to the trouble to find the square root $m$ of $5n^2 - 4$ or $5n^2 + 4$, you can avoid floating-point arithmetic by computing the next Fibonacci number as $(n + m)/2$. $\endgroup$ – Mark Dickinson Oct 13 at 9:18
  • $\begingroup$ @MarkDickinson How does that work? $\endgroup$ – Varad Mahashabde Oct 13 at 15:25
  • 2
    $\begingroup$ Good question, but it looks like @TonyK has saved me from answering ... $\endgroup$ – Mark Dickinson Oct 13 at 15:47
5
$\begingroup$

Along similar lines to Matthew Daly's answer:

Binet's formula gives an exact value for the n'th Fibonacci number where numbering starts with $F_0=0$ and $F_1=1$:

$F_n = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}$

$\sqrt{5} F_n=(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n$

$=\phi^n - (\frac{-1}{\phi})^n$, where $\phi = \frac{1+\sqrt{5}}{2}$ (using the identity that $\phi-1=\frac{1}{\phi}$, which is easy to prove).

From there it's easy to show that for $n>2$, $|$log$_\phi(F_n\sqrt{5})-n|<0.5$. (Hint: as $n$ becomes large, the first of these two terms becomes very large and the second goes to zero.)

If $F_n=1$ obviously the question is unanswerable, and if $F_n=0$ it's trivial. If $F_n>1$ then $n>2$ and so we can calculate $n$ by rounding log$_\phi(F_n\sqrt{5})$ to the nearest integer.

Now we have $n$, simply apply Binet's formula in the forwards direction and we're done.

$\endgroup$
  • 1
    $\begingroup$ Good answer, the log inequality requiring $1 + \frac{1}{(\phi + 1)^n} < \sqrt{\phi}$ ($n$ odd) and $\frac{1}{\sqrt{\phi}} < 1 - \frac{1}{(\phi + 1)^n}$ ($n$ even), which is easily checked directly for $n \geq 1$ and $n \geq 2$ respectively. $\endgroup$ – Ross Ure Anderson Oct 16 at 18:46

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.