Proof of linearity

I have this system:

$$y[n] − 4y[n − 1] + 4y[n − 2] = 20x[n] + 10x[n − 1]$$

I have no idea how to prove if the system is linear because it depends on future outputs.

• hmm, future or past outputs? – Olli Niemitalo May 20 '18 at 8:31
• Linear or causal? – A_A May 20 '18 at 9:18
• Nothing can be said about the causality of this system, but that doesn't matter since it has no bearing on the system's linearity. – Matt L. May 20 '18 at 9:33
• Could you try to explain what linearly should be? Dependance on past/future samples has little to do with that – Laurent Duval May 20 '18 at 9:50
• You can easily say that is linear because there are only sums and products by constants. You have not to consider past output (not future in your example) you have to consider that each x[n-i] and y[n-i] is a different variable changing i – Andrea May 20 '18 at 11:26

The question is, rephrased: if $x_1$ and $x_2$ are inputs, with $y_1$ and $y_2$ their respective outputs, is $\lambda y_1 +\mu y_2$ the output of weighted sum input $\lambda x_1 +\mu x_2$? So, on the one hand, you have:

$$y_1[n]−4y_1[n−1]+4y_1[n−2]=20x_1[n]+10x_1[n−1]$$ and $$y_2[n]−4y_2[n−1]+4y_2[n−2]=20x_2[n]+10x_2[n−1]$$ whose weighted sum is obviously: $$(\lambda y_1 +\mu y_2)[n]−4(\lambda y_1 +\mu y_2)[n−1]+(\lambda y_1 +\mu y_2)[n−2]=20(\lambda x_1 +\mu x_2)[n]+10(\lambda x_1 +\mu x_2)[n−1]$$ On the other hand, if you replace $x[n-k]$ in the original equation by $\lambda x_1[n-k] +\mu x_2[n-k]$, you should find the exactly same result, proving linearity. Indeed, $10x[n−1]$ becomes $10 \lambda x_1[n−1]+10 \lambda x_2[n−1]$, $20x[n]$ becomes $20 \lambda x_1[n]+20 \lambda x_2[n]$, and the rest follows quite nicely.

By definition, a system is linear if and only if

$$\mathcal T\big\{a_1x_1[n] + a_2x_2[n]\big\}=a_1\mathcal T\big\{x_1[n]\big\} + a_2\mathcal T\big\{x_2[n]\big\}$$ With $y_i[n] = \mathcal T\big\{x_i[n]\big\},\ \text{and}\ i = 1, 2.$ Or put in another way: $$\mathcal T\big\{a_1x_1[n] + a_2x_2[n]\big\}\iff a_1y_1[n]+ a_2y_2[n]\tag{1}$$

I.e. The superposition principle has to hold. Multiplying by $a_1$, then $a_2$ on both sides we get equation $(2)$ and $(3)$ respectively:

$$a_1\big(y_1[n] − 4y_1[n − 1] + 4y_1[n − 2]\big) = a_1\big(20x_1[n] + 10x_1[n − 1]\big)$$ $$\implies a_1y_1[n]-4\big(a_1y_1[n-1]\big)+4\big(a_1y_1[n-2]\big)=20\big(a_1x_1[n]\big) + 10\big(a_1x_1[n − 1]\big)\tag{2}$$

Similarly, $$a_2y_2[n]-4\big(a_2y_2[n-1]\big)+4\big(a_2y_2[n-2]\big)=20\big(a_2x_2[n]\big) + 10\big(a_2x_2[n − 1]\big)\tag{3}$$ Summing equation $(2)$ and $(3)$ you get: $$\bigg(a_1y_1[n] + a_2y_2[n]\bigg)-4\bigg(a_1y_1[n-1]+a_2y_2[n-1]\bigg)+4\bigg(a_1y_1[n-2]+a_2y_2[n-2]\bigg)=20\bigg(a_1x_1[n]+a_2x_2[n]\bigg) + 10\bigg(a_1x_1[n-1]+a_2x_2[n − 1]\bigg)\tag{4}$$ Linearity, satisfying the superposition principle in equation (1), is clearly seen equation $(4)$.

This is a $5$ variables equation, each variable is an $x[n-i]$ or $y[n-i]$ and you have not to consider the time to prove linearity. Take the linear equation definition:

$\sum_{k=1}^N c_k \cdot a_k = 0$

where $c$ are constants and $a$ are variables. If you move the right equation part to the left by sub the right part to left and right you will make an equation like linear equation definition: only sums of variable and products by constants equal to $0$. So this is a linear equation and the associate system is linear because a discrete time invariant SISO system is linear if:

$y[n]=\sum_i b[i]\cdot x[n-i] + \sum_{ j \neq 0 } a[j] \cdot y[n-j]$

where $b,a$ are constants.

If the equation is linear you can ever write the system in this form

PS: $\textrm{var}[n-i]$ is not a future sample but a past sample if $i$ is positive