Checking linearity/time-invariance etc. for recursive system

Question

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.

Answer 1

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:

$$y[n]=x[n-1]-x[n-2]+x[n-3]-+\ldots=\sum_{k=-\infty}^{n-1}(-1)^{n-k-1}x[k]\tag{1}$$

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.

Answer 2

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.