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)$

Answer

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?