« an ‘official’ Putnam sample problem
Meta Category setup »

Binet’s Formula

I’ve been working through proving some identities for the Fibonacci numbers, all of which have so far been provable using induction:

  1. f_0 + f_1 + \ldots + f_{n-1} = f_{n+1} - 1 for n \geq 1
  2. f_0 + f_2 + \ldots + f_{2n} = f_{2n+1} for n \geq 0
  3. f_1 + f_3 + \ldots + f_{2n-1} = f_{2n} - 1 for n \geq 1
  4. for n \geq 1, the successive Fibonacci numbers f_n and f_{n+1} are co-prime.
  5. f_{n+m} = f_{n-1}f_{m-1} + f_n f_m for n,m\geq 1
  6. if m | n, then f_{m-1} | f_{n-1}
  7. f_{n+1} f_{n-1} - f_n^2 = (-1)^{n+1}

However, I’m stuck on proving Binet’s formula,

\displaystyle f_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right],

I’m pretty sure this isn’t easily provable by induction, but it probably can be proven more easily than from scratch by using the identities above. I’ve seen it done before, e.g. in TAOCP, but I don’t remember how it was done. Besides, that would be cheating.

This entry was posted on Saturday, January 22nd, 2005 at 10:17 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to “Binet’s Formula”

  1. didier Says:
    January 22nd, 2005 at 11:46 pm

    Try solving the recurrence realtionship, i.e x^n = a*x^(n-1) + b*x^(n-2) for x, where a and b are constants. Then find a and b by using the fact that f_0 = 0 and f_1 = 1.

  2. Alex Says:
    January 23rd, 2005 at 5:22 pm

    Thanks for the tip. Actually, today I realized something similar about the generalized Fibonacci series: f_n = a f_{n-1} + b f_{n-2} . If \alpha is a root of the equation x^2 = ax + b , \alpha satisfies the recursion relation given. So does the sum of the roots, so I’m thinking that’s where the Binet formula comes from.

  3. tpc Says:
    February 2nd, 2005 at 10:56 pm

    Hi, actually Binet’s formula yields very easily to induction, the key being x^2-x-1=0. See Knuth et al’s Concrete Mathematics, very insightful.

  4. Harald Says:
    June 18th, 2005 at 5:42 pm

    Hi, try to proof Binet’s formula by going the way, the formula originally comes from. See my website for the proof; a comment would be kind. :-)

Leave a Reply