9
$\begingroup$

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?

Thanks.

$\endgroup$
5
  • 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

19
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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

Expand the numerator:

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

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.

$\endgroup$
3
  • $\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
2
$\begingroup$

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

and

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

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

So

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

$\endgroup$
3
  • $\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$ Jul 3, 2013 at 13:36
  • 1
    $\begingroup$ This works the same way for others polynom, beware of multiple roots. $\endgroup$ Jul 3, 2013 at 13:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .