The Fibonacci recurrence,
a_{n} = a_{n−1}+a_{n−2}
is linear. This might suggest either of two things to you, depending on your background:
- Like a linear differential equation, its solutions obey the superposition principle; the sum of solutions is a solution, and a multiple of a solution is a solution.
- Matrices will be involved in the theory somewhere.
Both of these are true, as we will see. I am going to discuss several different ways of finding a formula for the nth Fibonacci number.
Linear algebra
Let us take the matrices first. Let A be the matrix . Then (x,y)A = (y,x+y). If x = a_{n} and y = a_{n+1}, then the components of (x,y)A are (a_{n+1},a_{n+2}). So, if we let v_{n}=(a_{n},a_{n+1}), then we have
v_{n}A = v_{n+1}.
It follows that v_{n} = v_{0}A^{n}.
Now v_{0} is the vector whose components are the two “initial values” (a_{0},a_{1}). So the last equation gives the solution to the recurrence relation with any given initial conditions.
This form of the solution allows us to reduce the number of arithmetic operations involved in calculating the nth term. We can compute A^{n} with at most 2 log n matrix multiplications. (First, by successive squaring, we compute A^{2i} for all i with 2^{i} ≤ n; the, we multiply together the matrices corresponding to the powers of 2 occurring in the base 2 expansion of n. However, the gain is somewhat illusory, since multiplication is more complicated than addition.
The other advantage of the matrix method is that we can convert it into an explicit formula. The characteristic polynomial of A is x^{2}−x−1, and so the eigenvalues of A are the roots of this polynomial, namely α =(1+√5)/2 (the golden ratio) and β=(1−√5)/2. Since they are distinct, A is diagonalisable. If P is the idempotent matrix whose image is the α-eigenspace and whose kernel is the β-eigenspace, and Q is vice versa, then we have I = P+Q (where I is the identity matrix) and A = αP+βQ.
Since P^{2} = P, Q^{2} = Q, and PQ = O (the zero matrix), we find that
A^{n} = α^{n}P+β^{n}Q.
So we can write down a formula for a_{n}. Rather than work through the details, I’ll just give the conclusion, which is that
a_{n} = cα^{n}+dβ^{n},
where c and d are constants which can be found from the above calculation. But we can find them more easily, by noticing that
a_{0} | = | c+d, |
a_{1} | = | cα+dβ, |
giving two equations for c and d (in terms of the initial conditions) which can be easily solved.
Since we found the formula by a general argument (the rest of the proof was just putting it into more familiar form), there is no doubt that we have found all possible solutions.
Formal power series
Once again let the numbers a_{n} satisfy the Fibonacci recurrence. Let f(x) = ∑a_{n}x^{n}, where x is an indeterminate, and the sum is over the non-negative integers n. (This is a formal power series, which means that we don’t have to worry whether it is convergent or not; the theory of formal power series magically justifies all our manipulations.)
We have
.
f(x) | = | a_{0}+a_{1}x+∑_{n≥2}a_{n}x^{n} |
= | a_{0}+a_{1}x+∑_{n≥2}a_{n−1}x^{n}+∑_{n≥2}a_{n−2}x^{n} | |
= | a_{0}+a_{1}x+x(f(x)−a_{0})+x^{2}f(x) |
Rearranging, we obtain (1−x−x^{2})f(x) = a_{0}+(a_{1}−a_{0})x, so that
f(x) = (a_{0}+(a_{1}−a_{0})x)/(1−x−x^{2}).
To convert this to an explicit formula for a_{n}, we use the technique of partial fractions to convert it into
f(x) = c/(1−αx)+d/(1−βx),
where (1−αx)(1−βx) = 1−x−x^{2} (so that α and β are exactly as before). Then using the geometric series expansions
1/(1−αx) = ∑α^{n}x^{n}, 1/(1−βx) = ∑β^{n}x^{n},
and equating the coefficients of x^{n}, we obtain the same solution as before.
Because there is no requirement of convergence for formal power series, we know that we haven’t missed any possible solutions by this method.
Guesswork
If you ever studied differential equations, you will know that a technique for solving linear differential equations is to guess the form of the solution, find the parameters that make it work, and then take linear combinations of the solutions you find. The same trick works here.
Suppose that you guess that a solution to the Fibonacci recurrence is a_{n} = t^{n}, for some number t. In order for the recurrence to be satisfied, we must have
t^{n+2} = t^{n}+t^{n+1},
so that t^{2} = 1+t. Conversely, if t satisfies this equation, then a_{n} = t^{n} satisfies the recurrence.
Solving the quadratic, we find that the two possible values of t are exactly the α and β found earlier. So α^{n} and β^{n} are solutions. By linearity, we see that a_{n} = cα^{n}+dβ^{n} is a solution to the recurrence, for any values of the constants c and d. Now, as in the linear algebra argument, we can determine the values of c and d required to satisfy whatever initial conditions we are given.
The last line in an argument like this should be: the recurrence relation and initial conditions admit a unique solution (this is easily proved by induction: take two sequences satisfying the recurrence and the same initial conditions, and prove that they coincide); since we have found a solution, it is necessarily the only possible solution.
Final note
Since |β| < 1, the term dβ^{n} tends exponentially to zero; so we find that the asymptotic formula for the solution is simply cα^{n}, where α is the golden ratio. This is the famous connection between the Fibonacci numbers and the golden ratio.
Pingback: rods to stems to congruents to GOST to complexity | Peter's ruminations
Pingback: On Fibonacci numbers and the golden ratio « Maximal determinant blog
Pingback: Weekly links for March 25 | God plays dice