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$ 54 Answers
$\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$ 3 $\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$ $\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$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$ 4
