Linear Recursion Equations
This year, let us give thanks for linear algebra, one of the greatest tools available to mathematicians. In particular, let us be thankful for matrix theory, which helps us to painlessly solve linear recursion equations such as:
Note that therefore, this method can be used to painlessly derive the mysterious formula for the Fibonacci series. How, you ask? By what serendipitous conspiracy of fate can matrices help us with these sorts of problems? Well, read on.
Given 
, let 
, then we have
![\displaystyle u_{n+1} = \left[ \begin{matrix} x_{n+2} \\ x_{n+1} \end{matrix} \right] = \left[ \begin{matrix} 2x_{n+1} + 3x_n \\ x_{n+1} \end{matrix} \right] = \left[ \begin{matrix} 2 & 3 \\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} x_{n+1} \\ x_n \end{matrix} \right] = A u_n,](/cz/latexrender/pictures/6d48e9558083f221cf3b4046920b69ec.png "\displaystyle u_{n+1} = \left[ \begin{matrix} x_{n+2} \\ x_{n+1} \end{matrix} \right] = \left[ \begin{matrix} 2x_{n+1} + 3x_n \\ x_{n+1} \end{matrix} \right] = \left[ \begin{matrix} 2 & 3 \\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} x_{n+1} \\ x_n \end{matrix} \right] = A u_n,")
so clearly 
.
In general, I guess this is as far as you can go easily, then you are faced with the problem of finding a general form for 
. However, if 
is diagonalizable, as it is in this case, we have 
, which is easily calculated. Doing so,
![\displaystyle u_n = A^n u_0 = \left[ \begin{matrix} 3 & -1 \\ 1 & 1 \end{matrix}\right] \left[ \begin{matrix} 3^n & 0 \\ 0 & (-1)^n \end{matrix} \right] \left[ \begin{matrix} \frac{1}{4} & \frac{1}{4} \\ -\frac{1}{4} & \frac{3}{4} \end{matrix} \right] \left[ \begin{matrix} 1 \\ 1 \end{matrix} \right],](/cz/latexrender/pictures/48fa22e63df794a2e16132650c9f18a7.png "\displaystyle u_n = A^n u_0 = \left[ \begin{matrix} 3 & -1 \\ 1 & 1 \end{matrix}\right] \left[ \begin{matrix} 3^n & 0 \\ 0 & (-1)^n \end{matrix} \right] \left[ \begin{matrix} \frac{1}{4} & \frac{1}{4} \\ -\frac{1}{4} & \frac{3}{4} \end{matrix} \right] \left[ \begin{matrix} 1 \\ 1 \end{matrix} \right],")
so 
.
Now you may enjoy your mathematically enhanced turkey feast. (Actually, now I see this method is just a slight retasking of the technique I learned oh-so-long-ago for solving a system of ODEs)
Possibly relevant posts:
- problems out of context (3/17/2007)
- What good are eigensystems? (9/16/2005)
- Greens Theorem (9/5/2004)