AOCP/Fibonacci Numbers

Volume 1

Chapter 1: Basic Concepts: Fibonacci Numbers

Fibonacci Numbers: Definition

The Fibonacci numbers are defined as the sequence:

$ F_0 = 1, F_1 = 1, F_n = F_{n-1} + F_{n-2} $

(Note: Knuth uses the convention $ F_0 = 0, F_1 = 1 $ in AOCP Volume 1, Section 1.2.8. The two conventions are offset by one index. This page follows the $ F_0 = 1, F_1 = 1 $ convention unless otherwise noted.)

The first few Fibonacci numbers are:

$ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, \dots $

The Fibonacci sequence is one of the most important linear recurrence sequences in mathematics. It appears in numerous contexts: the analysis of algorithms (particularly Euclid's algorithm), the study of phyllotaxis, computer science (Fibonacci heaps, Fibonacci search), combinatorics, and number theory.

Closed-Form Expression: Binet's Formula

The Fibonacci numbers admit a remarkable closed-form expression. Let:

$ \phi = \dfrac{1 + \sqrt{5}}{2} \approx 1.6180339887\dots $

$ \hat{\phi} = \dfrac{1 - \sqrt{5}}{2} = 1 - \phi = -\phi^{-1} \approx -0.6180339887\dots $

Here $ \phi $ is the golden ratio (see Phi). Then Binet's formula gives:

$ F_n = \dfrac{1}{\sqrt{5}} \left( \phi^n - \hat{\phi}^n \right) $

Since $ |\hat{\phi}| < 1 $, the term $ \hat{\phi}^n $ vanishes rapidly, yielding the useful approximation:

$ F_n \approx \dfrac{\phi^n}{\sqrt{5}} \quad \text{(rounded to the nearest integer)} $

For the Knuth convention ($ F_0 = 0, F_1 = 1 $), Binet's formula is identical:

$ F_n = \dfrac{\phi^n - \hat{\phi}^n}{\sqrt{5}} $

Generating Function

The ordinary generating function for the Fibonacci numbers is derived in AOCP/Generating Functions. Define:

$ G(z) = \sum_{n \geq 0} F_n z^n = F_0 + F_1 z + F_2 z^2 + \dots $

Using the recurrence, multiply by $ z $ and $ z^2 $:

$ \begin{align} z G(z) &= F_0 z + F_1 z^2 + F_2 z^3 + \dots \\ z^2 G(z) &= F_0 z^2 + F_1 z^3 + F_2 z^4 + \dots \end{align} $

Subtracting and applying the recurrence $ F_n - F_{n-1} - F_{n-2} = 0 $ for $ n \geq 2 $:

$ (1 - z - z^2) G(z) = F_0 + (F_1 - F_0) z $

With $ F_0 = 1, F_1 = 1 $, the right side simplifies to $ 1 $:

$ G(z) = \dfrac{1}{1 - z - z^2} $

(Under the Knuth convention $ F_0 = 0, F_1 = 1 $, the generating function is $ G(z) = \dfrac{z}{1 - z - z^2} $.)

The generating function encapsulates the entire Fibonacci sequence: the coefficient of $ z^n $ in the Taylor expansion of $ G(z) $ is exactly $ F_n $.

Relationship to Binomial Coefficients

The Fibonacci numbers can be expressed as sums of binomial coefficients along the shallow diagonals of Pascal's triangle:

$ F_{n+1} = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} $

For example:

$ \begin{align} F_6 &= \binom{5}{0} + \binom{4}{1} + \binom{3}{2} = 1 + 4 + 3 = 8 \\ F_7 &= \binom{6}{0} + \binom{5}{1} + \binom{4}{2} + \binom{3}{3} = 1 + 5 + 6 + 1 = 13 \end{align} $

This identity reveals the deep connection between the Fibonacci numbers and the binomial coefficients (see AOCP/Binomial Coefficients).

Basic Identities

Fibonacci numbers satisfy thousands of identities; these can be classified as follows:

Cassini's Identity

$ F_{n-1} F_{n+1} - F_n^2 = (-1)^{n+1} $

For the Knuth convention ($ F_0 = 0, F_1 = 1 $), the identity is:

$ F_{n-1} F_{n+1} - F_n^2 = (-1)^n $

This is a special case of Catalan's identity (see below). Cassini's identity is the basis for the "Cassini paradox" in geometry.

Catalan's Identity

A generalization of Cassini's identity, for any $ r \geq 1 $:

$ F_{n-r} F_{n+r} - F_n^2 = (-1)^{n-r+1} F_r^2 $

d'Ocagne's Identity

$ F_m F_{n+1} - F_{m+1} F_n = (-1)^n F_{m-n} $

Addition Formula

$ F_{n+m} = F_m F_{n+1} + F_{m-1} F_n $

This is one of the most important Fibonacci identities. Setting $ m = n $ yields the doubling formula; setting $ m = n-1 $ yields a recurrence for $ F_{2n-1} $.

Doubling Formulas

$ F_{2n} = F_n (F_{n+1} + F_{n-1}) $

$ F_{2n-1} = F_n^2 + F_{n-1}^2 $

These allow computing Fibonacci numbers at large indices in $ O(\log n) $ steps.

Summation Identities

Sum of the first $ n $ Fibonacci numbers:

$ \sum_{k=1}^n F_k = F_{n+2} - 1 $

Sum of odd-index Fibonacci numbers:

$ \sum_{k=1}^n F_{2k-1} = F_{2n} $

Sum of even-index Fibonacci numbers:

$ \sum_{k=1}^n F_{2k} = F_{2n+1} - 1 $

Sum of squares:

$ \sum_{k=1}^n F_k^2 = F_n F_{n+1} $

These identities can be proved by induction using the addition formula.

Relationship to the Golden Ratio

The ratio of consecutive Fibonacci numbers converges to the golden ratio:

$ \lim_{n \to \infty} \dfrac{F_{n+1}}{F_n} = \phi = \dfrac{1 + \sqrt{5}}{2} $

Moreover, $ F_{n+1} $ and $ F_n $ are the nearest integers to $ \phi F_n $ and $ \dfrac{1}{\phi} F_{n+1} $ respectively.

The golden ratio and Fibonacci numbers are linked through the identity:

$ \phi^n = F_n \phi + F_{n-1} $

Valid for the Knuth convention ($ F_0 = 0, F_1 = 1 $).

GCD Property

One of the most remarkable properties of Fibonacci numbers:

$ \gcd(F_m, F_n) = F_{\gcd(m,n)} $

In particular, consecutive Fibonacci numbers are coprime:

$ \gcd(F_n, F_{n+1}) = 1 $

This property is intimately related to the Euclidean algorithm: the number of steps required by Euclid's algorithm to compute $ \gcd(F_{n+1}, F_n) $ is $ n $, making Fibonacci pairs the worst-case input.

Divisibility Properties

For positive integers $ m, n $:

$ F_n \mid F_m \quad \text{if and only if} \quad n \mid m $

Consequences:

• Every third Fibonacci number is even ($ F_{3k} $ is even)
• Every fourth Fibonacci number is divisible by 3
• Every fifth Fibonacci number is divisible by 5
• Every $ k $-th Fibonacci number is divisible by $ F_k $

Negative-Index Fibonacci Numbers

The Fibonacci recurrence can be extended backward:

$ F_{-n} = (-1)^{n+1} F_n $

So the Fibonacci sequence, extended symmetrically in both directions, gives:

$ \dots, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, \dots $

(This uses the Knuth convention $ F_0 = 0, F_1 = 1 $.)

Lucas Numbers

The Lucas numbers are a companion sequence to the Fibonacci numbers, defined by:

$ L_0 = 2, \quad L_1 = 1, \quad L_n = L_{n-1} + L_{n-2} $

First few Lucas numbers: $ 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, \dots $

Relationships between Fibonacci and Lucas numbers:

$ L_n = F_{n-1} + F_{n+1} $

$ L_n = F_{2n} / F_n $

$ F_n = \dfrac{L_{n-1} + L_{n+1}}{5} $

$ L_n^2 - 5 F_n^2 = 4 (-1)^n $

The Lucas numbers satisfy Binet's formula:

$ L_n = \phi^n + \hat{\phi}^n $

Fibonacci Number System (Zeckendorf's Theorem)

Every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers, with the restriction that no two consecutive Fibonacci numbers are used. This is Zeckendorf's theorem.

For example:

$ \begin{align} 1 &= F_2 \\ 2 &= F_3 \\ 3 &= F_4 \\ 4 &= F_4 + F_2 = 3 + 1 \\ 5 &= F_5 \\ 6 &= F_5 + F_2 = 5 + 1 \\ 7 &= F_5 + F_3 = 5 + 2 \\ 8 &= F_6 \\ 9 &= F_6 + F_2 = 8 + 1 \\ 10 &= F_6 + F_3 = 8 + 2 \end{align} $

(These examples use the Knuth convention $ F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, \dots $.)

This representation gives rise to Fibonacci coding, a universal code used in data compression.

Matrix Form

The Fibonacci recurrence can be expressed in matrix form:

$ \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} $

Let $ Q = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $. Then:

$ Q^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} $

This yields a fast method for computing Fibonacci numbers via exponentiation by squaring in $ O(\log n) $ time.

Periodicity Modulo m: The Pisano Period

The Fibonacci sequence modulo any positive integer $ m $ is periodic. The period length is called the Pisano period, denoted $ \pi(m) $.

For example, modulo 10 (the last digit of Fibonacci numbers):

$ 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, \dots $

with period $ \pi(10) = 60 $.

Example Problems

Some example problems involving Fibonacci numbers.

Knuth AOCP Section 1.2.8 Problem 1

Problem 1. (M10 difficulty) What are the generating functions for $ \langle F_{2n} \rangle $ and $ \langle F_{2n+1} \rangle $?

Solution

We start with the generating function for $ \langle F_n \rangle $ under the Knuth convention:

$ G(z) = \dfrac{z}{1 - z - z^2} $

To obtain the generating function for even-index Fibonacci numbers, we can use the identity:

$ \sum_{n \geq 0} F_{2n} z^n = \dfrac{G(\sqrt{z}) + G(-\sqrt{z})}{2} $

Working through the algebra:

$ G_{even}(z) = \dfrac{z}{1 - 3z + z^2} $

Similarly, for odd-index Fibonacci numbers:

$ G_{odd}(z) = \dfrac{1 - z}{1 - 3z + z^2} $

Cassini's Identity Proof

Prove Cassini's identity by induction:

$ F_{n-1} F_{n+1} - F_n^2 = (-1)^n $

Base Case

For $ n = 1 $:

$ F_0 F_2 - F_1^2 = 0 \cdot 1 - 1^2 = -1 = (-1)^1 $

Inductive Step

Assume the identity holds for $ n $. For $ n+1 $:

$ \begin{align} F_n F_{n+2} - F_{n+1}^2 &= F_n (F_{n+1} + F_n) - F_{n+1}^2 \\ &= F_n F_{n+1} + F_n^2 - F_{n+1}^2 \\ &= F_n F_{n+1} - (F_{n+1}^2 - F_n^2) \\ &= F_n F_{n+1} - F_{n+1}(F_n + F_{n-1}) + F_n^2 \\ &= F_n F_{n+1} - F_{n+1}F_n - F_{n+1}F_{n-1} + F_n^2 \\ &= -(F_{n-1}F_{n+1} - F_n^2) \\ &= -(-1)^n = (-1)^{n+1} \end{align} $

Thus the identity holds for all $ n \geq 1 $.

GCD of Fibonacci Numbers

Problem. Prove that $ \gcd(F_m, F_n) = F_{\gcd(m,n)} $.

Solution Outline

Use the addition formula and the Euclidean algorithm. First, show:

$ F_{n+m} = F_m F_{n+1} + F_{m-1} F_n $

From this, it follows that any divisor of both $ F_m $ and $ F_n $ also divides $ F_{m+n} $, and more generally $ F_{m \bmod n} $. Applying the Euclidean algorithm on the indices reduces the problem to computing $ F_{\gcd(m,n)} $.

Sum of Fibonacci Numbers Squared

Problem. Compute $ \sum_{k=1}^n F_k^2 $.

Solution

Use the doubling formula and telescoping. Observe:

$ F_k F_{k+1} - F_{k-1} F_k = F_k (F_{k+1} - F_{k-1}) = F_k^2 $

Summing from $ k=1 $ to $ n $ telescopes:

$ \sum_{k=1}^n F_k^2 = F_n F_{n+1} - F_0 F_1 = F_n F_{n+1} $

since $ F_0 = 0 $ under the Knuth convention.

Related

AOCP/Generating Functions - generating function derivation and partial fraction expansion

AOCP/Binomial Coefficients - Fibonacci numbers as sums of binomial coefficients

General Fibonacci Numbers - generalization with arbitrary starting values

Phi - the golden ratio, to 100,000 digits

Formulas - Binet's formula and other key formulas

AOCP/Infinite Series - infinite series involving Fibonacci numbers

Algorithms/Dynamic Programming - Fibonacci as a dynamic programming example