Today we will learn about difference operator and use it to prove a fundamental theorem for linear recurrence equations.
A fundamental theorem for linear recurrence equations. Suppose that the characteristic equation can be factored as $$f(x) = a_k x^k + a_{k-1} x^{k-1} + \dots + a_0 = (x - z)^j (b_s x^s + b_{s-1} x^{s-1} + \dots + b_0)$$ and $$f_n = p(n)~z^n,$$ where $p(n)$ is a polynomial of degree less than $j$. Then the sequence $f_n$ satisfies the recurrence equation
$$a_k f_{n} + a_{k-1} f_{n-1} + \dots + a_1 f_{n-k+1} + a_0 f_{n-k} = 0.$$
