Linear Recursion Equations
November 24th, 2005 ~ Posted in: MathematicsThis 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)
This entry was posted on Thursday, November 24th, 2005 at 7:56 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
Leave a Reply