Linear Recurrences

Chapter 3 • Section 3-4

"Predicting the future, one step at a time. 🔮"

🐇 The Fibonacci Sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each number is the sum of the previous two:

$$ F_{k+2} = F_{k+1} + F_k $$

0 1

We can write the recurrence as a matrix equation $\vec{v}_{k+1} = A \vec{v}_k$:

$$ \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix} $$

Now we can use powers of $A$ to find any term!

Using eigenvalues $\lambda = \frac{1 \pm \sqrt{5}}{2}$:

$$ F_k = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^k - \left(\frac{1-\sqrt{5}}{2}\right)^k \right) $$

Derived from $A = PDP^{-1}$!

Initial values: $x_0=0, x_1=1$.

Matrix: $A = \begin{bmatrix} 0 & 1 \\ -6 & 5 \end{bmatrix}$.
Eigenvalues: $\lambda^2 - 5\lambda + 6 = 0 \implies (\lambda-2)(\lambda-3)=0$. So $\lambda_1=2, \lambda_2=3$.
Eigenvectors: $\vec{v}_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \vec{v}_2 = \begin{bmatrix} 1 \\ 3 \end{bmatrix}$.
General Solution: $\vec{v}_k = c_1 2^k \vec{v}_1 + c_2 3^k \vec{v}_2$.
Solve for Constants: At $k=0$, $\begin{bmatrix} 0 \\ 1 \end{bmatrix} = c_1 \begin{bmatrix} 1 \\ 2 \end{bmatrix} + c_2 \begin{bmatrix} 1 \\ 3 \end{bmatrix}$. Solution: $c_1=-1, c_2=1$.
Final Formula: $x_k = 3^k - 2^k$.

For the recurrence $x_{k+1} = 3x_k - 2y_k$ and $y_{k+1} = x_k + y_k$, what is the matrix $A$?

If all $|\lambda| < 1$, the system goes to $\vec{0}$.

The origin is a "sink".

If all $|\lambda| > 1$, the system explodes away.

The origin is a "source".

If some $|\lambda| > 1$ and some $|\lambda| < 1$.

If eigenvalues are $0.5$ and $0.8$, what happens to $\vec{v}_k$ as $k \to \infty$?