unitgridOpacitycanvasColor

18. Fibonacci numbers

Review

Power iteration showed that repeatedly applying a matrix MM to a vector drives it toward the eigenvector of MM's largest eigenvalue, because Mn=VDnV−1M^n = VD^nV^{-1} and the dominant eigenvalue swamps the rest. This chapter cashes that idea out on a sequence every programmer knows.

If you write code, you have almost certainly met the Fibonacci numbers, and probably written a function to compute the nn-th one by iteration or recursion. Here we look at them through a linear-algebra lens, which reveals a closed-form formula and connects them to the broader family of linear recurrence relations.

18.1 Fibonacci numbers

The Fibonacci numbers are a sequence Fi, i=0,1,2,…F_i,\ i = 0, 1, 2, \ldots defined by F0=0F_0 = 0, F1=1F_1 = 1, and

Fi+2=Fi+1+Fifor i≥0F_{i+2} = F_{i+1} + F_i \quad \text{for } i \ge 0

The textbook recursive implementation follows the definition directly:

def fibonacci(n):
    if n == 0: return 0
    if n == 1: return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

18.2 Two consecutive Fibonacci numbers as a vector

Now pack two consecutive Fibonacci numbers into a 2D vector:

vn=[FnFn+1]v_n = \begin{bmatrix} \textcolor{#1d4ed8}{F_n} \\ \textcolor{#be185d}{F_{n+1}} \end{bmatrix}

This gives v0=[01]v_0 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}, v1=[11]v_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}, v2=[12]v_2 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, and so on.

18.2.1 What is the direction of this vector?

The direction of vnv_n is the angle tan⁡−1 ⁣(Fn+1Fn)\tan^{-1}\!\left(\dfrac{F_{n+1}}{F_n}\right). As nn grows, does this ratio of consecutive Fibonacci numbers converge? If it does, then the direction of vnv_n settles down too, and (just like power iteration) that limiting direction is the eigenvector of the largest eigenvalue of some matrix. Let's watch it happen before we find the matrix.

pie.clear()
pie.scalar(40, out='unit')
GRAY, TEAL, GOLD, VIOLET = '#71717a', '#0d9488', '#ca8a04', '#6d28d9'

Reveal the golden direction [1,ϕ][1, \phi], the line of slope ϕ≈1.618\phi \approx 1.618.

pie.line(pie.point(3, 4.854, out='ga', hidden=True), pie.point(-3, -4.854, out='gb', hidden=True), out='gline', stroke=VIOLET)
pie.text('[1, φ]', 4.2, 4.2, 13, out='lblGL', stroke=VIOLET)

Now plot the Fibonacci vectors one at a time:

  • v0=[0,1]v_0 = [0, 1]
pie.la_vec2d(0, 1, out='f0', stroke=TEAL)
pie.text('v₀', -0.5, 1.3, 13, out='lblV0', stroke=TEAL)
  • v1=[1,1]v_1 = [1, 1]
pie.la_vec2d(1, 1, out='f1', stroke=TEAL)
pie.text('v₁', 1.7, 0.85, 13, out='lblV1', stroke=TEAL)
  • v2=[1,2]v_2 = [1, 2]
pie.la_vec2d(1, 2, out='f2', stroke=TEAL)
pie.text('v₂', 0.4, 2.3, 13, out='lblV2', stroke=TEAL)
  • v3=[2,3]v_3 = [2, 3]
pie.la_vec2d(2, 3, out='f3', stroke=TEAL)
pie.text('v₃', 2.7, 3.0, 13, out='lblV3', stroke=TEAL)
  • and v4=[3,5]v_4 = [3, 5].
pie.la_vec2d(3, 5, out='f4', stroke=GOLD)
pie.text('v₄', 3.4, 5.3, 13, out='lblV4', stroke=GOLD)
pie.text('Each Fibonacci vector vₙ = [Fₙ, Fₙ₊₁] grows longer, but its direction locks onto the golden line: Fₙ₊₁/Fₙ → φ ≈ 1.618.', -2.9, 4.2, 12, 4.2, -1, out='sumBox', stroke=GRAY)

Each vector is longer than the last, but their directions zig-zag in and lock onto the violet line: the ratio Fn+1Fn\dfrac{F_{n+1}}{F_n} converges to ϕ\phi.

18.3 The recurrence relation

The trick is to express vn+1v_{n+1} as a matrix-vector product MvnM v_n. Finding MM is easy:

vn+1=[Fn+1Fn+2]=[0⋅Fn+Fn+1Fn+Fn+1⏟the recurrence]=[0111][FnFn+1]=[0111]vn\begin{aligned} v_{n+1} &= \begin{bmatrix} F_{n+1} \\ F_{n+2} \end{bmatrix} \\ &= \begin{bmatrix} 0 \cdot \textcolor{#1d4ed8}{F_n} + \textcolor{#be185d}{F_{n+1}} \\ \underbrace{\textcolor{#1d4ed8}{F_n} + \textcolor{#be185d}{F_{n+1}}}_{\text{the recurrence}} \end{bmatrix} \\ &= \begin{bmatrix} \textcolor{#1d4ed8}{0} & \textcolor{#be185d}{1} \\ \textcolor{#1d4ed8}{1} & \textcolor{#be185d}{1} \end{bmatrix} \begin{bmatrix} \textcolor{#1d4ed8}{F_n} \\ \textcolor{#be185d}{F_{n+1}} \end{bmatrix} \\ &= \begin{bmatrix} \textcolor{#1d4ed8}{0} & \textcolor{#be185d}{1} \\ \textcolor{#1d4ed8}{1} & \textcolor{#be185d}{1} \end{bmatrix} v_n \end{aligned}

So M=[0111]M = \begin{bmatrix} \textcolor{#1d4ed8}{0} & \textcolor{#be185d}{1} \\ \textcolor{#1d4ed8}{1} & \textcolor{#be185d}{1} \end{bmatrix}. Since v1=Mv0v_1 = M v_0, v2=Mv1=M2v0v_2 = M v_1 = M^2 v_0, and in general vn=Mnv0v_n = M^n v_0, the vector vnv_n points toward MM's dominant eigenvector for large nn, exactly the convergence we just saw. Let's find its eigenvalues and eigenvectors.

If λ\lambda is an eigenvalue of MM, then [−λ111−λ]\begin{bmatrix} -\lambda & 1 \\ 1 & 1 - \lambda \end{bmatrix} is singular, so its columns are parallel and its determinant vanishes:

−λ(1−λ)−1=0  ⟹  λ2=λ+1-\lambda(1 - \lambda) - 1 = 0 \implies \lambda^2 = \lambda + 1

This is precisely the equation that defines the golden ratio.

  • The eigenvalues are ϕ=1+52≈1.618\textcolor{#047857}{\phi} = \dfrac{1 + \sqrt{5}}{2} \approx 1.618 and ψ=1−52≈−0.618\textcolor{#b45309}{\psi} = \dfrac{1 - \sqrt{5}}{2} \approx -0.618.
  • The corresponding eigenvectors are [1ϕ]\begin{bmatrix} 1 \\ \textcolor{#047857}{\phi} \end{bmatrix} and [1ψ]\begin{bmatrix} 1 \\ \textcolor{#b45309}{\psi} \end{bmatrix}.

Since ϕ\textcolor{#047857}{\phi} is the larger absolute eigenvalue, for large nn the vector vn=[FnFn+1]v_n = \begin{bmatrix} F_n \\ F_{n+1} \end{bmatrix} points in the direction [1ϕ]\begin{bmatrix} 1 \\ \textcolor{#047857}{\phi} \end{bmatrix}. In other words, for large nn the ratio Fn+1Fn→ϕ=1+52\dfrac{F_{n+1}}{F_n} \to \textcolor{#047857}{\phi} = \dfrac{1 + \sqrt{5}}{2}.

18.3.1 Deriving Binet's formula

The eigendecomposition of MM is

M=VDV−1=[11ϕψ]⏟V[ϕ00ψ]⏟D1ψ−ϕ[ψ−1−ϕ1]⏟V−1\begin{aligned} M &= VDV^{-1} \\ &= \underbrace{\begin{bmatrix} 1 & 1 \\ \textcolor{#047857}{\phi} & \textcolor{#b45309}{\psi} \end{bmatrix}}_{V} \underbrace{\begin{bmatrix} \textcolor{#047857}{\phi} & 0 \\ 0 & \textcolor{#b45309}{\psi} \end{bmatrix}}_{D} \underbrace{\frac{1}{\textcolor{#b45309}{\psi} - \textcolor{#047857}{\phi}} \begin{bmatrix} \textcolor{#b45309}{\psi} & -1 \\ -\textcolor{#047857}{\phi} & 1 \end{bmatrix}}_{V^{-1}} \end{aligned}

Because vn=Mvn−1=Mnv0=VDnV−1v0v_n = M v_{n-1} = M^n v_0 = VD^nV^{-1}v_0, and using 1ψ−ϕ=−15\dfrac{1}{\textcolor{#b45309}{\psi} - \textcolor{#047857}{\phi}} = \dfrac{-1}{\sqrt{5}}, we can compute vnv_n in closed form:

[FnFn+1]=VDnV−1v0=[11ϕψ][ϕn00ψn]1ψ−ϕ[ψ−1−ϕ1][01]=15[ϕn−ψnϕn+1−ψn+1]\begin{aligned} \begin{bmatrix} F_n \\ F_{n+1} \end{bmatrix} &= VD^nV^{-1}v_0 \\ &= \begin{bmatrix} 1 & 1 \\ \textcolor{#047857}{\phi} & \textcolor{#b45309}{\psi} \end{bmatrix} \begin{bmatrix} \textcolor{#047857}{\phi^n} & 0 \\ 0 & \textcolor{#b45309}{\psi^n} \end{bmatrix} \frac{1}{\textcolor{#b45309}{\psi} - \textcolor{#047857}{\phi}} \begin{bmatrix} \textcolor{#b45309}{\psi} & -1 \\ -\textcolor{#047857}{\phi} & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{bmatrix} \textcolor{#047857}{\phi^n} - \textcolor{#b45309}{\psi^n} \\ \textcolor{#047857}{\phi^{n+1}} - \textcolor{#b45309}{\psi^{n+1}} \end{bmatrix} \end{aligned}

Reading off the first entry gives Binet's formula for the nn-th Fibonacci number:

Fn=ϕn−ψn5=15[(1+52)n⏟ϕn−(1−52)n⏟ψn]\begin{aligned} F_n &= \frac{\textcolor{#047857}{\phi^n} - \textcolor{#b45309}{\psi^n}}{\sqrt{5}} \\ &= \frac{1}{\sqrt{5}} \left[ \underbrace{\left( \frac{1 + \sqrt{5}}{2} \right)^n}_{\textcolor{#047857}{\phi^n}} - \underbrace{\left( \frac{1 - \sqrt{5}}{2} \right)^n}_{\textcolor{#b45309}{\psi^n}} \right] \end{aligned}

18.4 Generalizing to any linear sum of the last two values

This chain of reasoning is not special to Fibonacci: it works for any sequence where each term is a linear combination of the previous two. A slightly more general version is

a0=a,a1=b,an+2=p⋅an+q⋅an+1a_0 = a, \quad a_1 = b, \quad a_{n+2} = \textcolor{#1d4ed8}{p} \cdot \textcolor{#1d4ed8}{a_n} + \textcolor{#be185d}{q} \cdot \textcolor{#be185d}{a_{n+1}}

Here the same packing gives

vn+1=[an+1an+2]=[an+1p⋅an+q⋅an+1⏟the recurrence]=[01pq][anan+1]=[01pq]vn\begin{aligned} v_{n+1} &= \begin{bmatrix} a_{n+1} \\ a_{n+2} \end{bmatrix} \\ &= \begin{bmatrix} a_{n+1} \\ \underbrace{\textcolor{#1d4ed8}{p} \cdot \textcolor{#1d4ed8}{a_n} + \textcolor{#be185d}{q} \cdot \textcolor{#be185d}{a_{n+1}}}_{\text{the recurrence}} \end{bmatrix} \\ &= \begin{bmatrix} \textcolor{#1d4ed8}{0} & \textcolor{#be185d}{1} \\ \textcolor{#1d4ed8}{p} & \textcolor{#be185d}{q} \end{bmatrix} \begin{bmatrix} \textcolor{#1d4ed8}{a_n} \\ \textcolor{#be185d}{a_{n+1}} \end{bmatrix} \\ &= \begin{bmatrix} \textcolor{#1d4ed8}{0} & \textcolor{#be185d}{1} \\ \textcolor{#1d4ed8}{p} & \textcolor{#be185d}{q} \end{bmatrix} v_n \end{aligned}

with v0=[ab]v_0 = \begin{bmatrix} a \\ b \end{bmatrix}. The remaining steps are identical: find the eigenvalues and eigenvectors of this matrix, then use its eigendecomposition to write the nn-th value in closed form.

18.5 Linear recurrence relations

The most general version of this idea is a linear recurrence relation:

at=c1at−1+c2at−2+⋯+cnat−n+ka_t = \textcolor{#1d4ed8}{c_1 a_{t-1}} + \textcolor{#be185d}{c_2 a_{t-2}} + \cdots + \textcolor{#047857}{c_n a_{t-n}} + \textcolor{#0d9488}{k}

where the cic_i and kk are constants. The approach is unchanged in spirit: stack the last nn terms into a vector

vn=[at−nat−n+1⋮at−1]v_n = \begin{bmatrix} a_{t-n} \\ a_{t-n+1} \\ \vdots \\ a_{t-1} \end{bmatrix}

and find a matrix MM (plus a constant vector ww to absorb the kk term) so that vn+1=Mvn+wv_{n+1} = M v_n + w. Once again the powers of MM, through its eigendecomposition, carry all the information about how the sequence grows.

Another place higher powers of a matrix show up is Markov chains, where repeatedly applying a transition matrix drives a probability distribution toward a steady state. We look at them next.

← 17. Powers of a matrix · 19. Markov matrices →