Recently I've taken an interest in solving recurrence relations using annihilators but I'm still unclear as to how to find such annihilators.
My professor provides the following linear recurrence in his lecture notes:
$r_i$ = $7r_{i-1}$ - $16r_{i-2}$ + $12r_{i-3}$ with initial conditions $r_0$ = 1, $r_1$ = 5, and $r_2$ = 17
for some reason, the recurrence is converted to: $r_{i+3}$ - $7r_{i+2}$ + $16r_{i+1}$ - $12r_i$ = 0 and the annihilator found from there.
Could someone please provide some insight as to how the recurrence was converted to this form?
Also there's the matter of actually applying annihilators to recurrence relations themselves. For example, I'm still stumped as to how the annihilator $E^2$ - $E$ - $1$ when applied to the fibonacci recurrence $F_i$ = $F_{i-1} + F_{i-2}$ actually yields a sequence of all o's.
My professor writes: $E^2(F_i)$ - $E(F_i)$ - $F_i$ = $(F_{i+2} - F_{i+1} - F_i)$ = $(0)$ but the algebra behind said statement remains unclear.
Any clarification would be greatly appreciated.
For the Fibonacci numbers the recurrence identity is $F_{n+2} = F_{n+1} + F_{n}$. In the example the operator $E$ is such that $E f_{n} = f_{n+1}$. With this then \begin{align} F_{n+2} &= F_{n+1} + F{n} \\ E^2 F_{n} &= E F_{n} + F_{n} \\ (E^2 - E -1) \, F_{n} &= 0. \end{align} If $E^2 - E -1$ is considered as a polynomial then it can be found that: $x^2 - x - 1 = 0$ with roots $ x = \{ \alpha, \beta \}$ or $$(E - \alpha)(E - \beta) F_{n} = 0.$$
In terms of the four term recurrence relation then: \begin{align} r_{n+3} - 7 r_{n+2} + 16 r_{n+1} - 12 r_{n} &= 0 \\ E^3 r_{n} - 7 E^2 r_{n} + 16 E r_{n} - 12 r_{n} &= 0 \\ (E^3 - 7 E^2 + 16 E - 12) \, r_{n} &= 0 \\ (E - 3)(E - 2)^2 \, r_{n} &= 0. \end{align} This demonstrates that $r_{n}$ has the form $r_{n} = 2^n \, (a n + b) + c \, 3^n$. Considering the initial conditions, $r_{0} = 1, r_{1} = 5, r_{2} = 17$, then $$r_{n} = 2^n \, n + 3^n.$$