How to prove if a relation is linear and invariant by translation

Question

The input is the sequence $U_n$ and the output is the sequence $V_n$, and for all $n$ in $\mathbb{Z}$, $V_n=U_n-U_{n-1} +3U_{n+1}$ .

How to prove if the relation between the input and the output is linear and if it is invariant by translation.

Answer 1

I'll use capital letters to indicate sequences, lower indices to indicate entries in a sequence, and lower case letters to indicate scalars. I'll assume the sequences you are interested in are real valued. The space of all such sequences can be referred to as $\mathbb R^{|\mathbb Z|}$. This is vector space under the right operations, which allows us to define a notion of linearity.

We can define addition as an operation that acts independently on each element.

$$(A+B)_n=A_n+B_n$$

Scalar multiplication can be defined similarly.

$$(cA)_n=c(A_n)$$

Now, let $f:\mathbb R^{|\mathbb Z|}\to\mathbb R^{|\mathbb Z|}$ be a function such as the one you provided. We say $f$ is linear iff it preserves both addition and scalar multiplication. That is, for any $A,B\in\mathbb R^{|\mathbb Z|}$ and any $c\in\mathbb R$, the following hold:

$$f(A+B)=f(A)+f(B)$$

$$f(cA)=cf(A)$$

To prove these equalities for a function such as yours, we need to show that they hold at every index. Here's an example for proving the first equality.

$$f(A+B)_n=(A+B)_n-(A+B)_{n-1}+3(A+B)_{n+1}$$ $$=A_n+B_n-A_{n-1}-B_{n-1}+3A_{n+1}+3B_{n+1}$$ $$=(A_n-A_{n-1}+3A_{n-1})+(B_n-B_{n-1}+3B{n+1})$$ $$=f(A)_n+f(B)_n$$ $$=(f(A)+f(B))_n$$ We see that $f(A+B)_n=(f(A)+f(B))_n$ holds for any index $n\in\mathbb Z$, therefore $f(A+B)=f(A)+f(B)$.

Hopefully, proving the 2nd equality should be straightforward.

We can also define translations (or shifts) as a set of functions, which I'll call $T^k:\mathbb R^{|\mathbb Z|}\to\mathbb R^{|\mathbb Z|},\ k\in\mathbb Z$, such that:

$$T^k(A)_n=A_{n+k}$$

By plugging this into the equations above, we see that translations are linear functions. Also, we can refer to a function as translation invariant if it commutes with translations. In other words, $f$ is translation invariant iff for any $A\in\mathbb R^{|\mathbb Z|}$ and any $k\in \mathbb Z$, the following holds.

$$f(T^k(A))=T^k(f(A))$$

Again, this can be verified by showing the equality holds at every index $n$.