Linear Algebra/Topic: Linear Recurrences/Solutions

Solutions

Problem 1

Solve each homogeneous linear recurrence relations.

$f(n+1)=5f(n)-6f(n-1)$
$f(n+1)=4f(n)$
$f(n+1)=6f(n)+7f(n-1)+6f(n-2)$

Answer

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.
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.
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.

$f(0)=1$ , $f(1)=1$
$f(0)=0$ , $f(1)=1$
$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_{n}f(n)+\dots +a_{n-k}f(n-k)$ , let $r_{1}$ , ..., $r_{k}$ be the roots of the associated polynomial.

Prove that each function
$f_{r_{i}}(n)=r_{k}^{n}$ satisfies the recurrence (without initial conditions).
Prove that no $r_{i}$ is $0$ .
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?

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.