# 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_12^n+c_23^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 betwween $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_nf(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?