# Is Binet's formula for the Fibonacci numbers exact?

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.

-
Yes, it is exact. The irrational parts happen to cancel out. Have you tried plugging in a few values of $n$? – Tobias Kildetoft Jul 3 '13 at 9:53
Having irrational numbers in a formula producing integers is not anything strange. Just take e.g. $\sqrt{2}^2$. – Edvard Fagerholm Jul 3 '13 at 9:55
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? – awllower Jul 3 '13 at 10:15
It is exact. However, it is not a good way to calculate $F_n$ for very large $n$. – André Nicolas Jul 3 '13 at 13:21

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.

-
Maybe it should be Bennet's formula :). – Dan Rust Jul 3 '13 at 11:07
This is perfect, thank you. – N. McA. Jul 3 '13 at 14:48
@DanielRust When you time-travel names always get distorted... – Tobias Kienzler Jul 3 '13 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$.

-

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.

-
This is really neat but I have a perhaps very novice question: how do you relate recurrence relations and polynomials? – Cameron Williams Jul 3 '13 at 13:24
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. – Were_cat Jul 3 '13 at 13:36
This works the same way for others polynom, beware of multiple roots. – Were_cat Jul 3 '13 at 13:36
Oh that makes complete sense. Thanks! – Cameron Williams Jul 3 '13 at 13:38

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

-
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. – awllower Jul 4 '13 at 14:52
@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$ – Jack M Jul 4 '13 at 15:28
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. :) – awllower Jul 5 '13 at 4:59