We use MathJax
The explicit formula for the terms of the Fibonacci sequence, $F_n=\dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$. has been named in honor of the eighteenth century French mathematician Jacques Binet, although he was not the first to use it. Typically, the formula is proven as a special case of a more general study of sequences in number theory. However, we shall relate the formula to a geometric series.
Lemma 1: Let $F_n$ represent the $n$th term of the Fibonacci sequence, and define $E_n = F_n - \left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-1}$. Then $E_n = \left(\dfrac{1-\sqrt{5}}{2}\right)^{n-1}$.
Proof.
| Let $F_n$ represent the $n$th term of the Fibonacci sequence. Define $E_n = F_n - \left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-1}$. Then we have the following implications: | We must begin with the hypothesis of the lemma. |
| $E_n = (F_{n-1}+F_{n-2}) - \left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-1}$ | We apply a number of algebraic properties, beginning with substitution of the recursive formula of $F_n$. |
| $E_n = \left(1-\dfrac{1+\sqrt{5}}{2}\right)F_{n-1}+F_{n-2}$ | We collect like terms ... |
| $E_n = \left(\dfrac{1-\sqrt{5}}{2}\right) \left[F_{n-1}+\left(\dfrac{2}{1-\sqrt{5}}\right)F_{n-2}\right]$ | ... and simplify the expression in parentheses. Inside the brackets, we introduce its reciprocal as a coefficient of $F_{n-2}$ by "factoring". |
| $E_n = \left(\dfrac{1-\sqrt{5}}{2}\right)\left[F_{n-1}-\left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-2}\right]$ | Here we rationalize the denominator. |
| But the result in brackets is the error term for $n-1$. That is: $E_n = \left(\dfrac{1-\sqrt{5}}{2}\right)E_{n-1}$ | We now have a recursive formula for $E_n$. |
| By repeated use of this result, we can obtain: $E_n = \left(\dfrac{1-\sqrt{5}}{2}\right)^{n-2}E_2$ | In other words, $E_{n-1}$ can be written in terms of $E_{n-2}$, which can be written in terms of $E_{n-3}$, et cetera, until we reach $E_2$. |
| And applying the definition of $E_n$ to $E_2$ gives: $E_n = \left(\dfrac{1-\sqrt{5}}{2}\right)^{n-2} \left[F_2-\left(\dfrac{1+\sqrt{5}}{2}\right) F_1\right]$ $E_n = \left(\dfrac{1-\sqrt{5}}{2}\right)^{n-2}\left[1-\left(\dfrac{1+\sqrt{5}}{2}\right)\right]$ |
Then we substitute values for $F_1$ and $F_2$. |
| $E_n = \left(\dfrac{1-\sqrt{5}}{2}\right)^{n-1}$ | And lastly, we simplify the result. |
It is not obvious that there should be a connection between Fibonacci sequences and geometric series. Yet once this has been achieved, we will be able to use formulas for geometric series to write our proof of Binet's Formula.
Lemma 2: Each term of the Fibonacci sequence is the sum of a finite geometric series with first term $\left(\dfrac{1+\sqrt{5}}{2}\right)^{n-1}$ and ratio $\dfrac{1-\sqrt{5}}{1+\sqrt{5}}$.
Proof.
| Let $F_n$ represent the $n$th term of the Fibonacci sequence, and define $E_n = F_n - \left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-1}$. | Since the lemma implies a statement about the Fibonacci sequence, we begin by defining $F_n$. In order to use the result of the first lemma, we also define $E_n$. |
| Then $F_n=\left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-1} + E_n$, so $F_n=\left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-1} + \left(\dfrac{1-\sqrt{5}}{2}\right)^{n-1}$ | We solve the definition of $E_n$ for the value of $F_n$, then substitute the result of the first lemma. |
| Since we have written $F_n$ in terms of $F_{n-1}$, we can now write $F_{n-1}$ in terms of $F_{n-2}$, and so on. We get: $F_n=\left(\dfrac{1+\sqrt{5}}{2}\right)\left[\left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-2}+\left(\dfrac{1-\sqrt{5}}{2}\right)^{n-2}\right]+\left(\dfrac{1-\sqrt{5}}{2}\right)^{n-1}$ |
We can now use this result recursively, substituting the previous equation into itself, ... |
| $F_n=\left(\dfrac{1+\sqrt{5}}{2}\right)\left[\left(\dfrac{1+\sqrt{5}}{2}\right)\left[\left(\dfrac{1+\sqrt{5}}{2}\right)F_{n-3}\right.\right.$ $\qquad\qquad\qquad\qquad \left.\left.+\left(\dfrac{1-\sqrt{5}}{2}\right)^{n-3}\right]+\left(\dfrac{1-\sqrt{5}}{2}\right)^{n-2}\right]+\left(\dfrac{1-\sqrt{5}}{2}\right)^{n-1}$ |
... and again into itself. We begin to recognize a pattern developing ... |
| After $n-2$ substitutions, and recalling $F_1=1$, we have: $F_n=\left(\dfrac{1+\sqrt{5}}{2}\right)^{n-1} + \left(\dfrac{1+\sqrt{5}}{2}\right)^{n-2}\left(\dfrac{1-\sqrt{5}}{2}\right) + \ldots$ $\qquad\qquad\qquad\qquad + \left(\dfrac{1+\sqrt{5}}{2}\right)\left(\dfrac{1-\sqrt{5}}{2}\right)^{n-2} + \left(\dfrac{1-\sqrt{5}}{2}\right)^{n-1}$ |
... and here are the terms that result. |
| But the $n$ terms on the right hand side of the equation form a geometric sequence with ratio $\dfrac{1-\sqrt{5}}{1+\sqrt{5}}$. Since the right hand side has the proper first term, and $F_n$ is the sum of those terms, we have shown that each term of $F_n$ is the sum of a finite geometric series with the characteristics claimed in the statement of the lemma. | Note that the ratio of consecutive terms is $\dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^{n-k} \left(\frac{1-\sqrt{5}}{2}\right)^{k-1}} {\left(\frac{1+\sqrt{5}}{2}\right)^{n-k+1}\left(\frac{1-\sqrt{5}}{2}\right)^{k-2}} = \dfrac{1-\sqrt{5}}{1+\sqrt{5}}$. |
The first lemma was used to prove the second lemma, and now we can use the second lemma to establish Binet's Formula.
Theorem. If $F_n$ is the $n$th term of a Fibonacci sequence, then $F_n = \dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$.
Proof.
| Let $F_n$ be the $n$th term of a Fibonacci sequence. Then by the second lemma, $F_n$ is the sum of a finite geometric series with first term $\left(\dfrac{1+\sqrt{5}}{2}\right)^{n-1}$ and ratio $\dfrac{1-\sqrt{5}}{1+\sqrt{5}}$. | We begin with the hypothesis of the theorem, and immediately use the result of the second lemma. |
| Since the formula for the sum of a finite geometric sequence is $\sum\limits_{k=1}^{n} a_k = \dfrac{a_1 (1-r^n)}{1-r}$ we have $F_n = \dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}\left[1-\left(\frac{1-\sqrt{5}}{1+\sqrt{5}}\right)^n\right]}{\left(1-\frac{1-\sqrt{5}}{1+\sqrt{5}}\right)}$ | Using the formula for the sum of a finite geometric sequence, we substitute. |
| Simplifying this result, we obtain: $F_n=\dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1} - \left(\frac{1-\sqrt{5}}{1+\sqrt{5}}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}{\left(\frac{2\sqrt{5}}{1+\sqrt{5}}\right)}$ |
We distribute in the numerator, and combine terms in the denominator. |
| $F_n=\left(\dfrac{1+\sqrt{5}}{2\sqrt{5}}\right)\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n-1} - \left(\dfrac{1-\sqrt{5}}{1+\sqrt{5}}\right)\left(\dfrac{1-\sqrt{5}}{2}\right)^{n-1}\right]$ | We then multiply the numerator by the reciprocal of the denominator. |
| $F_n=\dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$ | After distributing, Binet's Formula is obtained. |