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

• Only if you exclude 1, since it would return two unique and valid answers Oct 13, 2019 at 20:37
• The obvious answer, although not very satisfying, is "calculate the Fibonacci sequence until you reach the number you were given, then go one more". I suggested an edit to exclude that, since I don't think it's what OP was looking for, but apparently the reviewers felt differently. Oct 15, 2019 at 3:34
• There is an explicit formula for F(n) that makes the given info about a value of F(n-1) unnecessary. But Matt Daly's answer is spot on as to the right idea, although there is an issue about rounding vs. floor vs. ceiling vs. precision... Oct 15, 2019 at 18:59

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.

• This is the best answer. Oct 14, 2019 at 1:29
• Good answer - the induction proof and the two square roots not both being integers follows straightforwardly. Oct 16, 2019 at 17:35
• Using this development, the difference $m-\phi n$ is asymptotic to $2/\sqrt5n$, and this justifies the rounding method.
– user65203
Oct 17, 2019 at 18:43

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.

• @sr123 He did say "round to the nearest integer". That's not what 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.
– HTNW
Oct 12, 2019 at 22:58
• Trying to do this in floating point is a bad idea; Fibonacci numbers quickly grow beyond the ability of floating point to accurately represent, so your computation will suffer from rounding error. Oct 13, 2019 at 6:52
• This is a math site, not a computer site, and we work with abstract real number arithmetic here, not floating point. However, anyone actually trying to compute a Fibonacci number by multiplying another Fibonacci number by $(1+\sqrt{5})/2$ is probably going to use a computer, and representation issues will be important. Oct 13, 2019 at 12:26
• It seems that floating-point precision first causes this to break down at the 79th Fibonacci number; at least in Python (64-bit floats), 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.) Oct 13, 2019 at 20:44
• @user2357112 While I agree that Henry's argument lacks complete rigor, I disagree with your statement "This is not a computer site". Mathematics is the art of computing. Henry's argument can be improved by noting that $F_n=\big(\varphi^{n+1}-(-\varphi)^{-(n+1)}\big)/\sqrt{5}$ and that $\varphi^{-n}/\sqrt5$ whenever $n\geq1$. There is nothing "dirty" in rounding to the nearest integer., Oct 16, 2019 at 9:13

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

• If you've gone to the trouble to find the square root $m$ of $5n^2 - 4$ or $5n^2 + 4$, you can avoid floating-point arithmetic by computing the next Fibonacci number as $(n + m)/2$. Oct 13, 2019 at 9:18
• @MarkDickinson How does that work? Oct 13, 2019 at 15:25
• Good question, but it looks like @TonyK has saved me from answering ... Oct 13, 2019 at 15:47

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.

• Good answer, the log inequality requiring $1 + \frac{1}{(\phi + 1)^n} < \sqrt{\phi}$ ($n$ odd) and $\frac{1}{\sqrt{\phi}} < 1 - \frac{1}{(\phi + 1)^n}$ ($n$ even), which is easily checked directly for $n \geq 1$ and $n \geq 2$ respectively. Oct 16, 2019 at 18:46