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.

Answer

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.

Attribution
Source : Link , Question Author : ppSpp , Answer Author : TonyK

Leave a Comment