The Fibonacci recurrence,
an = an−1+an−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.
Let us take the matrices first. Let A be the matrix . Then (x,y)A = (y,x+y). If x = an and y = an+1, then the components of (x,y)A are (an+1,an+2). So, if we let vn=(an,an+1), then we have
vnA = vn+1.
It follows that vn = v0An.
Now v0 is the vector whose components are the two “initial values” (a0,a1). 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 An with at most 2 log n matrix multiplications. (First, by successive squaring, we compute A2i for all i with 2i ≤ 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 x2−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 P2 = P, Q2 = Q, and PQ = O (the zero matrix), we find that
An = αnP+βnQ.
So we can write down a formula for an. Rather than work through the details, I’ll just give the conclusion, which is that
an = 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
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 an satisfy the Fibonacci recurrence. Let f(x) = ∑anxn, 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.)
Rearranging, we obtain (1−x−x2)f(x) = a0+(a1−a0)x, so that
f(x) = (a0+(a1−a0)x)/(1−x−x2).
To convert this to an explicit formula for an, 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−x2 (so that α and β are exactly as before). Then using the geometric series expansions
1/(1−αx) = ∑αnxn, 1/(1−βx) = ∑βnxn,
and equating the coefficients of xn, 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.
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 an = tn, for some number t. In order for the recurrence to be satisfied, we must have
tn+2 = tn+tn+1,
so that t2 = 1+t. Conversely, if t satisfies this equation, then an = tn 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 an = 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.
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.