# Linear Algebra/Topic: Linear Recurrences/Solutions

## Solutions

Problem 1

Solve each homogeneous linear recurrence relations.

1. $f(n+1)=5f(n)-6f(n-1)$
2. $f(n+1)=4f(n)$
3. $f(n+1)=6f(n)+7f(n-1)+6f(n-2)$
1. We express the relation in matrix form.
${\begin{pmatrix}5&-6\\1&0\end{pmatrix}}{\begin{pmatrix}f(n)\\f(n-1)\end{pmatrix}}={\begin{pmatrix}f(n+1)\\f(n)\end{pmatrix}}$
The characteristic equation of the matrix
${\begin{vmatrix}5-\lambda &-6\\1&-\lambda \end{vmatrix}}=\lambda ^{2}-5\lambda +6$
has roots of $2$  and $3$ . Any function of the form $f(n)=c_{1}2^{n}+c_{2}3^{n}$  satisfies the recurrence.
2. This is like the prior part, but simpler. The matrix expression of the relation is
${\begin{pmatrix}4\end{pmatrix}}{\begin{pmatrix}f(n)\end{pmatrix}}={\begin{pmatrix}f(n+1)\end{pmatrix}}$
and the characteristic equation of the matrix
${\begin{vmatrix}4-\lambda \end{vmatrix}}=4-\lambda$
has the single root $4$ . Any function of the form $f(n)=c4^{n}$  satisfies this recurrence.
3. In matrix form the relation
${\begin{pmatrix}6&7&6\\1&0&0\\0&1&0\end{pmatrix}}{\begin{pmatrix}f(n)\\f(n-1)\\f(n-2)\end{pmatrix}}={\begin{pmatrix}f(n+1)\\f(n)\\f(n-1)\end{pmatrix}}$
gives this characteristic equation.
${\begin{vmatrix}6-\lambda &7&6\\1&-\lambda &0\\0&1&-\lambda \end{vmatrix}}=-\lambda ^{3}+6\lambda ^{2}+7\lambda +6$
Problem 2

Give a formula for the relations of the prior exercise, with these initial conditions.

1. $f(0)=1$ , $f(1)=1$
2. $f(0)=0$ , $f(1)=1$
3. $f(0)=1$ , $f(1)=1$ , $f(2)=3$ .
Problem 3

Check that the isomorphism given between $S$  and $\mathbb {R} ^{k}$  is a linear map. It is argued above that this map is one-to-one. What is its inverse?

Problem 4

Show that the characteristic equation of the matrix is as stated, that is, is the polynomial associated with the relation. (Hint: expanding down the final column, and using induction will work.)

Problem 5

Given a homogeneous linear recurrence relation $f(n+1)=a_{n}f(n)+\dots +a_{n-k}f(n-k)$ , let $r_{1}$ , ..., $r_{k}$  be the roots of the associated polynomial.

1. Prove that each function $f_{r_{i}}(n)=r_{k}^{n}$  satisfies the recurrence (without initial conditions).
2. Prove that no $r_{i}$  is $0$ .
3. Prove that the set $\{f_{r_{1}},\dots ,f_{r_{k}}\}$  is linearly independent.
Problem 6

(This refers to the value $T(64)=18,446,744,073,709,551,615$  given in the computer code below.) Transferring one disk per second, how many years would it take the priests at the Tower of Hanoi to finish the job?