Use Differential Equation Method and Matrix Method to Find Fibonacci Sequence General Formula

    Nov 20, 2023

    This article gives two methods to derive Fibonacci sequence: matrix method and difference equation method

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

    Fn={0if n=01if n=1Fn1+Fn2if n2F_n = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F_{n-1} + F_{n-2} & \text{if } n \geq 2 \end{cases}

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

    Fn=15((1+52)n(152)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)

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

    Matrix Method

    Let's first discuss the case when n2n \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:

    Fn1+Fn2=FnF_{n-1} + F_{n-2} = F_{n}

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

    {Fn1+Fn2=FnFn1+0Fn2=Fn1\begin{cases} F_{n-1} + F_{n-2} = F_{n} \\ F_{n-1} + 0 \cdot F_{n-2} = F_{n-1} \end{cases}

    This can be transformed into matrix form as follows:

    [1110][Fn1Fn2]=[FnFn1]\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} = \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}

    Now, we can iterate this process:

    [FnFn1]=[1110][Fn1Fn2]=[1110]2[Fn2Fn3]==[1110]n1[F1F0]\begin{align} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^2 \begin{bmatrix} F_{n-2} \\ F_{n-3} \end{bmatrix} \\ &=\cdots \\ &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix} \end{align}

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

    Notice that matrix A\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:

    Ax=λx(1)\boldsymbol{A}\boldsymbol{x} = \lambda\boldsymbol{x}\tag{1}

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

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

    P1AP=diag{λ1,λ2}\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P} = \rm{diag}\{\lambda_1, \lambda_2\}

    Using matrix multiplication properties:

    (P1AP)n=P1A(PP1)A(PP1)AP=P1AnP(2)(\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P})^n = \boldsymbol{P}^{-1}\boldsymbol{A}(\boldsymbol{P}\boldsymbol{P}^{-1})\boldsymbol{A}(\boldsymbol{P}\cdots\boldsymbol{P}^{-1})\boldsymbol{A}\boldsymbol{P} = \boldsymbol{P}^{-1}\boldsymbol{A}^n\boldsymbol{P}\tag{2}

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

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

    (AλE)x=0(3)(\boldsymbol{A}-\lambda\boldsymbol{E})\boldsymbol{x} = \boldsymbol{0}\tag{3}

    Here, E\boldsymbol{E} is the identity matrix, and we can compute that AλE=[1λ11λ]\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:

    AλE=1λ11λ=λ2λ1=0\left| \boldsymbol{A}-\lambda\boldsymbol{E} \right| = \begin{vmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{vmatrix} = \lambda^2 - \lambda - 1 = 0

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

    Therefore, the diagonal matrix is:

    diag{λ1,λ2}=[1+5200152]\rm{diag}\{\lambda_1, \lambda_2\} = \begin{bmatrix} \frac{1+\sqrt{5}}{2} & 0 \\ 0 & \frac{1-\sqrt{5}}{2} \end{bmatrix}

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

    {(1λ1)x+y=0xλ1y=0,{(1λ2)x+y=0xλ2y=0\begin{cases} (1-\lambda_1)x + y = 0 \\ x - \lambda_1y = 0 \end{cases}, \begin{cases} (1-\lambda_2)x + y = 0 \\ x - \lambda_2y = 0 \end{cases}

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

    x1=[1+521]T,x2=[1521]T\boldsymbol{x}_1 = \begin{bmatrix} \frac{1+\sqrt{5}}{2} & 1 \end{bmatrix}^T, \boldsymbol{x}_2 = \begin{bmatrix} \frac{1-\sqrt{5}}{2} & 1 \end{bmatrix}^T

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

    P=[1+5215211]\boldsymbol{P} = \begin{bmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \\ 1 & 1 \end{bmatrix}

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

    Now, if we calculate Pdiag{λ1,λ2}\boldsymbol{P}\rm{diag}\{\lambda_1, \lambda_2\}, it exactly equals [λ1x1λ2x2λ1y1λ2y2]\begin{bmatrix} \lambda_1x_1 & \lambda_2x_2 \\ \lambda_1y_1 & \lambda_2y_2 \end{bmatrix}. This means that AP=Pdiag{λ1,λ2}\boldsymbol{A}\boldsymbol{P} = \boldsymbol{P}\rm{diag}\{\lambda_1, \lambda_2\} is inevitable. Left-multiplying by P1\boldsymbol{P}^{-1}, we get P1AP=diag{λ1,λ2}\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P} = \rm{diag}\{\lambda_1, \lambda_2\}. So, P=[x1x2y1y2]\boldsymbol{P} = \begin{bmatrix} x_1 & x_2 \\ y_1 & y_2 \end{bmatrix} is reasonable.

    Its inverse matrix is easy to calculate:

    P1=PP=15[115211+52]\boldsymbol{P}^{-1} = \frac{\boldsymbol{P}^*}{\left|\boldsymbol{P}\right|} = \frac{1}{\sqrt{5}}\begin{bmatrix} 1 & \frac{1-\sqrt{5}}{2} \\ 1 & \frac{1+\sqrt{5}}{2} \end{bmatrix}

    Substituting into equation (2)(2):

    An=P(P1AP)nP1=Pdiagn{λ1,λ2}P1\boldsymbol{A}^n = \boldsymbol{P}(\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P})^n\boldsymbol{P}^{-1} = \boldsymbol{P}\rm{diag}^n\{\lambda_1, \lambda_2\}\boldsymbol{P}^{-1}

    Where the diagonal matrix is:

    diagn{λ1,λ2}=[(1+52)n00(152)n]\rm{diag}^n\{\lambda_1, \lambda_2\} = \begin{bmatrix} \left(\frac{1+\sqrt{5}}{2}\right)^n & 0 \\ 0 & \left(\frac{1-\sqrt{5}}{2}\right)^n \end{bmatrix}

    Therefore,

    An=15[(1+52)n+1+(152)n+1(1+52)n+1(152)+(152)n+1(1+52)(1+52)n+(152)n(1+52)n(152)+(152)n(1+52)]\boldsymbol{A}^n = \frac{1}{\sqrt{5}}\begin{bmatrix} \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} + \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} & \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}\left(\frac{1-\sqrt{5}}{2}\right) + \left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\left(\frac{1+\sqrt{5}}{2}\right) \\ \left(\frac{1+\sqrt{5}}{2}\right)^n + \left(\frac{1-\sqrt{5}}{2}\right)^n & \left(\frac{1+\sqrt{5}}{2}\right)^{n}\left(\frac{1-\sqrt{5}}{2}\right) + \left(\frac{1-\sqrt{5}}{2}\right)^{n}\left(\frac{1+\sqrt{5}}{2}\right) \end{bmatrix}

    Then,

    [FnFn1]=An1[F1F0]=15[(1+52)n+(152)n(1+52)n1+(152)n1]\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \boldsymbol{A}^{n-1} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} = \frac{1}{\sqrt{5}}\begin{bmatrix} \left(\frac{1+\sqrt{5}}{2}\right)^{n} + \left(\frac{1-\sqrt{5}}{2}\right)^{n} \\ \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} + \left(\frac{1-\sqrt{5}}{2}\right)^{n-1} \end{bmatrix}

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

    Fn=15((1+52)n(152)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)

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


    Difference Equation Method

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

    Δ2an=Δan+1Δan=an+22an+1+an\Delta^2 a_n = \Delta a_{n+1} - \Delta a_n = a_{n+2} - 2a_{n+1} + a_n

    Further, we can define the mm-th order difference:

    Δman=Δm1an+1Δm1an=i=0m(1)iCmian+mi\Delta^m a_n = \Delta^{m-1} a_{n+1} - \Delta^{m-1} a_n = \sum_{i=0}^{m} (-1)^i C_m^i a_{n+m-i}

    And

    F(an,Δan,Δan,Δ2an,Δ3an,)F(a_n, \Delta a_n, \Delta a_n, \Delta^2 a_n, \Delta^3 a_n, \ldots)

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

    Δ2Fn=Fn+22Fn+1+Fn=Fn+1+Fn+12Fn+1+Fn=Fn+1Fn=Fn\Delta^2 F_n = F_{n+2} - 2F_{n+1} + F_n = F_{n+1} + F_{n+1} - 2F_{n+1} + F_n = F_{n+1} - F_n = F_n

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

    Δ2FnFn=0\Delta^2 F_n - F_n = 0

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

    r21=0r^2 - 1 = 0

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

    Fn=c11n+c2(1)nF_n = c_1 \cdot 1^n + c_2 \cdot (-1)^n

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

    F0=c110+c2(1)0=c1+c2=0F1=c111+c2(1)1=c1c2=1\begin{align*} F_0 &= c_1 \cdot 1^0 + c_2 \cdot (-1)^0 = c_1 + c_2 = 0 \\ F_1 &= c_1 \cdot 1^1 + c_2 \cdot (-1)^1 = c_1 - c_2 = 1 \end{align*}

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

    Fn=121n12(1)nF_n = \frac{1}{2} \cdot 1^n - \frac{1}{2} \cdot (-1)^n

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

    Fn=1212(1)n1F_n = \frac{1}{2} - \frac{1}{2} \cdot (-1)^{n-1}

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

    Fn=15((1+52)n(152)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)

    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.