 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/digital-systems-linear-algebra-introduction-to-formal-proof/4/c/solution

The initial vector records both initial Fibonacci numbers:

V_{1} = (U_{2}, U_{1})^{⊤} = (1, 1)^{⊤}

. For

n \geq 2

A V_{n - 1} = (1110) (U_{n} U_{n - 1}) = (U_{n} + U_{n - 1} U_{n}) = V_{n} .

Conversely this vector recurrence forces the second component to be the preceding first component and forces their sum to be the next first component, recovering the scalar recurrence and its initial conditions. Iterating, or using mathematical induction, yields $V_{n} = A^{n - 1} (1, 1)^{⊤}$ for every

n \geq 1

 New to topics? Read the docs here!