 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/d/solution

A = S D S^{- 1}

and hence

A^{n - 1} = S D^{n - 1} S^{- 1}

: the intervening factors

S^{- 1} S

cancel. The diagonal matrix power has entries

α^{n - 1}, β^{n - 1}

. Since

1 - β = α

and

α - 1 = - β

S^{- 1} (11) = \frac{1}{5} (α - β), V_{n} = \frac{1}{5} (α^{n + 1} - β^{n + 1} α^{n} - β^{n}) .

U_{n} = \frac{( ( 1 + 5 ) /2 ) ^{n} - ( ( 1 - 5 ) /2 ) ^{n}}{5} .

The derivation includes

n = 1

, and the expression gives

U_{1} = U_{2} = 1

, consistent with the specified indexing.

 New to topics? Read the docs here!