NOTE & BLOG

In Fibonacci's work The Book of Calculation the Fibonacci sequence is defined as follows:

It can be proven that its closed-form formula is:

With my current knowledge, I can only comprehend two proof methods as follows:

Matrix Method

Let's first discuss the case when $n \geq 2$. Our goal now is to transform the recurrence formula of the Fibonacci sequence into matrix form. How can we do that? We can approach it from the perspective of a system of linear equations.

First, here is what we know:

We can add the equation $F_{n-1} + 0 \cdot F_{n-2} = F_{n-1}$ to form a system of linear equations:

This can be transformed into matrix form as follows:

Now, we can iterate this process:

We denote the matrix $\boldsymbol{A} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$. So, the problem becomes finding $\boldsymbol{A}^{n-1}$, and then we can calculate $\boldsymbol{A}^{n}$ and replace all instances of $n$ with $n-1$.

Notice that matrix $\boldsymbol{A}$ is a square matrix, and we can utilize the eigenvalues and eigenvectors of matrices.

Eigenvectors can be understood as vectors that, when right-multiplied by the matrix, result in a vector parallel to themselves. Eigenvalues are the scaling factors by which the eigenvectors are scaled when right-multiplied by the matrix. In other words:

Here, $\lambda$ is the eigenvalue, and the non-zero vector $\boldsymbol{x} \in \mathbb{R}^n$ (where $n$ is the order of the square matrix) is the eigenvector corresponding to the eigenvalue $\lambda$ of matrix $\boldsymbol{A}$.

So, the specific approach is to first find the eigenvalues $\lambda_1$ and $\lambda_2$ (usually, an $n$-order matrix has $n$ eigenvalues) and obtain the diagonal matrix $\rm{diag}\{\lambda_1, \lambda_2\}$. Then, we find an invertible matrix $\boldsymbol{P}$ such that:

Using matrix multiplication properties:

This allows us to calculate $\boldsymbol{A}^{n}$.

Let's first find the eigenvalues. We can rewrite equation $(1)$ as:

Here, $\boldsymbol{E}$ is the identity matrix, and we can compute that $\boldsymbol{A}-\lambda\boldsymbol{E} = \begin{bmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{bmatrix}$. To ensure that there is a non-zero solution, we solve for:

Solving this equation, we obtain $\lambda_1 = \frac{1+\sqrt{5}}{2}$ and $\lambda_2 = \frac{1-\sqrt{5}}{2}$.

Therefore, the diagonal matrix is:

Assuming the eigenvector is $\boldsymbol{x} = \begin{bmatrix} x & y \end{bmatrix}^T$, we can substitute $\lambda_1$ and $\lambda_2$ into equation $(2)$ to obtain two systems of equations:

Setting $y = 1$ in both systems of equations gives us the two eigenvectors of the matrix:

So, the invertible matrix $\boldsymbol{P}$ is formed by these two eigenvectors:

Why is it like this? Let $\boldsymbol{P} = \begin{bmatrix} x_1 & x_2 \\ y_1 & y_2 \end{bmatrix}$ (where $x_1, y_1, x_2, y_2$ are the components of eigenvectors $\boldsymbol{x}_1, \boldsymbol{x}_2$ respectively).

Now, if we calculate $\boldsymbol{P}\rm{diag}\{\lambda_1, \lambda_2\}$, it exactly equals $\begin{bmatrix} \lambda_1x_1 & \lambda_2x_2 \\ \lambda_1y_1 & \lambda_2y_2 \end{bmatrix}$. This means that $\boldsymbol{A}\boldsymbol{P} = \boldsymbol{P}\rm{diag}\{\lambda_1, \lambda_2\}$ is inevitable. Left-multiplying by $\boldsymbol{P}^{-1}$, we get $\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P} = \rm{diag}\{\lambda_1, \lambda_2\}$. So, $\boldsymbol{P} = \begin{bmatrix} x_1 & x_2 \\ y_1 & y_2 \end{bmatrix}$ is reasonable.

Its inverse matrix is easy to calculate:

Substituting into equation $(2)$:

Where the diagonal matrix is:

Therefore,

Then,

Considering only the first row of the matrices on both sides of the equation, we obtain the closed-form formula for the Fibonacci sequence:

Substituting $n=0$ and $n=1$ to verify, we find that they both satisfy the equation.

Difference Equation Method

Defining the difference of a sequence $\{a_n\}$ as $\Delta a_n = a_{n+1} - a_n$ (using backward difference here), we can define the second-order difference as:

Further, we can define the $m$-th order difference:

And

The Fibonacci sequence, defined as $F_n = F_{n-1} + F_{n-2}$, has a second-order difference that is constant:

Now, we can write the second-order linear homogeneous difference equation for $F_n$:

This is a characteristic equation, and we can solve it by assuming $F_n = r^n$:

Solving this equation gives us two solutions: $r = 1$ and $r = -1$. Therefore, the general solution for the homogeneous difference equation is:

Now, we need initial conditions to find the particular solution. We know that $F_0 = 0$ and $F_1 = 1$. Substituting these into the general solution:

Solving this system of equations, we find $c_1 = \frac{1}{2}$ and $c_2 = -\frac{1}{2}$. Therefore, the particular solution for the Fibonacci sequence is:

This can be simplified further by noting that $(-1)^n$ is equal to $(-1)^{n-1} \cdot (-1) = -(-1)^{n-1}$:

This is indeed the closed-form formula for the Fibonacci sequence:

So, we have successfully derived the same result using the difference equation method.

In summary, both the matrix method and the difference equation method lead to the same closed-form expression for the Fibonacci sequence, demonstrating the beauty of mathematics in providing multiple ways to arrive at a solution.