Is Binet's formula for the Fibonacci numbers exact?

$F_n = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}$

If so, how, given the irrational numbers in it?


  • 12
    $\begingroup$ Yes, it is exact. The irrational parts happen to cancel out. Have you tried plugging in a few values of $n$? $\endgroup$ Jul 3, 2013 at 9:53
  • 2
    $\begingroup$ Having irrational numbers in a formula producing integers is not anything strange. Just take e.g. $\sqrt{2}^2$. $\endgroup$ Jul 3, 2013 at 9:55
  • 4
    $\begingroup$ Why not try before ask? Ir you can try to apply the homomorphism $\alpha $that send $\sqrt5$ to $-\sqrt5$ to observe that $F_n$ is always fixed by $\alpha$, i.e. $F_n$ is always a rational algebraic integer, hence an ordinary integer. Does this suffice to be a good reason that $F_n$ might look right? $\endgroup$
    – awllower
    Jul 3, 2013 at 10:15
  • $\begingroup$ It is exact. However, it is not a good way to calculate $F_n$ for very large $n$. $\endgroup$ Jul 3, 2013 at 13:21
  • 2
    $\begingroup$ Possible duplicate of Prove this formula for the Fibonacci Sequence $\endgroup$
    – Watson
    Jan 12, 2017 at 14:27

4 Answers 4


As others have noted, the $\sqrt 5$ parts cancel, leaving an integer. We can recover the Fibonacci recurrence formula from Binet as follows:

$$F_n+F_{n-1} = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}+\frac{(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}}{2^{n-1} \sqrt{5}}=$$$$\frac{(1+\sqrt{5})^{n-1}(1+\sqrt 5+2)-(1-\sqrt{5})^{n-1}(1-\sqrt5+2)}{2^n \sqrt{5}}$$

Then we notice that $(1\pm\sqrt5)^2=6\pm2\sqrt 5=2(3\pm\sqrt5)$

And we use this to simplify the final expression to $F_{n+1}$ so that $F_n+F_{n-1} =F_{n+1}$

And the recurrence shows that if two successive $F_r$ are integers, every Fibonacci number from that point on is an integer. Choose $r=0,1$. This is another way of proving that the cancellation happens.

  • 13
    $\begingroup$ Maybe it should be Bennet's formula :). $\endgroup$
    – Dan Rust
    Jul 3, 2013 at 11:07
  • $\begingroup$ This is perfect, thank you. $\endgroup$
    – N. McA.
    Jul 3, 2013 at 14:48
  • $\begingroup$ @DanielRust When you time-travel names always get distorted... $\endgroup$ Jul 3, 2013 at 18:09

It is exact, all right. When you expand the powers in the numerators the alternating signs mean that all the surviving terms are of the form an integer times $\sqrt5$. Therefore all the $\sqrt5$s cancel.

Try it out with $n=2$ and $n=3$.

It may be of interest to you to observe that as $|1-\sqrt5|/2\approx0.618$ its powers quickly approach zero. So for sizable $n$, you can drop that term, and just round the dominant term to the nearest integer. For example with $n=8$ you get $F_8=21$ and $(1+\sqrt5)^8/(2^8\sqrt5)\approx21.009$.


$${(1+\sqrt5)^n-(1-\sqrt5)^n} \over 2^n \sqrt5$$

Expand the numerator:


In the second sum, all the even powered terms get a positive sign, which becomes a negative sign due to the fact that the second sum is being subtracted. Those cancel out with the first sum and we get:

$$(1+\sqrt5)^n-(1-\sqrt5)^n=2\sum_{0\leq2k\leq n}{\binom{2k+1}{n}\sqrt5^{2k+1}}$$

We're dividing this by $2^n\sqrt5$ so we get:

$$\frac{2}{2^n}\sum_{0\leq2k\leq n}{\binom{2k+1}{n}\sqrt5^{2k}}$$ $$=\frac{1}{2^{n-1}}\sum_{0\leq2k\leq n}{\binom{2k+1}{n}5^k}$$

Though I have to say, I am a bit stumped as to why this should be an integer.

  • $\begingroup$ So this does not answer the question: And I think that to prove this expression is an integer is not so obvious. Maybe one can prove that this is an integer by induction; but then it loses the initial meaning of proving the integer-ness by an explicit expression I suppose. In any case, thanks for sharing this idea. $\endgroup$
    – awllower
    Jul 4, 2013 at 14:52
  • 1
    $\begingroup$ @awllower Strictly speaking the question only involved the irrationals, which this does explain. I have a bit of a feeling the integrality of this expression might have something to do with the sum of the $n$th row of Pascal's triangle adding to $2^n$ $\endgroup$
    – Jack M
    Jul 4, 2013 at 15:28
  • $\begingroup$ Good: it would be my pleasure to read the application of Pascal triangle in this situation as well. I think that, as an amazing application of combinatorial arguments, this answer is quite great. :) $\endgroup$
    – awllower
    Jul 5, 2013 at 4:59

For linear reccurent sequence you can find expression depending on the roots of the associated polynom.

$$ F_{n+1} = F_{n} + F_{n-1} $$

is associated to

$$ x^2 = x +1 $$

Wich has two solution, $ \frac{1 - \sqrt{5}}{2} $ and $ \frac{1 + \sqrt{5}}{2} $ (the golden ratio, a more than interesting number)

Simple roots give a general solution of the form:

$$F_{n} = A * (\frac{1 - \sqrt{5}}{2})^{n} + B * (\frac{1 + \sqrt{5}}{2})^n $$

To determine A and B you have to input initial contidions:

$$F_{0} = A + B = 0 $$

So $$ B = - A $$


$$F_{1} = -B * (\frac{1 - \sqrt{5}}{2} - \frac{1 + \sqrt{5}}{2}) =1 $$

$$ B = \frac{1}{\sqrt{5}} $$


$$F_{n} = \frac{ (1 + \sqrt{5})^{n} - (1 - \sqrt{5})^n}{2^n\sqrt{5}} $$

By Solving $F_0 = i$ and $F_1 = j$ you can find the general expression of Fibonnaci sequence with starting terms i and j.

  • $\begingroup$ This is really neat but I have a perhaps very novice question: how do you relate recurrence relations and polynomials? $\endgroup$ Jul 3, 2013 at 13:24
  • 1
    $\begingroup$ you just have to replace, if R is a root of the associated polynom, you have in the general expression $R^{n+1} = R^{n-1} * R^2 = R^{n-1} * (R + 1) = R^{n} + R^{n-1}$ thus satisfying the recurrence equation. General results about dimension of the space of solutions will give the reverse implication. $\endgroup$
    – lcrmorin
    Jul 3, 2013 at 13:36
  • 1
    $\begingroup$ This works the same way for others polynom, beware of multiple roots. $\endgroup$
    – lcrmorin
    Jul 3, 2013 at 13:36
  • $\begingroup$ Oh that makes complete sense. Thanks! $\endgroup$ Jul 3, 2013 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.