 # The Fibonacci Sequence

### 1. Definition of the Fibonacci Sequence

The Fibonacci sequence is the sequence of integers constructed according to the following two rules:

• Initial values: The first two terms are 0 and 1.
• Recurrence relation: Each subsequent term is the sum of the two preceding terms.

It is easy to calculate the first few terms:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

### 2. Representation in Closed Form

The closed form for the n-th term of the Fibonacci sequence (where the first term is number 0) is

(1)   [(½ + ½ √ 5) n - (½ - ½ √ 5) n]/√5.

At this point, most people want to know where the closed form came from. It can be verified by mathematical induction, but it seems too complicated to have arisen from such simple rules.

Actually, the derivation is fairly simple. Consider a sequence with a recurrence relation even simpler than the Fibonacci relation. The rules are as follows:

• Initial values: The first term is 1.
• Recurrence relation: Each subsequent term is obtained by multiplying the previous term by a nonzero common ratio r.

Given the common ratio r, it is easy to write the terms of the sequence:

1, r, r 2, r 3, ...

The closed form for the n-th term of this sequence is simple and obvious: r n.

Now we ask the crucial question. Is there any value of the common ratio r for which this sequence also obeys the Fibonacci recurrence relation? If so, then

r n+2 = r n+1 + r n.

Since r ≠ 0, we can divide both sides of this equation by r n to obtain:

r 2 = r + 1.

This is a simple quadratic equation whose two roots are

(2)       r1 = ½ + ½ √ 5,
(3)       r2 = ½ - ½ √ 5,

Hence each of the following obeys the Fibonacci recurrence relation:

1, r1, r1 2, r1 3, ...
1, r2, r2 2, r2 3, ...

Now we write the Fibonacci recurrence relation for these sequences:

r1 n+2 = r1 n+1 + r1 n,
r2 n+2 = r2 n+1 + r2 n.

If we multiply the first equation by a, multiply the second equation by b, and add the results, we obtain

ar1 n+2 + br2 n+2 = ar1 n+1 + br2 n+1 + ar1 n + br2 n.

This is the Fibonacci recurrence relation for the sequence whose n-th term is

(4)   ar1 n + br2 n.

However, this sequence may not have the Fibonacci initial values. For that, we must choose a and b so that

a+b = 0,
ar1 + br2 = 1.

The solution of this system is

(5)   a = 1 / (r1 - r2) = 1/√5,
(6)   b = -1 / (r1 - r2) = -1/√5.

The closed form (1) for the n-th term of the Fibonacci sequence is then obtained by substituting (2), (3), (5) and (6) into (4).

### 3. The Ratio of Consecutive Terms

The ratio of consecutive terms of the Fibonacci sequence appears to tend to a limit:

1/1 = 1, 2/1 = 2, 3/2 = 1.5, 5/3 = 1.667, 8/5 = 1.6, 13/8 = 1.625, 21/13 = 1.615, 34/21 = 1.619, ...

In fact, the limit is precisely ½ + ½ √ 5, which is approximately 1.61803. This can be seen from the closed form (1), which lets us write the ratio of consecutive terms as

(½ + ½ √ 5) n+1 - (½ - ½ √ 5) n+1
--------------------------------------------
(½ + ½ √ 5) n - (½ - ½ √ 5) n

If we divide both numerator and denominator by (½ + ½ √ 5) n, this becomes

½ + ½ √ 5 - (½ - ½ √ 5) s n+1
--------------------------------------
1 - s n

where s = (½ - ½ √ 5) / (½ + ½ √ 5) ≅ -0.381967. Since |s| < 1, the terms containing s tend to zero as n increases without bound, and the ratio tends to ½ + ½ √ 5.

### 4. General Linear Recurrence Sequences

The same technique can be used to find a closed form for any sequence whose recurrence relation is linear with constant coefficients.

In general, such a sequence is defined as follows:

• Initial values: The first m terms are x0, x1, ..., xm-1.
• Recurrence relation: Each subsequent term is defined by xn = c1xn-1 + c2xn-2 + c3xn-3 + ... + cmxn-m , for all n ≥ m.

Here we require that cm ≠ 0, but the other coefficients may be zero.

Proceeding as in the Fibonacci case, we find that the sequence whose n-th term is r n obeys the recurrence relation if

r m = c1r m-1 + c2r m-2 + c3r m-3 + ... + cm-1r + cm.
i.e., if r is a root of the m-th degree polynomial
(7)   r m - c1r m-1 - c2r m-2 - c3r m-3 - cm-1r - ... - cm = 0.

Since cm ≠ 0, none of the roots is zero.

If this polynomial has m distinct roots r1, r2, ... rm, the desired closed form is

(8)   xn = a1 r1 n + a2 r2 n + a3 r3 n + ... + am rm n.
where the coefficients a1, a2, a3, ... am are the solutions to
(9)   a1 + a2 + a3 + ... + am = x0
a1 r1 + a2 r2 + a3 r3 + ... + am rm = x1
a1 r1 2 + a2 r2 2 + a3 r3 2 + ... + am rm 2 = x2
***
a1 r1 m-1 + a2 r2 m-1 + a3 r3 m-1 + ... + am rm m-1 = xm-1

The matrix of this system is the transpose of a square Vandermonde matrix, which is known to be nonsingular (see the Appendix).

What if the polynomial (7) has one or more multiple roots? There will not be enough equations in the system (9) to guarantee a solution. Clearly, some modification is needed.

We can write the recurrence relation for the sequence whose n-th term is r n as follows:

r n - c1r n-1 - c2r n-2 - c3r n-3 - ... - cmr n-m = 0.

This polynomial has a zero root of multiplicity n-m, but we are not interested in that root. A nonzero double root of this polynomial is also a root of its derivative:

nr n-1 - (n-1)c1r n-2 - (n-2)c2r n-3 - (n-3)c3r n-4 - ... - (n-m)cmr n-m-1 = 0.

Hence the sequence {0, 1, 2r, 3r 2, ...}, whose n-th term is nr n-1, also obeys the recurrence relation in this case.

Therefore, if r1 is a double root, and r2, r3, ... rm-1 are the other roots, the closed form (8) becomes

xn = a1 r1 n + a2 nr1 n-1 + a3 r2 n + ... + am rm-1 n.

The system (9) becomes:

a1 + 0 + a3 + ... + am = x0
a1 r1 + a2 + a3 r2 + ... + am rm-1 = x1
a1 r1 2 + a2 2r1 + a3 r2 2 + ... + am rm-1 2 = x2
a1 r1 3 + a2 3r1 2 + a3 r2 3 + ... + am rm-1 3 = x2
***
a1 r1 m-1 + a2 (m-2)r1 m-2 + a3 r2 m-1 + ... + am rm-1 m-1 = xm-1

The matrix of this system is the transpose of a square confluent Vandermonde matrix, which is known to be nonsingular (see the Appendix).

If there are other double roots, they can be handled in the same way.

Roots of higher multiplicity can be handled similarly, using higher-order derivatives.

### APPENDIX. Square Vandermonde Matrices

A square Vandermonde matrix is a matrix V whose rows are geometric progressions of the following form:

| 1, r1, r1 2, r1 3, ..., r1 n-1 |
| 1, r2, r2 2, r2 3, ..., r2 n-1 |
V = | 1, r3, r3 2, r3 3, ..., r3 n-1 |
***
| 1, rn, rn 2, rn 3, ..., rn n-1 |

If r1, r2, r3, ... rn are all different, the matrix is nonsingular.

To prove this, we first notice that if V were singular, then there would be some nonzero column vector u = (u1, u2, u3, ... un)T such that Vu is zero, i.e.,

u1 + u2r1 + u3r1 2 + ... + unr1 n-1 = 0
u1 + u2r2 + u3r2 2 + ... + unr2 n-1 = 0
***
u1 + u2rn + u3rn 2 + ... + unrn n-1 = 0

However, this would require the polynomial p(x) = u1 + u2x + u3x 2 + ... + unx n-1 to have n distinct roots r1, r2, r3, ... rn, which is impossible because it is a nonzero polynomial of degree at most n-1.

In a square confluent Vandermonde matrix, some rows are accompanied by their derivatives. The same line of argument is used, but the polynomial p(x) has fewer than n distinct roots. However, it has roots whose multiplicities add up to n, which is also impossible for a nonzero polynomial of degree at most n-1.