The Fibonacci Sequence Philip J. Erdelsky August 30, 2012

Please e-mail comments, corrections and additions to the webmaster at pje@efgh.com.

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) ⁿ - (½ - ½ √ 5) ⁿ]/√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 ², r ³, ...

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

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 ⁿ⁺² = r ⁿ⁺¹ + r ⁿ.

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

       r ² = r + 1.

This is a simple quadratic equation whose two roots are

(2)       r₁ = ½ + ½ √ 5,
(3)       r₂ = ½ - ½ √ 5,

Hence each of the following obeys the Fibonacci recurrence relation:

       1, r₁, r₁ ², r₁ ³, ...
       1, r₂, r₂ ², r₂ ³, ...

Now we write the Fibonacci recurrence relation for these sequences:

       r₁ ⁿ⁺² = r₁ ⁿ⁺¹ + r₁ ⁿ,
       r₂ ⁿ⁺² = r₂ ⁿ⁺¹ + r₂ ⁿ.

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

       ar₁ ⁿ⁺² + br₂ ⁿ⁺² = ar₁ ⁿ⁺¹ + br₂ ⁿ⁺¹ + ar₁ ⁿ + br₂ ⁿ.

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

(4)   ar₁ ⁿ + br₂ ⁿ.

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

       a+b = 0,
       ar₁ + br₂ = 1.

The solution of this system is

(5)   a = 1 / (r₁ - r₂) = 1/√5,
(6)   b = -1 / (r₁ - r₂) = -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) ⁿ⁺¹ - (½ - ½ √ 5) ⁿ⁺¹
       --------------------------------------------
       (½ + ½ √ 5) ⁿ - (½ - ½ √ 5) ⁿ

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

       ½ + ½ √ 5 - (½ - ½ √ 5) s ⁿ⁺¹
       --------------------------------------
       1 - s ⁿ

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 x₀, x₁, ..., x_m-1.
• Recurrence relation: Each subsequent term is defined by x_n = c₁x_n-1 + c₂x_n-2 + c₃x_n-3 + ... + c_mx_n-m , for all n ≥ m.

Here we require that c_m ≠ 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 ⁿ obeys the recurrence relation if

       r ^m = c₁r ^m-1 + c₂r ^m-2 + c₃r ^m-3 + ... + c_m-1r + c_m.

(7)   r ^m - c₁r ^m-1 - c₂r ^m-2 - c₃r ^m-3 - c_m-1r - ... - c_m = 0.

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

If this polynomial has m distinct roots r₁, r₂, ... r_m, the desired closed form is

(8)   x_n = a₁ r₁ ⁿ + a₂ r₂ ⁿ + a₃ r₃ ⁿ + ... + a_m r_m ⁿ.

(9)   a₁ + a₂ + a₃ + ... + a_m = x₀
       a₁ r₁ + a₂ r₂ + a₃ r₃ + ... + a_m r_m = x₁
       a₁ r₁ ² + a₂ r₂ ² + a₃ r₃ ² + ... + a_m r_m ² = x₂
       ***
       a₁ r₁ ^m-1 + a₂ r₂ ^m-1 + a₃ r₃ ^m-1 + ... + a_m r_m ^m-1 = x_m-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 ⁿ as follows:

       r ⁿ - c₁r ^n-1 - c₂r ^n-2 - c₃r ^n-3 - ... - c_mr ^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)c₁r ^n-2 - (n-2)c₂r ^n-3 - (n-3)c₃r ^n-4 - ... - (n-m)c_mr ^n-m-1 = 0.

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

Therefore, if r₁ is a double root, and r₂, r₃, ... r_m-1 are the other roots, the closed form (8) becomes

       x_n = a₁ r₁ ⁿ + a₂ nr₁ ^n-1 + a₃ r₂ ⁿ + ... + a_m r_m-1 ⁿ.

The system (9) becomes:

       a₁ + 0 + a₃ + ... + a_m = x₀
       a₁ r₁ + a₂ + a₃ r₂ + ... + a_m r_m-1 = x₁
       a₁ r₁ ² + a₂ 2r₁ + a₃ r₂ ² + ... + a_m r_m-1 ² = x₂
       a₁ r₁ ³ + a₂ 3r₁ ² + a₃ r₂ ³ + ... + a_m r_m-1 ³ = x₂
       ***
       a₁ r₁ ^m-1 + a₂ (m-2)r₁ ^m-2 + a₃ r₂ ^m-1 + ... + a_m r_m-1 ^m-1 = x_m-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, r₁, r₁ ², r₁ ³, ..., r₁ ^n-1 |
       | 1, r₂, r₂ ², r₂ ³, ..., r₂ ^n-1 |
V = | 1, r₃, r₃ ², r₃ ³, ..., r₃ ^n-1 |
         ***
       | 1, r_n, r_n ², r_n ³, ..., r_n ^n-1 |

If r₁, r₂, r₃, ... r_n 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 = (u₁, u₂, u₃, ... u_n)^T such that Vu is zero, i.e.,

u₁ + u₂r₁ + u₃r₁ ² + ... + u_nr₁ ^n-1 = 0
u₁ + u₂r₂ + u₃r₂ ² + ... + u_nr₂ ^n-1 = 0
***
u₁ + u₂r_n + u₃r_n ² + ... + u_nr_n ^n-1 = 0

However, this would require the polynomial p(x) = u₁ + u₂x + u₃x ² + ... + u_nx ^n-1 to have n distinct roots r₁, r₂, r₃, ... r_n, 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.

Links

• A Croation Translation by Milika Novak.