Euler-Binet Formula

Theorem

The Fibonacci numbers have a closed-form solution:

$\displaystyle F \left({n}\right) = \frac {\phi^n - \left({1 - \phi}\right)^n} {\sqrt 5} = \frac {\phi^n - \left({-1 / \phi}\right)^n} {\sqrt 5}$

where $\phi$ is the golden mean.

Putting $\hat \phi = 1 - \phi = -\dfrac 1 \phi$ this can be written:

$\displaystyle F \left({n}\right) = \frac {\phi^n - \hat \phi^n} {\sqrt 5}$

Proof

Proof by induction:

For all $n \in \N$, let $P \left({n}\right)$ be the proposition:

$\displaystyle F \left({n}\right) = \frac {\phi^n - \hat \phi^n} {\sqrt 5}$

Basis for the Induction

$P(0)$ is true, as this just says:

$\displaystyle \frac {\phi^0 - \hat \phi^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0 = F(0)$

$P(1)$ is the case, as follows from the following computation:

$\displaystyle \frac {\phi - \hat \phi} {\sqrt 5} = \frac {\left({ \frac {1 + \sqrt {5}} {2} }\right) - \left({ \frac {1 - \sqrt 5} {2} }\right)} {\sqrt 5} = \frac {\left({1 - 1}\right) + \left({ \sqrt 5 + \sqrt 5 }\right)} {2 \sqrt 5} = 1 = F \left({1}\right)$

This is our basis for the induction.

Induction Hypothesis

• Now we need to show that, if $P \left({n}\right)$ is true for all $0 \le n \le k+1$, then it logically follows that $P \left({k+2}\right)$ is true.

So this is our induction hypothesis:

$\displaystyle F \left({n}\right) = \frac {\phi^n - \hat \phi^n} {\sqrt 5}$ for all $0 \le n \le k+1$.

Then we need to show:

$\displaystyle F \left({k+2}\right) = \frac {\phi^{k+2} - \hat \phi^{k+2}} {\sqrt 5}$

Induction Step

This is our induction step:

We observe that we have the following two identities:

$\displaystyle \phi^2 = \left({ \frac {1 + \sqrt 5} {2} }\right)^2 = \frac 1 4 \left({6 + 2 \sqrt {5}}\right) = \frac {3 + 2 \sqrt 5} {2} = 1 + \phi$

$\displaystyle \hat \phi^2 = \left({ \frac {1 - \sqrt 5} {2} }\right)^2 = \frac 1 4 \left({6 - 2 \sqrt 5}\right) = \frac {3 - 2 \sqrt 5} {2} = 1 + \hat \phi$

Alternatively, this can be deduced from the definition of the golden mean: the fact that $\phi$ and $\hat \phi$ are the solutions to the quadratic equation $x^2 = x + 1$.

This means that we can compute:

	\(\displaystyle \)	\(\displaystyle \phi^{k+2} - \hat \phi^{k+2}\)	\(=\)	\(\displaystyle \left({ 1 + \phi }\right) \phi^k - \left({ 1 + \hat \phi }\right) \hat \phi^k\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({ \phi^k - \hat \phi^k }\right) + \left({ \phi^{k+1} - \hat \phi^{k+1} }\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sqrt 5 \left({ F \left({k}\right) + F \left({k+1}\right) }\right)\)	\(\displaystyle \)	by the induction hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sqrt 5 F \left({k+2}\right)\)	\(\displaystyle \)	from the definition of $F$

The result follows by the Second Principle of Mathematical Induction.

Therefore:

$\displaystyle \forall n \in \N: F \left({n}\right) = \frac {\phi^n - \hat \phi^n} {\sqrt 5}$

$\blacksquare$

Alternative Proof

This follows as a direct application of the first Binet form:

$U_n = m U_{n-1} + U_{n-2}$

where:

	\(\displaystyle \)	\(\displaystyle U_0\)	\(=\)	\(\displaystyle 0\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle U_1\)	\(=\)	\(\displaystyle 1\)	\(\displaystyle \)

has the closed-form solution:

$U_n = \dfrac {\alpha^n - \beta^n} {\Delta}$

where:

	\(\displaystyle \)	\(\displaystyle \Delta\)	\(=\)	\(\displaystyle \sqrt {m^2 + 4}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \alpha\)	\(=\)	\(\displaystyle \frac {m + \Delta} 2\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \beta\)	\(=\)	\(\displaystyle \frac {m - \Delta} 2\)	\(\displaystyle \)

where $m=1$.

$\blacksquare$

Source of Name

This entry was named for Jacques Philippe Marie Binet and Leonhard Paul Euler.

It is also known as Binet's Formula.

Binet derived it in 1843, but it was already known to Euler, de Moivre and Daniel Bernoulli over a century earlier.

However, it was Binet who derived the more general Binet Form of which this is an elementary application.