Given a linear recursive equation such as \(x_{n+1}=f\left (x_{n},x_{n-1,}\cdots \right ) \), the goal is to find an non-recursive solution for \(x_{n}\)
To do that, we introduce the shift operator \(E\), rewrite the recursive equation in terms of \(E\), we get a polynomial in \(E\) which we solve. and depending on how the root come out, we get a solution for \(x_{n}\), which is called the explicit solution.
Notice that the explicit solution gives the value of \(x_{n}\) right away as a function of \(n\). No recursion is needed to find \(x\) for some specific \(n\), hence one can get numerical problems with the recursive solution due to cancellation errors, while the explicit solution will not show this problem. It is always better to use the explicit solution.
\begin {align*} x_{n+1} & =3x_{n}-2x_{n-1}\\ E^{2}x_{n-1} & =3Ex_{n-1}-2E^{0}x_{n-1}\\ \left (E^{2}-3E+2\right ) x_{n-1} & =0 \end {align*}
Solve \(P\relax (E) =0\), we get roots \(\lambda _{1}=2,\lambda _{2}=1\), hence simple distinct roots. Hence explicit solution is
\begin {align*} x_{n} & =A_{1}\lambda _{1}^{n}+A_{2}\lambda _{2}^{n}\\ & =A_{1}2^{n}+A_{2} \end {align*}
Now \(A_{1}\) and \(A_{2}\) can be found from initial conditions
\[ 4x_{n}+7x_{n-1}+2x_{n-2}-x_{n-3}=0 \]
\[ P\relax (E) =4E^{3}x_{n-3}+7E^{2}x_{n-3}+2Ex_{n-3}-E^{0}x_{n-3}=0 \]
Hence roots are found from \(\left (E+1\right ) ^{2}\left (4E-1\right ) =0\), so \(\lambda _{1}=\lambda _{2}=-1\) repeated 2 times, and \(\lambda _{3}=\frac {1}{4}\)
hence solution is \[ x_{n}=\left (A_{1}\lambda _{1}^{n}+A_{2}n\lambda _{2}^{n-1}\right ) +A_{3}\lambda _{3}^{n}\]
so it a root is repeated \(k\) times, we write
\[ x_{n}=\left (A_{1}\lambda _{1}^{n}+A_{2}n\lambda _{2}^{n-1}+A_{3}n\left ( n-1\right ) \lambda _{3}^{n-2}+\cdots +A_{k}n\left (n-1\right ) \left ( n-2\right ) \cdots \left (\lambda _{k}^{n-k+1}\right ) \right ) +A_{k+1}\lambda _{k+1}^{n}\]
so here we have \[ x_{n}=A_{1}\left (-1\right ) ^{n}+A_{2}n\left (-1\right ) ^{n-1}+A_{3}\left (\frac {1}{4}\right ) ^{n}\]
and use I.C. to find the coefficients.
sequence \(x_{n}=[x_{1},x_{2},\cdots ]\) is bounded if there is a constant \(c\) s.t. \(\left \vert x_{n}\right \vert \leq c\) for all \(n\). i.e. \(\sup _{n}\left \vert x_{n}\right \vert <\infty \)
\(P\relax (E) x=0\) is stable if all its solutions are stable.
Theorem: polynomial \(p\) satisfying \(P\relax (0) \neq 0\) the difference equation \(P\relax (E) x=0\) is stable iff all simple roots of \(p\left ( E\right ) =0\) are \(\leq 1\) and all repeated roots are \(<1\)
So to find if a recursive equation is stable, find the roots of \(P\left ( E\right ) =0\) and check as per above