In this section, we will only be interestd in LTI difference equations and ignore the more general cases.
Definition: Define the operator $\Delta$ as
\begin{eqnarray}
\Delta y[n] = y[n+1]
\end{eqnarray}
$\Delta$ plays the same role in difference equations as $ D = \frac{d}{dx}$ plays in differential equations.
Example: Consider the discrete function $x[n] = n^2 – 2n + U[n-4]$. Then $x[3]=3$, $\Delta x[3]= x[4]=9$.
Definition: A scalar LTI difference equation is can be written as
\begin{eqnarray}
a_m y[n+m] + a_{m-1} y[n+m-1] + \ldots + a_1 y[n+1] + a_0y[n] = f[n]\\
\end{eqnarray}
or
\begin{eqnarray}
a_m \Delta^m y[n] + a_{m-1} \Delta^{m-1}y[n] + \ldots + a_1 \Delta y[n] + a_0y[n] = f[n]
\end{eqnarray}
or
\begin{eqnarray}
\left(a_m \Delta^m + a_{m-1} \Delta^{m-1} + \ldots + a_1 \Delta + a_0 \right)y[n] = f[n] \qquad\qquad(1)
\end{eqnarray}
or, more economically
\begin{eqnarray}
\sum_{r=0}^m a_{m-r} \Delta^{m-r} y[n] = f[n]
\end{eqnarray}
where $a_m, \ldots, a_0 \in \mathbb{R}$. As discussed in the chapter for differential equations, we can always divide both sides with $a_m$ and make $a_m = 1$.
Definition: When $f[n]=0$, the scalar LTI difference equation is defined to be “unforced“.
Factorization of scalar LTI difference equations
Consider the factorized part of Eq. (1).
\begin{eqnarray}
\left(a_m \Delta^m + a_{m-1} \Delta^{m-1} + \ldots + a_1 \Delta + a_0 \right)
\end{eqnarray}
We may consider this as a polynomial in $x$
\begin{eqnarray}
\left(a_m x^m + a_{m-1}x^{m-1} + \ldots + a_1 x + a_0 \right)
\end{eqnarray}
and separate it to its roots. If the above polynomial has $k$ roots $\alpha_1, \ldots, \alpha_k$ and the root $\alpha_j$ has degree $m_j$, this factorization will take the form:
\begin{eqnarray}
\left(a_m x^m + a_{m-1}x^{m-1} + \ldots + a_1 x + a_0 \right) = (x-\alpha_1)^{m_1} \ldots (x-\alpha_{k-1})^{m_{k-1}}(x-\alpha_k)^{m_k}
\end{eqnarray}
with the restriction $m_1+\ldots+m_k=m$. This means that the LHS of the difference equation can be factored as:
\begin{eqnarray}
(\Delta-\alpha_1)^{m_1} \ldots (\Delta-\alpha_{k-1})^{m_{k-1}}(\Delta-\alpha_k)^{m_k} y =0
\end{eqnarray}
Solution of scalar unforced LTI difference equations
The solution for difference equations is almost the same with differential equations. In the interests of time, we will just state the solution as a theorem and will not give any proof. Note that the proof in the discrete case is considerably harder compared to the continuous cae.
Theorem: The solution for the difference equation
\begin{eqnarray}
(\Delta-\alpha_1)^{m_1} \ldots (\Delta-\alpha_{k-1})^{m_{k-1}}(\Delta-\alpha_k)^{m_k} y =0
\end{eqnarray}
is
\begin{eqnarray}
y[n] &=& \left( C_1^1 + C_2^1 n+ \ldots + C_{m_1}^1 n^{m_1-1}\right)\alpha_1^n+\ldots+ \left( C_1^k + C_2^k n+ \ldots + C_{m_k}^k n^{m_k-1}\right) \alpha_k^n \\
&=& \sum_{i=1}^k \left(\sum_{j=1}^{m_i} C_j^i n^{j-1} \right)\alpha_i^n
\end{eqnarray}
Example: Solve $(\Delta+3)^2 (\Delta-5)^3 y[n] =0 $. What is the degree of this equation? How many initial conditions are needed?
Solution: $y[n] = (C_1^1 + C_2^1 n ) (-3)^n + (C_1^2 + C_2^2 n + C_3^2 n^2 ) 5^n $. The equation is fifth order, hence it needs five initial conditions to resolve the coefficients $C_1^1, C_2^1, C_1^2 , C_2^2 , C_3^2 $.
Example: Solve the difference equation for the Fibonacci series.
Solution: The difference equation for the fibonacci series can be written as $y[n+2] = y[n+1]+y[n]$. This is clearly an unforced scalar LTI difference equation. Initial conditions are $y[0]=1$, $y[1]=1$. Applying the steps defined above:
\begin{eqnarray}
y[n+2] – y[n+1] – y[n] = 0 \\
\Delta^2 y[n] – \Delta y[n] – y[n] = 0\\
(\Delta^2 – \Delta – 1 )y[n] = 0\\
\left( \Delta – \frac{1-\sqrt{5}}{2} \right)\left( \Delta – \frac{1+\sqrt{5}}{2} \right)y[n] =0
\end{eqnarray}
Therefore the solution is
\begin{eqnarray}
y[n] = C_1\left( \frac{1-\sqrt{5}}{2} \right)^n + C_2\left( \frac{1+\sqrt{5}}{2} \right)^n
\end{eqnarray}
Applying the initial conditions will set up two equations for $C_1$ and $C_2$:
\begin{eqnarray}
y[0] &=& C_1 + C_2=1 \\
y[1] &=& C_1\left( \frac{1-\sqrt{5}}{2} \right) + C_2\left( \frac{1+\sqrt{5}}{2} \right) =1
\end{eqnarray}
Complex conjugate roots
Complex conjugate roots are no exception to the above theorem. If our difference equation includes $m$th order complex conjugate roots:
\begin{eqnarray}
\ldots (\Delta-a-ib)^m(\Delta-a+ib)^m\ldots y[n] = 0
\end{eqnarray}
the solution will be
\begin{eqnarray}
y[n] = \ldots+\left( C_1 + C_2 n+ \ldots + C_m n^{m-1}\right)(a-ib)^n+ \left( D_1 + D_2 n+ \ldots + D_m n^{m-1}\right) (a+ib)^n+\ldots \\
\end{eqnarray}
By using euler’s law, we can write
\begin{eqnarray}
a \pm ib = Re^{\pm i\theta}
\end{eqnarray}
where $R=\sqrt{a^2+b^2}$, $\theta=\arctan\frac{b}{a}$. After substitution, we get
\begin{eqnarray}
y[n] &=& \ldots+\left( C_1 + \ldots + C_m n^{m-1}\right)(R e^{-i\theta})^n+ \left( D_1 + \ldots + D_m n^{m-1}\right) (R e^{i\theta})^n+\ldots \\
&=& \ldots+\left( C_1 + \ldots + C_m n^{m-1}\right)R^n e^{-in\theta}+ \left( D_1 + \ldots + D_m n^{m-1}\right) R^n e^{in\theta}+\ldots
\end{eqnarray}
Here we will do exactly the same sequence of tricks as we have done in the previous chapter and arrive at
\begin{eqnarray}
y[n] = \ldots+\left( A_1 + \ldots + A_m n^{m-1}\right)R^n \cos(n\theta)+ \left( B_1 + \ldots + B_m n^{m-1}\right) R^n \sin(n\theta)+\ldots \\
\end{eqnarray}
which is a pure real solution.
Summary: Steps in solving an unforced LTI differential equation
Now we are ready to present an algoritm which will summarize all our findings listed above and which will provide a solution to any unforced LTI difference equation.
- Check if the equation is an LTI unforced equation. If not, the methods you have learned in this chapter is not useful for solution.
- If there is $a_n$, divide it to all the other coefficients to make it 1.
- Factorize the difference equation to find the roots. The roots will either be real or complex conjugate.
- If the factorization contains a term $(D-\alpha)^r$, this means we have an r th degree real root $\alpha$. Add the term $\sum_{k=1}^r C_k n^{k-1} \alpha^n$ to the solution.
- If the factorization contains the term $(D-\alpha+i\beta)^r (D-\alpha-i\beta)^r$, this means we have an r th degree complex conjugate root $\alpha \pm i\beta$. Find the polar representation of the complex number $\alpha+i\beta$, ie, $\alpha+i\beta=Re^{i\theta}$. Add the term $\sum_{k=1}^r A_k n^{k-1} R^n \cos[\theta n] + \sum_{k=1}^n B_k n^{k-1} R^n \sin[\theta n]$ to the solution.
- Use initial conditions to find the constants.
Stability of Solutions