Main Index
Number Theory
Sequences
Recurrent sequences
Linear recurrent sequences
Binary recurrent sequences
Lucas’ sequences
Fibonacci Numbers
Subject Index
comment on the page
It can be easily proved by induction that
Theorem. We have
for all positive integers .
Proof.
Let . Then the right inequality we get using
,
since , where . QED
The following closed form expression for Fibonacci numbers was rediscovered very often (see below):
Theorem. (Binet’s formula) The th term of the Fibonacci series is given be the formula
(1) |
1st proof:
The partial fraction decomposition of the right hand side of the generating function is
This in turn can be modified to the form
.
Expanding the factors into power series finishes the proof of the Theorem.
2nd proof:
If and , then , , and . Therefore
.
In a similar way we get . subtraction both identities yields and Binet’s formula follows.
3rd proof:
The formula is trivially true for . The formula is also true for for . 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
or in other words that
The expression in parentheses on both sides vanishes due to the fact that and are roots of . QED
We can also write
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 th Fibonacci number is the positive integer nearest to
(2) |
Proof.
If and , then . Since , then and thus the corresponding part of Binet’s formula approaches . QED
The above theorem shows the exponential growth rate of . Plotting the logarithm we get a linear function of .
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 , , , .... 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 and are close to each other and the previous Corollary shows that the ratio approaches . 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 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.
The limit as a of the ratio of successive Fibonacci numbers is the golden ratio.
Corollary. We have .
The following identity can be proved by induction using equation (1), since it is true for and :
(3) |
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. |
[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.