Main Index Number Theory Sequences Recurrent sequences Linear recurrent sequences Binary recurrent sequences Lucas’ sequences Fibonacci Numbers
Subject Index
comment on the page

Binet’s formula

It can be easily proved by induction that

Theorem. We have

((1 + 5^(1/2))/2)^(n - 2) <= F(n) <= ((1 + 5^(1/2))/2)^(n - 1)

for all positive integers typeset structure.

Proof.

Let typeset structure. Then the right inequality we get using
typeset structure,
since typeset structure, where typeset structure.   QED

The following closed form expression for Fibonacci numbers was rediscovered very often (see below):

Theorem.  (Binet’s formula)  The typeset structureth term of the Fibonacci series is given be the formula

F(n) = 1/5^(1/2) (((1 + 5^(1/2))/2)^n - ((1 - 5^(1/2))/2)^n) .(1)

1st proof:

The partial fraction decomposition of the right hand side of  the generating function typeset structure     is

                                           -1 + Sqrt[5]                  -1 - Sqrt[5] FormBox[ ... orm]                                    Sqrt[5] (-1 + Sqrt[5] - 2 z)   Sqrt[5] (1 + Sqrt[5] + 2 z)

This in turn can be modified to the form
typeset structure.
Expanding the factors into power series finishes the proof of the Theorem.  

2nd proof:

If  typeset structure and typeset structure, then typeset structure, typeset structure, and typeset structure. Therefore
typeset structure.
In a similar way we get typeset structure. subtraction both identities yields typeset structureand Binet’s formula follows.  

3rd proof:

The formula is trivially true for typeset structure.  The formula is also true for typeset structure for typeset structure. Thus, it sufficient to prove that the expression on the right hand side of the formula obeys the same recursive relation as the Fibonacci numbers, i.e. that   

(φ^n - (Overscript[φ, _])^n)/5^(1/2) + (φ^(n + 1) - (Overscript[φ, _])^(n + 1))/5^(1/2) = (φ^(n + 2) - (Overscript[φ, _])^(n + 2))/5^(1/2),

or in other words that

                                            n                                                  ... 66;]], ), Cell[BoxData[ ], TextSuperscript, SingleLetterItalics - False], ).}]], TraditionalForm]

The expression in parentheses on both sides vanishes due to the fact that typeset structure and typeset structure are roots of typeset structure.  QED

We can also write

F(n) = 1/5^(1/2) (φ^n - (-1/φ)^n) = (φ^n - (Overscript[φ, _])^n)/(φ - Overscript[φ, _]) .

Like many results in mathematics it is often not the original discoverer who gets the glory of having their name attached to the result.  J. P. M. Binet (1786-1856) published  [1]  this result now known as the Binet’s formula in 1843 although the result was known earlier. It seems that Daniel Bernoulli (1700-1782) discovered and proved this formula in 1726 ([2], §7). Two years later also Euler mentioned the formula in a letter to Bernoulli, but he published  [3] it only in 1765.  A. de Moivre (1667-1754)  published it in the general form in the first systematic account of linear recurrences ([4], pp. 26-42) and it seems that Binet’s formula was known to him already in 1718 [5]. From the later authors let us mention for instance E.Lucas who may rediscovered it but did not report it before 1876.  

For an animation of Binet’s formula visit http://members.aol.com/kwpapke/Binet.html.

The next result goes back to de Moivre:

Corollary. The typeset structureth Fibonacci number is the positive integer nearest to

1/5^(1/2) ((1 + 5^(1/2))/2)^n .(2)

Proof.

If  typeset structure and typeset structure, then typeset structure. Since typeset structure, then typeset structure and thus the corresponding part of Binet’s formula approaches typeset structure.  QED

The above theorem shows the exponential growth rate of typeset structure. Plotting the logarithm typeset structure we get a linear function of typeset structure.

[Graphics:HTMLFiles/BinetFormula_40.gif]

de Moivre’s formula (2)  says that the limit of the ration of two adjacent Fibonacci numbers is none other than the Euclidean golden ratio 0.618. In fact typeset structure, typeset structure, typeset structure, .... the further it goes, the closer the proportion of two Fibonacci numbers to 0.618 the golden mean. This follows using Cassini’s formula , which says that typeset structure and typeset structure are close to each other and the previous Corollary shows that the ratio approaches typeset structure.  This fact was first pointed out by Johannes Kepler  (1571-1630).  Kepler in his small monograph Strena seu de Nive Sexangula (A New Year Gift : On Hexagonal Snow)1 (1611) [6] rediscovered Fibonacci sequence, their recurrence property and made the remarkable discover about the ratios of consecutive terms of the Fibonacci sequence.23  He expressed the opinion the seminal faculty (that is the reproductive process)  is developed in a way analogous to this proportion which perpetuates itself. This is a farsighted insight as it implies that Fibonacci numbers and specially the number typeset structure play a fundamental role to the biological processes of self replication. The insight was overlooked and in nineteenth century again rediscovered by biologists  in the study of phyllotaxis leaf arrangements in plants.

[Graphics:HTMLFiles/BinetFormula_51.gif]

The limit as a typeset structure of the ratio of successive Fibonacci numbers is the golden ratio.

Corollary. We have typeset structure.

The following identity can be proved by induction using equation (1), since it is true for typeset structure and typeset structure:

F(n + 1) = (1 + 5^(1/2))/2 F(n) + ((1 - 5^(1/2))/2)^n(3)

Notes

1 This booklet is mainly concerned with the packing together of circles in a plane and spheres in space.  It also describes the structure of flowers in quincuncial arrangements (i.e. arrangments of five objects at each of the four corners of a square).

2 J.Kepler: Vom sechseckigen Schnee, Leipzig 1987, p.34-35: Die fünfzähligen regelmässigen Körper und ihr Ursprung aus der göttlichen Proportion (goldener Schnitt)
Es gibt zwei regelmässige Körper, das Dodekaeder und das Ikosaeder, die such aus dem Grundplan des Fünfecks ergeben. Jenes wird von Fünfecken umschlossen, dieses von gleichseitigen Dreiecken, aber stets sind fünf in der Form eines Fünfeks angeordnet. Die Konstruktion beider Körper, jedoch vor allem die des Fünfecks selbst, ist ohne jene Proportion nicht durchführbar, die die heutigen Mathematiker die göttliche nennen. Diese aber ist in ihrem Aufbau so, dass die beiden kleineren Glieder einer stetigen Proportion zusammen das dritte Glied ergeben, und so bildet immer die Summe zweier vorhergehender Glieder das folgende Glied. Dabei kann die gleiche Proportion ins Unendliche fortsgesetzt werden. In Zahlen kann man das Ergebnis nicht vollständig ausdrücken. Je weiter wir uns von der Einheit entfernen, desto besser wird die Annähering. Es seien die beiden kleinsten Zahlen gegeben 1 und 1, die Du als ungleich betrachten musst. Wenn Du sie addierst, dann ergeben 2. Dazu die (grössere) 1 addiert, ergibt 3, nun 2 dazu gezählt, ergibt 5. Addiert man weiter 3 dazu, so erhältst Du 8, dann 5 hinzugeben, ergibt 13, 8 dazu addiert, ergibt 21. Es verhält sich nun 5 zu 8 annähernd wie 8 zu 13 und 8 zu 13 annähernd wie 13 zu 21.
Entsprechend einer Analogie dieser sich selbst fortsetzenden Proportion ist, so glauch ich, das Zeugungvermögen versinnbildlicht. So wird die Blütte dem Zeugungsvermögen für die Früchte deutlich ein fünfzackiges Fähnlein vorangetragen. Ich übergebe manche Gedanken, die zur Bestärkung dieser Ansicht in einer ergötzlichen Betrachtung hinzugefügt werden könnten. Doch dafür braiche ich einen eigenen Platz. Hier hatte ich diese Gedanken nur als ein Beispiel aufgenommen, um zur Erforschung der secheckigen gestalt des Schnees besser geübt und vorbereitet zu sein.

3 Kepler develops similar ideas also in his  Weltharmonik, pp.165 - 166.

References

[1]  Binet, J. P. (1843). Mémoire sur l’intégration des équations linéaires aux différences finies, d’un ordre quelconque, à coefficients variables. Comptes Rendus hebdomadaires des séances de l’Académie des Sciences (Paris), 17, 559-567.

[2]  Bernoulli, D. (1728). Comment. Acad. Sci. Petrop., 3, 85-100.

[3]  Euler, L. (1765). Observationes analyticae. Novi commentarii ascaemiae scientiarum imperialis Petropolotanae, 11, 124-143.

[4]  de Moivre, A. (1730). Miscellanea analytica de seriebus et quadraturis . London.

[5]  de Moivre, A. (1722).Philos. Trans., 32, 162-178.

[6]  Kepler, J. (1987). Vom sechseckigen Schnee (Strena seu de Nive sexangula). Leipzig: Akademische Verlagsgeselschaft, Geest & Portig K.-G..

Cite this web-page as:

Štefan Porubský: Binet’s Formula.

Page created  .