3.4 Section 1.3. difference equations, characteristic polynomial, simple and repeated roots, analytic solution and stability

Given a linear recursive equation such as $x_{n+1}=f(x_n,x_{n-1,}\cdots )$, 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.

3.4.1 Example simple roots, no repeated roots

$$\begin{array}{rl}{x}_{n+1}& =3x_n-2x_{n-1}\\ E^2{x}_{n-1}& =3E{x}_{n-1}-2E^0{x}_{n-1}\\ (E^2-3E+2)x_{n-1}& =0\end{array}$$

Solve $P(E)=0$, we get roots ${\lambda }_1=2,{\lambda }_2=1$, hence simple distinct roots. Hence explicit solution is

$$\begin{array}{rl}{x}_n& =A_1{\lambda }_1^n+A_2{\lambda }_2^n\\ & =A_1{2}^n+A_2\end{array}$$

Now $A_1$ and $A_2$ can be found from initial conditions

3.4.2 Example simple roots, repeated roots

$$4x_n+7x_{n-1}+2x_{n-2}-x_{n-3}=0$$

$$P(E)=4E^3{x}_{n-3}+7E^2{x}_{n-3}+2E{x}_{n-3}-E^0{x}_{n-3}=0$$

Hence roots are found from ${(E+1)}^2(4E-1)=0$, so ${\lambda }_1={\lambda }_2=-1$ repeated 2 times, and ${\lambda }_3=\frac{1}{4}$

hence solution is $$x_n=(A_1{\lambda }_1^n+A_{2}n{\lambda }_2^{n-1})+A_3{\lambda }_3^n$$

so it a root is repeated $k$ times, we write

$$x_n=(A_1{\lambda }_1^n+A_{2}n{\lambda }_2^{n-1}+A_{3}n(n-1){\lambda }_3^{n-2}+\cdots +A_{k}n(n-1)(n-2)\cdots \left({\lambda }_k^{n-k+1}\right))+A_{k+1}{\lambda }_{k+1}^n$$

so here we have $$x_n=A_1{(-1)}^n+A_{2}n{(-1)}^{n-1}+A_3{\left(\frac{1}{4}\right)}^n$$

and use I.C. to find the coefficients.

3.4.3 Bounded sequence

sequence $x_n=[x_1,x_2,\cdots ]$ is bounded if there is a constant $c$ s.t. $\left|x_n\right|\le c$ for all $n$. i.e. $\underset{n}{sup}\left|x_n\right|<\mathrm{\infty }$

3.4.3.1 Stable solution for the difference equation $P(E)x=0$

$P(E)x=0$ is stable if all its solutions are stable.

Theorem: polynomial $p$ satisfying $P(0)\ne 0$ the difference equation $P(E)x=0$ is stable iff all simple roots of $p\left(E\right)=0$ are $\le 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