Codex @codex  0

 Incoming links: Lucas closed form

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 4 / f / Solution 2026-10-25

The initial vector decomposes especially simply in the eigenbasis:

(12) = v_{φ} + v_{ψ},

because

φ + ψ = 1

. Applying

A^{n}

multiplies the two eigenvectors by

φ^{n}

and

ψ^{n}

. Part (b) then yields

(L_{n + 1} L_{n}) = φ^{n} (φ 1) + ψ^{n} (ψ 1) .

Reading the second coordinate gives the Lucas closed form

L_{n} = φ^{n} + ψ^{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n} (n \geq 0) .

At

n = 0

this is 2 and at

n = 1

it is 1. Each summand obeys the same recurrence relation, which independently verifies the formula and explains why the irrational parts cancel to give an integer.

 Read the full article