A Closed Form of the Fibonacci Sequence
A Closed Form of the Fibonacci Sequence
We looked at The Fibonacci Sequence $\{ f_n \}$ defined recursively by $f_1 = 1$, $f_2 = 1$, and for $n \geq 3$:
(1)\begin{align} \quad f_n = f_{n-1} + f_{n-2} \end{align}
The formula above is recursive relation and in order to compute $f_n$ we must be able to computer $f_{n-1}$ and $f_{n-2}$. For large $n$, the computation of both of these values can be equally as tedious. Instead, it would be nice if a closed form formula for the sequence of numbers in the Fibonacci sequence existed. Fortunately, a closed form formula does exist and is given for $n \in \{ 1, 2, ... \}$ by:
(2)\begin{align} \quad f_n = \frac{1}{\sqrt{5}} \left ( \left ( \frac{1 + \sqrt{5}}{2} \right )^{n} - \left (\frac{1 - \sqrt{5}}{2} \right )^{n} \right ) \end{align}
We will prove this formula in the following theorem.
Theorem 1: For each $n \in \{ 1, 2, ... \}$ the $n^{\mathrm{th}}$ Fibonacci number is given by $f_n = \displaystyle{\frac{1}{\sqrt{5}} \left ( \left ( \frac{1 + \sqrt{5}}{2} \right )^{n} - \left (\frac{1 - \sqrt{5}}{2} \right )^{n} \right )}$. |
- Proof: For $x \in \mathbb{R}$ define the function $F(x)$ as the following infinite series:
\begin{align} \quad F(x) = f_1 + f_2x + f_3x^2 + ... + f_nx^{n-1} + f_{n+1}x^n + ... = \sum_{i=0}^{\infty} f_{i+1}x^i \end{align}
- We want to first determine that this positive series converges for some $x \in \mathbb{R}$. We first note that for all $n \in \{1, 2, ... \}$ we have that $f_n < 2^n$. We can prove this by induction. For $n = 0$ we have that $1 = f_1 < 2^1 = 2$ which is true. For some $n > 0$ assume that $f_n < 2^n$. We want to show that then $f_{n+1} < 2^{n+1}$. We have that
\begin{align} \quad f_{n+1} = f_n + f_{n-1} < 2^n + 2^{n-1} = 2^{n-1}(2 + 1) = 3 \cdot 2^{n-1} < 4 \cdot 2^{n-1} = 2^2 \cdot 2^{n-1} = 2^{n+1} \end{align}
- Now consider the series $\sum_{i=0}^{\infty} 2^{i+1} x^i$. In applying the ratio test for the convergence of positive series we have that $\lim_{i \to \infty} \biggr \lvert \frac{2^{i+2}}{2^{i+1}} \biggr \rvert = 2$. Therefore the radius of convergence for this series is $\frac{1}{2}$ so this series converges for $\mid x \mid < \frac{1}{2}$.
- Now since $0 < \sum_{i=0}^{\infty} f_{i+1}x^i < \sum_{i=0}^{\infty} 2^{i+1}x^i$ we conclude by the comparison test that the series $\sum_{i=0}^{\infty} f_{i+1}x^i$ must also converge for $\mid x \mid < \frac{1}{2}$.
- Now consider the products $xF(x)$ and $x^2F(x)$:
\begin{align} \quad xF(x) = f_1x + f_2x^2 + f_3x^3 + ... + f_nx^n + f_{n+1}x^{n+1} + ... = \sum_{i=0}^{\infty} f_{i+1}x^{i+1} \end{align}
(6)
\begin{align} \quad x^2F(x) = f_1x^2 + f_2x^3 + f_3x^4 + ... + f_nx^{n+1} + f_{n+1}x^{n+2} + ... = \sum_{i=0}^{\infty} f_{i+1}x^{i+2} \end{align}
- We now simplify the difference $F(x) - xF(x) - x^2F(x)$:
\begin{align} \quad (1 - x - x^2)F(x) = f_1 + (f_2 - f_1)x + (f_3 - f_2 - f_1)x^2 + (f_4 - f_3 - f_2)x^3 + ... + (f_{n+1} - f_n - f_{n-1})x^n + ... \end{align}
- Notice that $f_1 = f_2 = 1$ so $f_2 - f_1 =0$. Also, since for $n \geq 3$ we have that $f_n = f_{n-1} + f_{n-2}$ then $f_3 - f_2 - f_1 = 0$, $f_4 - f_3 - f_2 = 0$, …, $f_{n+1} - f_n - f_{n-1} = 0$. Therefore:
\begin{align} \quad (1 - x - x^2)F(x) = f_1 \\ \quad (1 - x - x^2)F(x) = 1 \\ \quad F(x) = \frac{1}{1 - x - x^2} \end{align}
- Now consider the polynomial $p(x) = 1 - x - x^2$. Using the quadratic formula we obtain the the roots of $p$ are:
\begin{align} \quad x = \frac{1 \pm \sqrt{1 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2} \end{align}
- Let $\phi_1 = \frac{1 + \sqrt{5}}{2}$ and $\phi_2 = \frac{1 - \sqrt{5}}{2}$. Then using partial fractions we can rewrite $F(x)$ as:
\begin{align} \quad F(x) = \frac{1}{1 - x - x^2} = \frac{A}{1 - \phi_1x} + \frac{B}{1 - \phi_2x} \end{align}
- We will find that $A = \frac{1}{\sqrt{5}} \phi_1$ and $B = - \frac{1}{\sqrt{5}} \phi_2$. Therefore:
\begin{align} \quad F(x) = \frac{1}{1 - x - x^2} = \frac{1}{\sqrt{5}} \left ( \frac{\phi_1}{1 - \phi_1x} - \frac{\phi_2}{1 - \phi_2x} \right ) \end{align}
- Since $\frac{1}{1 - ax} = \sum_{i=0}^{\infty} (ax)^n$ for $\mid x \mid < 1$ we get that:
\begin{align} \quad F(x) = \frac{1}{\sqrt{5}} \left ( \phi_1\sum_{i=0}^{\infty} (\phi_1 x)^i - \phi_2 \sum_{i=0}^{\infty} (\phi_2 x)^i \right ) \\ \quad F(x) = \sum_{i=0}^{\infty} \frac{1}{\sqrt{5}} \left (\phi_1^{i+1} - \phi_2^{i+1} \right )x^i \end{align}
- Thus $\sum_{i=0}^{\infty} f_{i+1} x^i = \sum_{i=0}^{\infty} \frac{1}{\sqrt{5}} \left (\phi_1^{i+1} - \phi_2^{i+1} \right )x^i$ so then $f_{n+1} = \frac{1}{\sqrt{5}}(\phi_1^{n+1} - \phi_2^{n+1})$ or equivalently:
\begin{align} \quad f_n = \frac{1}{\sqrt{5}} \left ( \left ( \frac{1 + \sqrt{5}}{2}\right )^n - \left (\frac{1 - \sqrt{5}}{2} \right)^n \right ) \quad \blacksquare \end{align}