# Given a Fibonacci number , find the next Fibonacci number

The Fibonacci sequence is $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34,\ldots0, 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 = 8n = 8$$ then the answer should be $$1313$$ because $$1313$$ is the next Fibonacci number after $$88$$.

Given a Fibonacci number $$nn$$, let $$mm$$ be the next Fibonacci number. The Fibonacci sequence has the property that for any three consecutive elements $$r,s,tr,s,t$$, we have $$rt=s^2\pm 1rt=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-nm-n$$. So we have
$$m(m-n)=n^2\color{red}{\pm} 1m(m-n)=n^2\color{red}{\pm} 1$$
This is a quadratic equation in $$mm$$, with solutions
$$m=\frac12(n\color{blue}{\pm}\sqrt{5n^2\color{red}{\pm} 4})m=\frac12(n\color{blue}{\pm}\sqrt{5n^2\color{red}{\pm} 4})$$. We know that $$m\ge nm\ge n$$, so $$mm$$ must equal $$\frac12(n\color{blue}{+}\sqrt{5n^2\color{red}{\pm} 4})\frac12(n\color{blue}{+}\sqrt{5n^2\color{red}{\pm} 4})$$. And we can choose between $$\color{red}{+}4\color{red}{+}4$$ and $$\color{red}{-}4\color{red}{-}4$$ because only one of $$\sqrt{5n^2\color{red}{+}4}\sqrt{5n^2\color{red}{+}4}$$ and $$\sqrt{5n^2\color{red}{-}4}\sqrt{5n^2\color{red}{-}4}$$ can be an integer (with the single exception of $$n=1n=1$$).
So the answer is whichever one of $$\frac12(n+\sqrt{5n^2+4})\frac12(n+\sqrt{5n^2+4})$$ and $$\frac12(n+\sqrt{5n^2-4})\frac12(n+\sqrt{5n^2-4})$$ is an integer.
Note that the single exception $$n=1n=1$$ occurs twice in the Fibonacci sequence, so there are indeed two possible answers in this case.