Linear Recurrences

Solve each homogeneous linear recurrence relations.

• $f(n)=5f(n-1)-6f(n-2)$

• $f(n)=4f(n-2)$

• $f(n)=5f(n-1)-2f(n-2)-8f(n-3)$

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

Check that the isomorphism given between $S$ and $\mathbb{R}^{k}$ is a linear map.

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

Given a homogeneous linear recurrence relation $f(n)=a_{n}f(n-1)+\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).