987/610

Calculation

Closed form expression

Like every sequence defined by linear recurrence, the Fibonacci numbers have a closed-form solution. It has become known as Binet‘s formula, even though it was already known by Abraham de Moivre:^[11]

$F\left(n\right) = {{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}={{\varphi^n-(-1/\varphi)^{n}} \over {\sqrt 5}}\, ,$

where

$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\dots\,$

is the golden ratio (sequence A001622 in OEIS).

That

$1-\varphi=-1/\varphi,$

follows from the defining equation above.

The Fibonacci recursion

$F(n+2)-F(n+1)-F(n)=0\,$

is similar to the defining equation of the golden ratio in the form

$x^2-x-1=0,\,$

which is also known as the generating polynomial of the recursion.

[edit]Proof by induction

Any root of the equation above satisfies $\begin{matrix}x^2=x+1,\end{matrix}\,$ and multiplying by $x^{n-1}\,$ shows:

$x^{n+1} = x^n + x^{n-1}\,$

By definition $\varphi\,$ is a root of the equation, and the other root is $1-\varphi\,=-1 / \varphi\, .$ Therefore:

$\varphi^{n+1} = \varphi^n + \varphi^{n-1}\,$

and

$(1-\varphi)^{n+1} = (1-\varphi)^n + (1-\varphi)^{n-1}\, .$

Both $\varphi^{n}$ and $(1-\varphi)^{n}=(-1/\varphi)^{n}$ are geometric series (for n = 1, 2, 3, …) that satisfy the Fibonacci recursion. The first series grows exponentially; the second exponentially tends to zero, with alternating signs. Because the Fibonacci recursion is linear, any linear combination of these two series will also satisfy the recursion. These linear combinations form a two-dimensional linear vector space; the original Fibonacci sequence can be found in this space.

Linear combinations of series $\varphi^{n}$ and $(1-\varphi)^{n}$ , with coefficients a and b, can be defined by

$F_{a,b}(n) = a\varphi^n+b(1-\varphi)^n$ for any real $a,b\, .$

All thus-defined series satisfy the Fibonacci recursion

$\begin{align} F_{a,b}(n+1) &= a\varphi^{n+1}+b(1-\varphi)^{n+1} \\ &=a(\varphi^{n}+\varphi^{n-1})+b((1-\varphi)^{n}+(1-\varphi)^{n-1}) \\ &=a{\varphi^{n}+b(1-\varphi)^{n}}+a{\varphi^{n-1}+b(1-\varphi)^{n-1}} \\ &=F_{a,b}(n)+F_{a,b}(n-1)\,. \end{align}$

Requiring that F_a,b(0) = 0 and F_a,b(1) = 1 yields $a=1/\sqrt 5$ and $b=-1/\sqrt 5$ , resulting in the formula of Binet we started with. It has been shown that this formula satisfies the Fibonacci recursion. Furthermore, an explicit check can be made:

$F_{a,b}(0)=\frac{1}{\sqrt 5}-\frac{1}{\sqrt 5}=0\,\!$

and

$F_{a,b}(1)=\frac{\varphi}{\sqrt 5}-\frac{(1-\varphi)}{\sqrt 5}=\frac{-1+2\varphi}{\sqrt 5}=\frac{-1+(1+\sqrt 5)}{\sqrt 5}=1,$

establishing the base cases of the induction, proving that

$F(n)={{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}$ for all $n\, .$

Therefore, for any two starting values, a combination a,b can be found such that the function $F_{a,b}(n)\,$ is the exact closed formula for the series.

[edit]Computation by rounding

Since $\begin{matrix}|1-\varphi|^n/\sqrt 5 < 1/2\end{matrix}$ for all $n\geq 0$ , the number F(n) is the closest integer to $\varphi^n/\sqrt 5\, .$ Therefore it can be found by rounding, or in terms of the floor function:

$F(n)=\bigg\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\bigg\rfloor,\ n \geq 0.$

Similarly, if you already know that the number F is a Fibonacci number, you can determine its index within the sequence by

$n = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5}\right) + \frac{1}{2} \bigg\rfloor$

[edit]Limit of consecutive quotients

Johannes Kepler observed that the ratio of consecutive Fibonacci numbers converges. He wrote that “as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost”, and concluded that the limit approaches the golden ratio $\varphi\,$ .^[12]

$\lim_{n\to\infty}\frac{F(n+1)}{F(n)}=\varphi,$

This convergence does not depend on the starting values chosen, excluding 0, 0. For example, the initial values 19 and 31 generate the sequence 19, 31, 50, 81, 131, 212, 343, 555 … etc. The ratio of consecutive terms in this sequence shows the same convergence towards the golden ratio.

[edit]Proof

In brief, Fibonacci numbers are approximately exponential: $F_{a,b}(n) \approx k\phi^n,$ where the constant depends on starting values – as the remaining term in the exact formula for the Fibonacci numbers becomes exponentially close to zero as n grows. Taking the ratio yields $F(n+1)/F(n) \approx (k\phi^{n+1})/(k\phi^n) = \phi.$

More formally, it must always follow from the explicit formula that for any real $a \ne 0, \, b \ne 0 \,$

$\begin{align} \lim_{n\to\infty}\frac{F_{a,b}(n+1)}{F_{a,b}(n)} &= \lim_{n\to\infty}\frac{a\varphi^{n+1}-b(1-\varphi)^{n+1}}{a\varphi^n-b(1-\varphi)^n} \\ &= \lim_{n\to\infty}\frac{a\varphi-b(1-\varphi)(\frac{1-\varphi}{\varphi})^n}{a-b(\frac{1-\varphi}{\varphi})^n} \\ &= \varphi \end{align}$

because $\bigl|{\tfrac{1-\varphi}{\varphi}}\bigr| < 1$ and thus $\lim_{n\to\infty}\left(\tfrac{1-\varphi}{\varphi}\right)^n=0 .$

[edit]Decomposition of powers of the golden ratio

Since the golden ratio satisfies the equation

$\varphi^2=\varphi+1,\,$

this expression can be used to decompose higher powers $\varphi^n$ as a linear function of lower powers, which in turn can be decomposed all the way down to a linear combination of $\varphi\,$ and 1. The resulting recurrence relationships yield Fibonacci numbers as the linear coefficients:

$\varphi^n=F(n)\varphi+F(n-1).$

This expression is also true for $n \, <\, 1 \,$ if the Fibonacci sequence $F(n) \,$ is extended to negative integers using the Fibonacci rule $F(n) = F(n-1) + F(n-2) . \,$

[edit]Matrix form

A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is

${F_{k+2} \choose F_{k+1}} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} {F_{k+1} \choose F_{k}}$

$\vec F_{k+1} = A \vec F_{k}\,.$

The eigenvalues of the matrix A are $\varphi\,\!$ and $(1-\varphi)\,\!$ , and the elements of the eigenvectors of A, ${\varphi \choose 1}$ and ${1 \choose -\varphi}$ , are in the ratios $\varphi\,\!$ and $(1-\varphi\,\!).$ Using these facts, and the properties of eigenvalues, we can derive a direct formula for the nth element in the fibonacci series:

$F_{n} = \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$

This matrix has a determinant of −1, and thus it is a 2×2 unimodular matrix. This property can be understood in terms of the continued fraction representation for the golden ratio:

$\varphi =1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{\;\;\ddots\,}}} \;.$

The Fibonacci numbers occur as the ratio of successive convergents of the continued fraction for $\varphi\,\!$ , and the matrix formed from successive convergents of any continued fraction has a determinant of +1 or −1.

The matrix representation gives the following closed expression for the Fibonacci numbers:

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.$

Taking the determinant of both sides of this equation yields Cassini’s identity

$(-1)^n = F_{n+1}F_{n-1} - F_n^2\,.$

Additionally, since AⁿA^m = A^{m + n} for any square matrix A, the following identities can be derived:

${F_m}{F_n} + {F_{m-1}}{F_{n-1}} = F_{m+n-1}\,,$

$F_{n+1}F_{m} + F_n F_{m-1} = F_{m+n}\,.$

In particular, with m = n,

$F_{2n-1} = F_n^2 + F_{n-1}^2\,,$

$F_{2n} = (F_{n-1}+F_{n+1})F_n = (2F_{n-1}+F_n)F_n\,.$

For another way to derive the F_{2n + k} formulas see the “EWD note” by Dijkstra.^[13]