I'm familiar with the general methodology for checking if a system is linear:

  1. Define output $y_1[n]$ for input $x_1[n]$, define output $y_2[n]$ for input $x_2[n]$
  2. Define $x_3[n] = ax_1[n] + bx_2[n]$
  3. Compute output $y_3[n]$ for input $x_3[n]$ and verify whether $y_3[n]=ay_1[n]+by_2[n]$. If it is, the system is linear.

However, I am having trouble applying this method to systems that are recursive. Some recursive systems can be converted to an iterative form by inspection. For example: $y[n] - y[n-1] = x[n] \implies y[n] = x[n] + y[n-1] \implies y[n] = \sum\limits_{k=-\infty}^n x[k]$

For others, I am having more trouble, such as $y[n]+y[n+1]=x[n]$

First, I do a change of variables:

$k = n+1 \implies y[k]+y[k-1]=x[k-1]$

Following the general approach:

$y_1[k]+y_1[k-1] = x_1[k-1]$

$y_2[k]+y_2[k-1] = x_2[k-1]$

$x_3[k] = ax_1[k]+bx_2[k]$

$y_3[k]+y_3[k-1] = x_3[k-1] = ax_1[k-1]+bx_2[k-1]$

Here is where I got stuck. I was anticipating that the system should be linear, but due to the recursive term, I do not see how the approach I took could yield $y_3[n] = ay_1[n]+by_2[n]$.

Does anyone know where I made a mistake, or if there is a different approach I should be taking? (For instance, is there a general process for going from a recursive expression to an iterative one that I could use?) I'm a student using Oppenheim and Schafer for reference.

  • $\begingroup$ $$\begin{align}y[k]&=x[k-1]-y[k-1]\\&=x[k-1]-\left[x[k-2]-y[k-2]\right]\\&=x[k-1]-x[k-2]+y[k-2]\\&=x[k-1]-x[k-2]+\left[x[k-3]-y[k-3]\right]\end{align}$$ etc? $\endgroup$ Sep 15, 2014 at 1:00

2 Answers 2


You made no mistake. Following the hint in Dilip Sarwate's comment, you will be able to show the following input-output relation of the system:


Using this relation, showing linearity will be much easier.

Furthermore, note that any system described by a linear difference equation with constant coefficients is linear and time-invariant (if the initial conditions are zero!). And your system obviously belongs to this class.

  • $\begingroup$ Thank you! That makes a lot of sense. I recognized it as a linear difference equation with constant coefficients, but was looking for a more rigorous way to show it, and for some reason did not think about substituting in for $y[k-1]$ etc. $\endgroup$
    – jlj-ee
    Sep 15, 2014 at 16:53

you can apply the linearity and time-invarancy tests to the original recursive difference equation.

in this case it's:

$$ y[n] - y[n-1] = x[n] $$

which is really

$$ y[n] = x[n] + y[n-1] $$

now, as a premise you say that $y_1[n]$ is the output when the input is $x_1[n]$ and that $y_2[n]$ is the output when the input is $x_2[n]$, and that $x_1[n]$ and $x_2[n]$ are totally arbitrary. you don't get to choose a convenient $x_1[n]$ and $x_2[n]$, the Devil hands you a pair $x_1[n]$ and $x_2[n]$ (which have some resulting outputs $y_1[n]$ and $y_2[n]$) and you have to deal with whatever the Devil gives you.

now, assuming $x_1[n]$ and $x_2[n]$ (along with their respective $y_1[n]$ and $y_2[n]$) satisfy the above difference equation. and let's label $y_3[n]$ as the result from an input that is the sum $x_1[n] + x_2[n]$, does $y_3[n]$ satisfy the above difference equation?

$$ \begin{align} y_3[n] & = (x_1[n] + x_2[n]) + y_3[n-1] \\ y_1[n] + y_2[n] & = (x_1[n] + x_2[n]) + (y_1[n-1] + y_2[n-1]) \\ \end{align} $$

is that mathematical statement true or not? if it is for any possible set of inputs $x_1[n]$ and $x_2[n]$, the system is linear. if not, it's not.

now, for time-invariancy, it's the same thing but a different criterion to test. again you assume the premise that when $x[n]$ is the input, $y[n]$ is the output. then ask if $x[n-N]$ is the input, is $y[n-N]$ the output? it is if it satisfies the defining difference equation. so if $ y[n] = x[n] + y[n-1] $ is true, is or is not this also true:

$$ y[n-N] = x[n-N] + y[n-N-1] \quad \forall n, N \in \mathbb{Z} $$

?? if it is true, it's time-invariant, if not, it's not.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.