Linear Algebra/Topic: Linear Recurrences/Solutions

From Wikibooks, open books for an open world
< Linear Algebra‎ | Topic: Linear Recurrences
Jump to: navigation, search

Solutions[edit]

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_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?