Given a Fibonacci number , find the next Fibonacci number

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.


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