Linear Constant Coefficient Discrete Difference Equations

Introduction

This is a step-by-step guide for finding the impulse response for Linear Constant Coefficient Discrete Difference Equations (LCCDDE). Once you find the impulse response, you can find the response to any other input signal.

Very Basic First Difference

Let's start with the simplest case:

\( y[n]+a_1\,y[n-1]=x[n] \)

To find the impulse response $$h[n]$$ we want to solve:

\( h[n]+a_1\,h[n-1]=\delta[n] \)

where $$\delta[n]$$ is the discrete impulse, which is 1 when $$n=0$$ and 0 everywhere else. Assuming $$y[n]=0$$ for all $$n<0$$, we could make a table to see how the impulse response progresses:

\( \begin{array}{cccc} n & h[n-1] & \delta[n] & h[n]=\delta[n]-a_1\,h[n-1]\\ -1 & 0 & 0 & 0-(a_1)(0)=0 \\ 0 & 0 & 1 & 1-(a_1)(0)=1 \\ 1 & 1 & 0 & 0-(a_1)(1) = -a_1 \\ 2 & -a_1 & 0 & 0-(a_1)(-a_1)=(-a_1)^2\\ \end{array} \)

As the pattern continues, it looks like we have:

\( h[n]=\begin{cases} n\lt 0, & 0 \\n\geq 0 & \left(a_1\right)^n\end{cases} \)

or in other words:

\( h[n]=\left(-a_1\right)^n\,u[n] \)

Slightly Less Basic First Difference

Now let's make the left side a little less basic by including a non-unity coefficient $$a_0$$ on $$y[n]$$:

\( a_0y[n]+a_1\,y[n-1]=x[n] \)

We can start by normalizing the equation by $$a_0$$:

\( y[n]+\frac{a_1}{a_0}\,y[n-1]=\frac{1}{a_0}x[n] \)

To find the impulse response $$h[n]$$ we want to solve:

\( h[n]+\frac{a_1}{a_0}\,h[n-1]=\frac{1}{a_0}\delta[n] \)

Assuming $$y[n]=0$$ for all $$n<0$$, we could again make a table to see how the impulse response progresses:

\( \begin{array}{cccc} n & h[n-1] & \delta[n] & h[n]=\frac{\delta[n]-a_1\,h[n-1]}{a_0}\\ -1 & 0 & 0 & 0 \\ 0 & 0 & 1 & \frac{1}{a_0} \\ 1 & \frac{1}{a_0} & 0 & \frac{0-a_1\frac{1}{a_0}}{a_0} = \frac{1}{a_0}\left(-\frac{a_1}{a_0}\right) \\ 2 & \frac{1}{a_0}\left(-\frac{a_1}{a_0}\right) & 0 & \frac{0-a_1\frac{1}{a_0}\left(-\frac{a_1}{a_0}\right)}{a_0} = \frac{1}{a_0}\left(-\frac{a_1}{a_0}\right)^2 \\ \end{array} \)

As the pattern continues, it looks like we have:

\( h[n]=\begin{cases} n\lt 0, & 0 \\n\geq 0 & \frac{1}{a_0}\left(-\frac{a_1}{a_0}\right)^n\end{cases} \)

or in other words:

\( h[n]=\frac{1}{a_0}\left(-\frac{a_1}{a_0}\right)^n\,u[n] \)

General Homogeneous Solution

For LCCDDE problems, we can use a general homogeneous solution of $$y_h[n]=C\,\gamma^n$$, where $$\gamma$$ is some constant based on the coefficients. The impulse response for the basic first difference will generally be the same as the homogeneous response except for the $$h[0]=1$$ time. We can treat that more like an initial condition than a forcing function as follows:

\( a_0\,y[n]+a_1\,y[n-1]=b_0x[n] \)

or, normalizing based on $$a_0$$:

\( y[n]+\frac{a_1}{a_0}\,y[n-1]=\frac{b_0}{a_0}x[n] \)

To find the impulse response $$h[n]$$ we want to solve:

\( \begin{align*} h[n]+\frac{a_1}{a_0}\,h[n-1] &= 0, n\gt 0\\ h[n] &= 0, n\lt 0\\ h[n] &= \frac{b_0}{a_0}, n=0 \end{align*} \)

Substituting in $$h[n]=y_h[n]=C\,\gamma^n$$ for the $$n>0$$ equation gives:

\( \begin{align*} C\,\gamma^n+\frac{a_1}{a_0}\,C\,\gamma^{n-1} &= 0\\ C\,\gamma^{n-1}\,\left(\gamma+\frac{a_1}{a_0}\right) &=0 \end{align*} \)

For that second equation to work, we either need $$C=0$$ (trivial case), $$\gamma^{n-1}=0$$ impossible for all $$n$$ unless $$\gamma=0$$, or $$\gamma=-\frac{a_1}{a_0}$$.

To figure out $$C$$, we can look at the $$n=0$$ case: $$y_h[0] = C = \frac{b_0}{a_0}$$. Since $$h[n]=0$$ for $$n<0$$ we can put the homogeneous solution together with a step function to get:

\( h[n]=\frac{b_0}{a_0}\left(-\frac{a_1}{a_0}\right)^n\,u[n] \)

Characteristic Polynomial

From this point forward, for first- and higher-shift differences we can use a technique that is very similar to using $$y_h(t)=C\,e^{st}$$ for differential equations; instead of getting a characteristic polynomial by replacing $$\frac{d^ky(t)}{dt^k}$$ with $$s^k$$, we will replace $$y[n-k]$$ with $$\gamma^{N-k}$$ where $$N$$ is the largest value of $$k$$ (the largest shift of $$y$$). Instead of solving for $$s$$ as an exponent, we will solve for $$\gamma$$ as a geometric constant. For example, if we have:

\( y[n]+6y[n-1]+8y[n-2]=x[n] \)

the characteristic polynomial would be:

\( \gamma^2+6\gamma+8=0 \)

which would tell us that $$\gamma=-2,-4$$.

Example 1: Fits Basic Case

Imagine you want to solve for the impulse response of

\( 3\,y[n]-2\,y[n-1]=x[n] \)

• Normalize the equation based on the coefficient of $$y[n]$$:\( y[n]-\frac{2}{3}\,y[n-1]=\frac{1}{3}x[n] \)
• Find $$\gamma$$ by replacing $$x[n]$$ with 0 and all $$y[n-k]$$ with $$\gamma^{1-k}$$ (the 1 comes from the fact that the largest shift in $$y$$ is 1): \(\begin{align*}\gamma-\frac{2}{3}&=0\\ \gamma&=\frac{2}{3}\end{align*}\)
• Find $$C$$ by putting $$C\,\gamma^n\,u[n]$$ in for $$n=0$$ case: \(\begin{align*}C\,\left(\frac{2}{3}\right)^0\,u[0]-\frac{2}{3}\,C\,\left(\frac{2}{3}\right)^{-1}\,u[-1]&=\frac{1}{3}\\ C+0&=\frac{1}{3}\\ C&=\frac{1}{3}\end{align*}\)
• $$h[n] =\frac{1}{3}\left(\frac{2}{3}\right)^n\,u[n]$$

Example 2: Fits Basic Case After Scaling and Shifting

Imagine you want to solve for the impulse response of

\( 6\,y[n+1]=2\,x[n+1]+4\,y[n] \)

• Adjust the equation so that all the $$y$$ are on the left, all the $$x$$ are on the right, all the shifts are $$n-k$$ where $$k\geq 0$$ (the system is LTI so we can shift everything by the same amount), and $$y[n]$$ has a coefficient of 1:

\(\begin{align*} 6\,y[n+1]&=2\,x[n+1]+4\,y[n]\\ 6\,y[n+1]-4\,y[n]&=2\,x[n+1]\\ y[n]-\frac{2}{3}\,y[n-1]&=\frac{1}{3}x[n] \end{align*}\)

• At this point, this perfectly fits the basic case above.
• As above, $$h[n] =\frac{1}{3}\left(\frac{2}{3}\right)^n\,u[n]$$

More Complicated Forcing Function

All the cases above could be re-written to have a single $$x[n]$$ on the right, and at that point, all the $$y[n-k]$$ had $$k\geq 0$$ meaning, among other things, the system was causal. If the right-hand-side ends up more complicated than $$x[n]$$, it turns out that you can still solve the problem by re-writing things such that the left side contains a new variable $$z[n-k]$$ with all $$k\geq 0$$, solving as if the right side at that point were merely $$x[n]$$, and then relating $$z[n]$$ to the more complicated right side using scaling and shifting.

Reminder: Scaled Convolutions with Impulses

Recall that $$f[n]\ast a\,\delta[n-k]=a\,f[n-k]$$. That means that something like $$\frac{3}{2}\,x[n]-\frac{7}{2}\,x[n-2]$$ could also be written as $$x[n]\ast\left(\frac{3}{2}\,\delta[n]-\frac{7}{2}\,\delta[n-2]\right)$$

Back to Basics

Let's start with:

\( 2\,y[n]-5\,y[n-1]=3\,x[n]-7\,x[n-2] \)

All the $$y$$ shifts are 0 or more to the right so that part is all good. The issue now is the complicated right side - even after we divide by 3 to get the coefficient of $$y[n]$$ to be 1, there will be more than just $$x[n]$$ on the right. So let's start by normalizing the equation based on $$a_0$$:

\( y[n]-\frac{5}{2}\,y[n-1]=\frac{3}{2}x[n]-\frac{7}{2}\,x[n-2] \)

Now I am going to solve a slightly different equation - one where the only variable on the right is $$x[n]$$. I am going to replace the variables on the left with a new variable, $$z[n]$$:

\( z[n]-\frac{5}{2}\,z[n-1]=x[n] \)

Note that if I convolve both sides of this equation with $$\frac{3}{2}\delta[n]-\frac{7}{2}\,\delta[n-2]$$ I get:

\( \begin{align*} \left(z[n]-\frac{5}{2}\,z[n-1]\right)*\left(\frac{3}{2}\delta[n]-\frac{7}{2}\,\delta[n-2]\right)&=x[n]*\left(\frac{3}{2}\delta[n]-\frac{7}{2}\,\delta[n-2]\right) \end{align*} \)

If I distribute the convolution on the right I get:

\( \begin{align*} \left(z[n]-\frac{5}{2}\,z[n-1]\right)*\left(\frac{3}{2}\delta[n]-\frac{7}{2}\,\delta[n-2]\right)&=\frac{3}{2}x[n]-\frac{7}{2}\,x[n-2] \end{align*} \)

which is the original right side of my equation; I can then replace it with the original left side of my equation:

\( \begin{align*} \left(z[n]-\frac{5}{2}\,z[n-1]\right)*\left(\frac{3}{2}\delta[n]-\frac{7}{2}\,\delta[n-2]\right)&=y[n]-\frac{5}{2}\,y[n-1] \end{align*} \)

Now I can actually replace scaled, shifted signals with an unshifted signal convolved with scaled, shifted deltas:

\( \begin{align*} z[n]*\left(\delta[n]-\frac{5}{2}\,\delta[n-1]\right)*\left(\frac{3}{2}\delta[n]-\frac{7}{2}\,\delta[n-2]\right)&= y[n]*\left(\delta[n]-\frac{5}{2}\,\delta[n-1]\right) \end{align*} \)

I will rearrange the order of the convolution on the left side a bit to get:

\( \begin{align*} z[n]*\left(\frac{3}{2}\delta[n]-\frac{7}{2}\,\delta[n-2]\right)*\left(\delta[n]-\frac{5}{2}\,\delta[n-1]\right)&= y[n]*\left(\delta[n]-\frac{5}{2}\,\delta[n-1]\right) \end{align*} \)

For these equations to be equal, $$y[n]=z[n]*\left(\frac{3}{2}\delta[n]-\frac{7}{2}\,\delta[n-2]\right)=\frac{3}{2}\,z[n]-\frac{7}{2}\,z[n-2]$$. This means if I can solve for the impulse response $$h_z[n]$$ for the $$z[n]$$ equation, I can find the impulse reponse $$h_y[n]=\frac{3}{2}\,h_z[n]-\frac{7}{2}\,h_z[n-1]$$. We know the general solution for a first-difference problem already, so can quickly find:

\( h_z[n]=\left(\frac{5}{2}\right)^{n}\,u[n] \)

and from that we can get $$h_y[n]$$:

\( \begin{align*} h_y[n]&=\frac{3}{2}h_z[n]-\frac{7}{2}\,h_z[n-1]\\ ~&=\frac{3}{2}\left(\frac{5}{2}\right)^{n}\,u[n] - \frac{7}{2}\left(\frac{5}{2}\right)^{n-2}\,u[n-2] \end{align*} \)

Another First-Difference Example

Find the impulse response $$h_y[n]$$ if:

\( \begin{align*} y[n+1]&=\frac{1}{2}\,y[n]+3\,x[n] \end{align*} \)

• First, get all the $$y$$ on one side, move shifts to make them at or to the right of 0, and divide by $$a_0$$ as needed: \( \begin{align*} y[n]-\frac{1}{2}\,y[n-1]&=3\,x[n-1] \end{align*} \)
• Solve for $$h_z[n]$$ assuming just $$x[n]$$ on the right:\( \begin{align*} z[n]-\frac{1}{2}\,z[n-1]&=x[n]\\ h_z[n]=\left(\frac{1}{2}\right)^n\,u[n] \end{align*} \)
• Solve for $$h_y[n]$$, in this case noting that $$h_y[n]=3h_z[n-1]$$\( \begin{align*} h_y[n]=3\left(\frac{1}{2}\right)^{n-1}\,u[n-1] \end{align*} \)

Big Picture

For a difference equation of the form:

\( \begin{align*} \sum_{k=0}^{N}a_k\,y[n-k]&=\sum_{l=0}^{M}b_k\,x[n-l] \end{align*} \)

you can find the geometric constants $$\gamma$$ by solving:

\( \begin{align*} \sum_{k=0}^{N}a_k\,\gamma^{N-k}&=0 \end{align*} \)

You can solve a simplified impulse response $$h_z[n]$$ using:

\( \begin{align*} \sum_{k=0}^{N}a_k\,h_z[n-k]&=\delta[n] \end{align*} \)

and then you can find the actual impulse response $$h_y[n]$$ with:

\( \begin{align*} h_y[n]&=\sum_{l=0}^{M}b_k\,h_z[n-l] \end{align*} \)

Second Difference and More

If the left side of the equations has more terms than just $$y[n]+a_1\,y[n-1]$$, the nature of $$\gamma$$ expands from a simple real constant $$\gamma=-a_1$$ to all the possible solutions for an $$N$$th order polynomial, where $$N$$ is again the largest shift on the left side of the equation. Here are some possibilities for $$N$$th order polynomials (assuming real-valued coefficients):

• For a 1st order polynomial, $$\gamma$$ will be a single real value.
• For a 2nd order polynomial, $$\gamma$$ could be:
  • two different real values,
  • a real value repeated twice, or
  • a complex conjugate pair (whose real part may or may not be 0)
• For a 3rd order polynomial, $$\gamma$$ could be a real value and then any of the possibilities for 2nd order polynomials, so:
  • three different real values,
  • one real value and a different real value repeated twice,
  • a real value repeated three times, or
  • a real value and a complex conjugate pair (whose real part may or may not be 0)
• For a 4th order polynomial, $$\gamma$$ could be any of the possibilities for a 2nd order polynomial combined with any of the possibilities for a 2nd order polynomial, so:
  • four different real values,
  • two different real values and a third real value repeated twice,
  • a real value repeated four times,
  • two different real values and a complex conjugate pair (whose real part may or may not be 0),
  • a real value repeated twice and a complex conjugate pair (whose real part may or may not be 0),
  • two different complex conjugate pairs (whose real parts may or may not be 0), or
  • a repeated set of complex conjugate pairs (whose real parts may or may not be 0)
  • a real value repeated twice, or
  • a complex conjugate pair (whose real part may or may not be 0)
• After this, the pattern continues with some combination of (possibly repeated) real values and (possibly repeated) complex conjugate pairs

Each type of $$\gamma$$ has a particular form for the homogeneous response:

• Individual real roots $$\gamma$$ have $$C\gamma^nu[n]$$
• Real roots $$\gamma$$ repeated $$p$$ times have a $$(p-1)$$th order polynomial along with the $$\gamma^n$$ term, meaning $$\sum_{k=0}^{p-1}C_kn^k\gamma^nu[n]$$
• Complex conjugate pairs $$\gamma=|\gamma|\pm(\angle\gamma)$$ create geometric sinusoids $$C|\gamma|^n\cos(n\angle\gamma+\phi)u[n]$$ or $$|\gamma|^n\left(C_c\cos(n\angle\gamma)+C_s\sin(n\angle\gamma)\right)u[n]$$
• Complex conjugate pairs $$\gamma=|\gamma|\pm(\angle\gamma)$$ repeated $$p$$ times have a $$(p-1)$$th order polynomial along with the sinusoids meaning $$\sum_{k=0}^{p-1}C_kn^k|\gamma|^n\cos(n\angle\gamma+\phi_k)u[n]$$ or $$\sum_{k=0}^{p-1}n^k|\gamma|^n\left(C_{c,k}\cos(n\angle\gamma)+C_{s,k}\sin(n\angle\gamma)\right)u[n]$$

Second-Difference Example: Fibonacci Sequence

The Fibonacci Sequence can be calculated using the impulse response of the equation:

\( \begin{align*} y[n]&=y[n-1]+y[n-2]+x[n] \end{align*} \)

so, find the impulse response $$h_y[n]$$ for this equation.

• First, get all the $$y$$ on one side, move shifts to make them at or to the right of 0, and divide by $$a_0$$ as needed: \( \begin{align*} y[n]-y[n-1]-y[n-2]&=x[n] \end{align*} \)
• Since $$x[n]$$ is unscaled and unshifted on the right, we do not need to do the intermediate $$z[n]$$ step.
• Replace $$y[n-k]$$ with $$\gamma^{N-k}$$ and replace $$x[n]$$ with 0 to find geometric constants:\( \begin{align*} \gamma^2-\gamma-1&=0\\ \gamma&=\frac{1\pm\sqrt{1+4}}{2}=\frac{1\pm\sqrt{5}}{2} \end{align*} \)
• This means that the general form of the impulse response is:\( \begin{align*} h_y[n]=C_1\left(\frac{1+\sqrt{5}}{2}\right)^nu[n]+C_2\left(\frac{1-\sqrt{5}}{2}\right)^nu[n] \end{align*} \)
• Get coefficients by specifically looking at $$n=0$$ and $$n=1$$\( \begin{align*} n=0:&~\\ h_y[0]-h_y[-1]-h_y[-2]&=\delta[0]\\ \left(C_1+C_2\right)-\left(0+0\right)-\left(0+0\right)&=1\\ C_1+C_2&=1\\ ~&~\\ n=1:&~\\ h_y[1]-h_y[0]-h_y[-1]&=\delta[1]\\ \left(\left(\frac{1+\sqrt{5}}{2}\right)C_1+\left(\frac{1-\sqrt{5}}{2}\right)C_2\right)-\left(C_1+C_2\right)-\left(0+0\right)&=0\\ (-1+\sqrt{5})C_1+(-1-\sqrt{5})C_2&=0 \end{align*} \)Solving these two equations gives:\( \begin{align*} C_1&=\frac{5+\sqrt{5}}{10}\\ C_2&=\frac{5-\sqrt{5}}{10}\\ h_y[n]&=\left(\frac{5+\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^nu[n]+ \left(\frac{5-\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^nu[n] \end{align*} \)

Second Difference: Complex $$\gamma$$

Find the impulse response for:

\( y[n]-y[n-1]+1.69y[n-2]=x[n]. \)

• First, get all the $$y$$ on one side, move shifts to make them at or to the right of 0, and divide by $$a_0$$ as needed - already there!
• Since $$x[n]$$ is unscaled and unshifted on the right, we do not need to do the intermediate z[n] step.
• Replace $$y[n−k]$$ with $$\gamma^{N−k}$$ and replace $$x[n]$$ with 0 to find geometric constants:\( \begin{align*} \gamma^2-\gamma+1.69&=0\\ \gamma&=\frac{1\pm\sqrt{1-6.76}}{2}=\frac{1\pm j2.4}{2}=0.5+j1.2 \end{align*}\)
• The magnitude of the root is $$|\gamma|=1.3$$ and the angle (picking the + version of the imaginary part) is $$\angle\gamma=\mbox{arctan(1.2/0.5)}=1.176$$. This means the form of the impulse response would be:\( \begin{align*} h_y[n]&= 1.3^nC\cos(1.176n + \phi)u[n]\mbox{ or}\\~&=1.3^n\left(C_1\cos(1.176n)+C_2\sin(1.176n)\right)u[n] \end{align*}\)
• (Aside - for this example, $$\cos(\gamma)=\frac{5}{13}$$ and $$\sin(\gamma)=\frac{12}{13}$$ - these numbers were picked to make things...pretty.
• Get coefficients by specifically looking at $$n=0$$ and $$n=1$$ (using cos and sin version)\( \begin{align*} n=0&:~\\ h_y[0]-h_y[-1]+1.69h_y[-2]&=\delta[0]\\ C_1-0+0&=1\\ C_1&=1\\ ~&~\\ n=1:&~\\ h_y[1]-h_y[0]+1.69h_y[-1]&=\delta[1]\\ 1.3\left(C_1\cos(1.176)+C_2\sin(1.176)\right)-C_1+0&=0\\ C_2&=\frac{C_1-1.3\cos(1.176)}{1.3\sin(1.176)}=\frac{1-1.3\frac{5}{13}}{1.3\frac{12}{13}}=\frac{10-5}{12}=\frac{5}{12}\end{align*}\) meaning\( \begin{align*} h_y[n]&=1.3^n\left(\cos(1.176n)+\frac{5}{12}\sin(1.176n)\right)u[n]\end{align*}\)