Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
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
1  
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
3  
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

4 Answers 4

up vote 15 down vote accepted

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.

share|improve this answer
8  
Maybe it should be Bennet's formula :). –  Daniel 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$.

share|improve this answer

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.

share|improve this answer
    
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
1  
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. –  lmorin Jul 3 '13 at 13:36
1  
This works the same way for others polynom, beware of multiple roots. –  lmorin 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.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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