Given a Fibonacci number , find the next Fibonacci number

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

Solution 1:

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.

Solution 2:

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.

Solution 3:

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

Solution 4:

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.