Here is the translation of the provided article into English:
In Fibonacci's work The Book of Calculation the Fibonacci sequence is defined as follows:
Fn=⎩⎨⎧01Fn−1+Fn−2if n=0if n=1if n≥2
It can be proven that its closed-form formula is:
Fn=51((21+5)n−(21−5)n)
With my current knowledge, I can only comprehend two proof methods as follows:
Matrix Method
Let's first discuss the case when n≥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:
Fn−1+Fn−2=Fn
We can add the equation Fn−1+0⋅Fn−2=Fn−1 to form a system of linear equations:
{Fn−1+Fn−2=FnFn−1+0⋅Fn−2=Fn−1
This can be transformed into matrix form as follows:
We denote the matrix A=[1110]. So, the problem becomes finding An−1, and then we can calculate An and replace all instances of n with n−1.
Notice that matrix 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)
Here, λ is the eigenvalue, and the non-zero vector x∈Rn (where n is the order of the square matrix) is the eigenvector corresponding to the eigenvalue λ of matrix A.
So, the specific approach is to first find the eigenvalues λ1 and λ2 (usually, an n-order matrix has n eigenvalues) and obtain the diagonal matrix diag{λ1,λ2}. Then, we find an invertible matrix P such that:
P−1AP=diag{λ1,λ2}
Using matrix multiplication properties:
(P−1AP)n=P−1A(PP−1)A(P⋯P−1)AP=P−1AnP(2)
This allows us to calculate An.
Let's first find the eigenvalues. We can rewrite equation (1) as:
(A−λE)x=0(3)
Here, E is the identity matrix, and we can compute that A−λE=[1−λ11−λ]. To ensure that there is a non-zero solution, we solve for:
∣A−λE∣=1−λ11−λ=λ2−λ−1=0
Solving this equation, we obtain λ1=21+5 and λ2=21−5.
Therefore, the diagonal matrix is:
diag{λ1,λ2}=[21+50021−5]
Assuming the eigenvector is x=[xy]T, we can substitute λ1 and λ2 into equation (2) to obtain two systems of equations:
{(1−λ1)x+y=0x−λ1y=0,{(1−λ2)x+y=0x−λ2y=0
Setting y=1 in both systems of equations gives us the two eigenvectors of the matrix:
x1=[21+51]T,x2=[21−51]T
So, the invertible matrix P is formed by these two eigenvectors:
P=[21+5121−51]
Why is it like this? Let P=[x1y1x2y2] (where x1,y1,x2,y2 are the components of eigenvectors x1,x2 respectively).
Now, if we calculate Pdiag{λ1,λ2}, it exactly equals [λ1x1λ1y1λ2x2λ2y2]. This means that AP=Pdiag{λ1,λ2} is inevitable. Left-multiplying by P−1, we get P−1AP=diag{λ1,λ2}. So, P=[x1y1x2y2] is reasonable.
Solving this system of equations, we find c1=21 and c2=−21. Therefore, the particular solution for the Fibonacci sequence is:
Fn=21⋅1n−21⋅(−1)n
This can be simplified further by noting that (−1)n is equal to (−1)n−1⋅(−1)=−(−1)n−1:
Fn=21−21⋅(−1)n−1
This is indeed the closed-form formula for the Fibonacci sequence:
Fn=51((21+5)n−(21−5)n)
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.