Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
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\color{red}{\pm} 1$$ This is a quadratic equation in $m$, with solutions $m=\frac12(n\color{blue}{\pm}\sqrt{5n^2\color{red}{\pm} 4})$. We know that $m\ge n$, so $m$ must equal $\frac12(n\color{blue}{+}\sqrt{5n^2\color{red}{\pm} 4})$. And we can choose between $\color{red}{+}4$ and $\color{red}{-}4$ because only one of $\sqrt{5n^2\color{red}{+}4}$ and $\sqrt{5n^2\color{red}{-}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.
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.
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$
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$
Oct 13, 2019 at 20:44
$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$.
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.
