• Blog
• Projects
• Maths
• Akira Tanase

Finding a closed form expression for the Fibonacci Sequence

In this article, I will illustrate a number of ways in which we can find a closed form expression for the fibonacci sequence. Although elementary, many of these approaches can be seen across various fields of mathematics.

Background

We consider the following problem: Define a domino to be a $1\times2$ rectangle. In how many ways can a $n\times2$ rectangle be tiled by dominoes?

In fact, the number of ways(which I leave as an exercise to the reader to prove) can be denoted by the $n$th Fibonacci number, $F_n$, which satisifes the reccurence relation $F_{n}=F_{n-1}+F_{n-2}$ and $F_1=1$, $F_2=1$ for all integers $n\geq2$.

This example is one of many in mathematics in which we find the Fibonacci numbers cropping up. This article examines a number of ways to obtain Binet's formula for $F_n$: $$F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right).$$

Approach 1 - Algebra

We let the solutions to the auxiliary equation $x^2-x-1=0$ be $\alpha$ and $\beta$. We note that $\alpha+\beta=1$ and $\alpha\beta=-1$. Therefore: $$F_n=(\alpha+\beta)F_{n-1}-\alpha\beta F_{n-2}$$ Rearranging this gives us: $$F_n-\alpha F_{n-1}=\beta(F_n-\alpha F_{n-1})$$ Therefore, $$F_n-\alpha F_{n-1}=\beta^{n-2}(F_2-\alpha F_1)=\beta^{n-1}$$ Similarly, $$F_n-\beta F_{n-1}=\alpha^{n-2}(F_2-\beta F_1)=\alpha^{n-1}$$ Solving for $F_n$ gives us: $$ \begin{aligned} F_n&=\frac{\alpha^n-\beta^n}{\alpha-\beta}\\ &=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right) \end{aligned} $$ as desired.

Approach 2 - Generating Functions

Let $F_n$ denote the $n$th Fibonacci number. We define the generating function for the Fibonacci numbers, $G(x)$, by the following power series: $$G(x)=\sum_{n=0}^{\infty}{F_n x^n}=\sum_{n=1}^{\infty}{F_n x^n}$$ We observe that $$xG(x)=\sum_{n=1}^{\infty}{F_nx^n}=x\sum_{n=2}^{\infty}{F_{n-1}x^{n-1}}=\sum_{n=2}^{\infty}{F_{n-1}x^{n}}$$ and, $$x^2G(x)=x^2\sum_{n=0}^{\infty}{F_nx^n}=x^2\sum_{n=2}^{\infty}{F_{n-2}x^{n-2}}=\sum_{n=2}^{\infty}{F_{n-2}x^{n}}$$ As $F_n$ satisifies the relationship $F_n-F_{n-1}-F_{n-2}=0$. Therefore, we have: $$\begin{aligned} G(x)&=x+\sum_{n=2}^{\infty}{F_{n}x^{n}}\\ &=x+\sum_{n=2}^{\infty}{(F_{n-1}+F_{n-2})x^n}\\ &=x+\sum_{n=2}^{\infty}{F_{n-1}x^n}+\sum_{n=2}^{\infty}{F_{n-2}x^n}\\ &=x+xG(x)+x^2G(x) \end{aligned} $$ Rearranging in terms of $G(x)$ gives us: $$G(x)=\frac{x}{1-x-x^2}$$ We let the roots of the polynomial $1-x-x^2=0$ be $-\alpha$ and $-\beta$. This allowes us to rewrite $G(x)$: $$G(x)=-\frac{x}{(x+\alpha)(x+\beta)}=\frac{A}{x+\alpha}+\frac{B}{x+\beta}$$ Where $A=-\frac{\alpha}{\sqrt{5}}$ and $B=-\frac{\beta}{\sqrt{5}}$. Therefore: $$G(x)=\frac{1}{\sqrt{5}}\left(\frac{\alpha}{x+\alpha}-\frac{\beta}{x+\beta}\right)$$ We note that $\alpha\beta=-1$ and thus: $$\frac{\alpha}{x+\alpha}=\frac{1}{1+\frac{x}{\alpha}}=\frac{1}{1-\beta x}=\sum_{n=0}^{\infty}{\beta^n x^n}$$ Similarly: $$\frac{\beta}{x+\beta}=\sum_{n=0}^{\infty}{\alpha^n x^n}$$ This gives us: $$ \begin{aligned} G(x)&=\frac{1}{\sqrt{5}}\left(\frac{\alpha}{x+\alpha}-\frac{\beta}{x+\beta}\right)\\ &=\frac{1}{\sqrt{5}}{\left(\sum_{n=0}^{\infty}{\beta^n x^n}-\sum_{n=0}^{\infty}{\alpha^n x^n}\right)}\\ &=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}(\beta^n-\alpha^n)x^n\\ \end{aligned} $$ Substituting in the values of $\alpha$ and $\beta$ gives us: $$ F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right) $$ as desired.

Approach 3 - Matrix Exponentiation

We observe that: $$ \begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}=\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} \begin{pmatrix}F_n \\F_{n-1} \end{pmatrix} $$ Therefore: $$ \begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}=\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^n \begin{pmatrix}F_1 \\F_{0} \end{pmatrix} $$ We also note that $$ \begin{pmatrix}F_{n}\\F_{n-1}\end{pmatrix}=\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^n \begin{pmatrix}F_0 \\F_{-1} \end{pmatrix} $$ Setting $F_{-1}=1$, $F_0=0$, $F_1=1$, gives us: $$ \begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1}\end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n $$ Evaluating this gives us: $$ F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right) $$ as desired.

This method is well known in the computer science world, as it has time complexity of $O(\log(n))$ whereas the standard dynamic programming approach would be $O(n)$.