Difference Equation
Difference Equation
To solve difference equation like \(x_t = a_{t-1} x_{t-1} + a_{t-2} x_{t-2} + \dots + a_0\), we first rewrite it into the matrix form:
\[ \left[ \begin{array} \\ x_t \\ x_{t-1} \\ \vdots \\ x_2 \\ x_1 \end{array} \right] = \underbrace{ \left[ \begin{array} \\ a_{t-1} & a_{t-2} & \cdots & a_1 & a_0 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & \vdots \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{array} \right] }_{A} \left[ \begin{array} \\ x_{t-1} \\ x_{t-2} \\ \vdots \\ x_1 \\ x_0 \end{array} \right] \]
To solve it, we try to find the eigenvalues and eigenvectors of \(A\): \[ A - \lambda I = \left[ \begin{array} \\ a_{t-1} - \lambda & a_{t-2} & \cdots & a_1 & a_0 \\ 1 & -\lambda & \cdots & 0 & 0 \\ 0 & 1 & \cdots & \vdots & 0 \\ \vdots & \vdots & \ddots & -\lambda & \vdots \\ 0 & 0 & \cdots & 1 & -\lambda \end{array} \right] \] Apply Laplacian expansion along the first column to get its determinant as \[ \det (A - \lambda I) = (a_{t-1} -\lambda) (-\lambda)^{t-1} - \det B_{t-1} \] where \[ B_{t-1} = \underbrace{ \begin{bmatrix} a_{t-2} & a_{t-3} & \cdots & a_1 & a_0 \\ 1 & -\lambda & \cdots & 0 & 0 \\ 0 & 1 & \cdots & \vdots & 0 \\ \vdots & \vdots & \ddots & -\lambda & \vdots \\ 0 & 0 & \cdots & 1 & -\lambda \end{bmatrix} }_\text{$t-1$ columns} \] Apply Laplacian expansion along the first column of \(B_{n-1}\) to give the following recurrence relation: \[ \left. \begin{array} \\ \det B_{t-1} = a_{t-2} (-\lambda)^{t-2} - \det B_{t-2} \\ \det B_1 = a_0 \end{array} \right\} \Rightarrow \det B_{t-1} = (-1)^t (a_{t-2} \lambda^{t-2} + a_{t-3} \lambda^{t-3} + \dots + a_0) \] In all, \[ \begin{aligned} \det (A - \lambda I) &= (a_{t-1} - \lambda)(-\lambda)^{t-1} - (-1)^t (a_{t-2} \lambda^{t-2} + a_{t-3} \lambda^{t-3} + \dots + a_0) \\ &= (-1)^t (\lambda^t - a_{t-1} \lambda^{t-1} - a_{t-2} \lambda^{t-2} - \dots - a_0) \end{aligned} \]
After solving the eigenvalues \(\lambda_1 \ge \dots \ge \lambda_t\) and corresponding eigenvectors \(\newcommand{\v}{\mathrm{v}} \v_1, \dots, \v_t\) from above equation, we can rewrite the vector formed by the initial \(t\) terms as the linear combination of \(\v_1, \dots, \v_t\): \[ \x_0 = \left[ x_{t-1}, \cdots, x_0 \right]^T = c_1 \v_1 + \dots c_t \v_t \] Then for every \(n \ge t\), \[ x_n = \left[ A^{n-t+1} \x_0 \right]_0 = \left[ \lambda_1^{n-t+1} c_1 \v_1 + \dots + \lambda_t^{n-t+1} c_t \v_t\right]_0 \] \(x_n\) will be asymptotic to \(\lambda_1^{n}\) as \(n \to \infty\).