Section 8 of 11 · Notes pages 69–72
Linear Constant Coefficient Difference Equations
Difference equations written as a matrix recursion and solved with eigenvectors, or with the roots of the characteristic equation, including repeated roots.
Linear Constant Coefficient Difference Equations
A difference equation defines a sequence by a rule that gives each term from the previous ones. A linear constant-coefficient difference equation of order \(k\) has the form \[\underbrace{x[n]=\underbrace{a_1}_{\text{coefficient}}x[n-1]+\cdots+\underbrace{a_k}_{\text{coefficient}}x[n-k]}_{k^{\text{th}}\text{-order difference equation}}\] Such equations appear very often in discrete-time systems and in discretized models of continuous-time systems. A good way to study them is to turn the single order-\(k\) equation into a first-order equation for a vector. Stack the \(k\) most recent values into a vector \(\xx_n\). Then the next vector is obtained from the current one by a fixed matrix \(\mA\), the companion matrix, whose first row holds the coefficients and whose other rows just shift the older values down: \[\xx_n=\col{x[n]\\\vdots\\x[n-k+1]},\quad\mA=\col{a_1&\cdots&a_k\\1&&0\\&\ddots&\vdots\\&1&0}=\left[\begin{array}{c}\begin{matrix}a_1&\cdots&a_k\end{matrix}\\\begin{matrix}\mI_{k-1}&\boldsymbol{0}\end{matrix}\end{array}\right].\]
Applying this rule again and again, starting from the initial conditions \(\xx_0\), gives \[\xx_n=\mA(\mA(\cdots(\mA\xx_0)\cdots))=\mA^n\xx_0,\qquad\xx_0=\underbrace{\col{x[0]\\\vdots\\x[-k+1]}}_{\text{initial conditions}}.\] So, in principle, \(\xx_n\) for any \(n\) can be found by multiplying \(\xx_0\) by \(\mA\) a total of \(n\) times. This is not efficient, and it does not give a closed-form answer. Eigenvectors give more insight.
Theorem DE.1
If \((\lambda,\xx_0)\) is an eigenpair of \(\mA\), then the solution of \(\xx_n=\mA\xx_{n-1}\) that starts at \(\xx_0\) is \(\xx_n=\lambda^n\xx_0\).
Proof \(\xx_n=\mA^n\xx_0=\lambda^n\xx_0\), since each multiplication by \(\mA\) just multiplies the eigenvector by \(\lambda\).
Theorem DE.2
If the starting vector is not an eigenvector, we can still handle it when \(\mA\) has enough eigenvectors: write \(\xx_0\) as a combination of eigenvectors and let each one evolve by itself.
If \(\mA\) has a full set of eigenvectors \(\vv_i\) that span \(\R^k\), then \(\xx_n=\mA^n\xx_0\) is given by \[\xx_n=\sum_{i=1}^k\alpha_i\lambda_i^n\vv_i\quad\text{where}\quad\xx_0=\sum_{i=1}^k\alpha_i\vv_i.\]
Proof Multiply the expansion of \(\xx_0\) by \(\mA^n\), and use \(\mA^n\vv_i=\lambda_i^n\vv_i\): \[\mA^n\xx_0=\mA^n\left(\sum_{i=1}^k\alpha_i\vv_i\right)=\sum_{i=1}^k\alpha_i\mA^n\vv_i=\underbrace{\sum_{i=1}^k\alpha_i\lambda_i^n\vv_i}_{\xx_n}.\quad\blacksquare\] Example Solve \(x[n]=2x[n-1]+x[n-2]\) with initial conditions \(x[0]=3\) and \(x[-1]=1\). Here \(k=2\) and the companion matrix has eigenvalues \(1\pm\sqrt2\): \[\xx_n=\col{x[n]\\x[n-1]},\quad\mA=\col{2&1\\1&0}\Rightarrow\underbrace{\lambda_1=1+\sqrt2;\quad\lambda_2=1-\sqrt2}_{\text{eigenvalues}}.\] We find the eigenvectors by solving \((\mA-\lambda\mI)\vv=\nul\). For \(\lambda_1\): \[(\mA-(1+\sqrt2)\mI)\vv=\nul\Rightarrow\col{1-\sqrt2&1\\1&-1-\sqrt2}\col{v_1\\v_2}=\col{0\\0}\Rightarrow\vv_1=\col{1+\sqrt2\\1}.\] For \(\lambda_2\): \[(\mA-(1-\sqrt2)\mI)\vv=\nul\Rightarrow\col{1+\sqrt2&1\\1&-1+\sqrt2}\col{v_1\\v_2}=\col{0\\0}\Rightarrow\vv_2=\col{-1+\sqrt2\\-1}.\] Next we express the initial vector \(\xx_0=\col{x[0]\\x[-1]}=\col{3\\1}\) in the eigenvectors: \[\xx_0=\col{3\\1}=\alpha_1\vv_1+\alpha_2\vv_2=\col{1+\sqrt2&-1+\sqrt2\\1&-1}\col{\alpha_1\\\alpha_2}\] \[\Rightarrow\alpha_2=\frac{2-\sqrt2}{2\sqrt2}=\frac{\sqrt2-1}{2}=-\frac{1-\sqrt2}{2},\qquad\alpha_1=1+\alpha_2=\frac{\sqrt2+1}{2}.\] By Theorem DE.2, \begin{align*} \xx_n&=\alpha_1\lambda_1^n\vv_1+\alpha_2\lambda_2^n\vv_2\\ &=\frac{\sqrt2+1}{2}(1+\sqrt2)^n\col{1+\sqrt2\\1}-\frac{1-\sqrt2}{2}(1-\sqrt2)^n\col{\sqrt2-1\\-1}\\ \Rightarrow\xx_n&=\col{\dfrac{(1+\sqrt2)^{n+2}}2+\dfrac{(1-\sqrt2)^{n+2}}2\\[6pt]\dfrac{(1+\sqrt2)^{n+1}}2+\dfrac{(1-\sqrt2)^{n+1}}2}. \end{align*} The first component of \(\xx_n\) is \(x[n]\):
As a check, this gives \(x[0]=3\), and the recursion gives \(x[1]=2\cdot3+1=7\), which the formula also gives.
There is a quicker way to the same answer, based on one observation. Given the difference equation \[x[n]=a_1x[n-1]+a_2x[n-2]+\cdots+a_kx[n-k],\] try a solution of the form \(x[n]=r^n\). It works exactly when \[r^n=a_1r^{n-1}+a_2r^{n-2}+\cdots+a_kr^{n-k}\] or, moving everything to one side, \[r^n-a_1r^{n-1}-a_2r^{n-2}-\cdots-a_kr^{n-k}=0\quad\forall n.\] Factoring out \(r^{n-k}\) leaves a polynomial in \(r\): \[\Rightarrow r^{n-k}\underbrace{(r^k-a_1r^{k-1}-a_2r^{k-2}-\cdots-a_k)}_{\text{characteristic equation of the difference equation}}=0.\] So \(r^n\) is a solution exactly when \(r\) is a root of the characteristic equation of the difference equation. This is the same polynomial (up to a sign) as \(\det(\mA-r\mI)\) for the companion matrix \(\mA\) above, so the roots \(r\) are exactly the eigenvalues of \[\mA=\left[\begin{array}{c}\begin{matrix}a_1&\cdots&a_k\end{matrix}\\\begin{matrix}\mI_{(k-1)}&\begin{matrix}0\\\vdots\\0\end{matrix}\end{matrix}\end{array}\right].\] There are at most \(k\) distinct roots. If they are all distinct, a general solution is any combination of the corresponding powers:
The constants \(\alpha_i\) are fixed by the initial conditions, given either as \(x[0],\ldots,x[-k+1]\) or as \(x[-1],\ldots,x[-k]\). For the second form, evaluating the formula at \(n=-1,\ldots,-k\) gives a linear system for the \(\alpha_i\) with an invertible coefficient matrix: \[\underbrace{\col{r_1^{-1}&r_2^{-1}&\cdots&r_k^{-1}\\r_1^{-2}&r_2^{-2}&\cdots&r_k^{-2}\\\vdots&&&\vdots\\r_1^{-k}&r_2^{-k}&\cdots&r_k^{-k}}}_{\text{invertible}}\col{\alpha_1\\\vdots\\\alpha_k}=\col{x[-1]\\\vdots\\x[-k]}.\] Example Apply this approach to the previous example.
The difference equation is \(x[n]=2x[n-1]+x[n-2]\), with characteristic equation \(r^2-2r-1=0\) and roots \(r_1=1+\sqrt2\) and \(r_2=1-\sqrt2\). So \(x[n]=\alpha_1r_1^n+\alpha_2r_2^n\). The initial conditions \(x[0]=3\) and \(x[-1]=1\) give two equations: \[\begin{gathered}3=\alpha_1+\alpha_2\\1=\underbrace{\dfrac{\alpha_1}{r_1}+\dfrac{\alpha_2}{r_2}}_{r_1r_2=r_2\alpha_1+r_1\alpha_2}\end{gathered}\Rightarrow\begin{gathered}\alpha_1=\dfrac{r_1r_2-3r_1}{r_2-r_1}=\dfrac{4+3\sqrt2}{2\sqrt2}\\\alpha_2=3-\alpha_1=\dfrac{3\sqrt2-4}{2\sqrt2}.\end{gathered}\] Hence \[x[n]=\left(\frac{4+3\sqrt2}{2\sqrt2}\right)(1+\sqrt2)^n+\left(\frac{3\sqrt2-4}{2\sqrt2}\right)(1-\sqrt2)^n,\quad n\ge0.\] This looks different from the first answer, but it is the same sequence: both give \(x[0]=3\), \(x[1]=7\), \(x[2]=17\), \(x[3]=41,\ldots\)
Example The second approach also handles repeated roots, with one change. Consider \[x[n]=2x[n-1]-x[n-2],\quad x[-1]=3,\quad x[-2]=4.\] The characteristic equation is \(r^2-2r+1=0\), so \(r_1=r_2=1\) is a double root. When a root is repeated, the solution takes the form \[x[n]=\alpha_1r_1^n+\alpha_2nr_1^n.\] (A proof for the similar situation of differential equations is given later.) The initial conditions give \begin{align*} x[-1]=3&=\alpha_1r_1^{-1}-\alpha_2r_1^{-1}=(\alpha_1-\alpha_2)r_1^{-1}\\ x[-2]=4&=\alpha_1r_1^{-2}-2\alpha_2r_1^{-2}=(\alpha_1-2\alpha_2)r_1^{-2}. \end{align*} With \(r_1=1\) these are two simple equations: \[\Rightarrow\begin{gathered}\alpha_1-\alpha_2=3r_1=3\\\alpha_1-2\alpha_2=4r_1^2=4\end{gathered}\quad\Big\}\quad\alpha_2=-1,\quad\alpha_1=2.\] Therefore \[\Rightarrow x[n]=2-n,\quad n\ge0.\]