# Finding Annihilators for Recurrence Relations

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.

• Welcome to Math Stack Exchange. Replace $i$ with $i+3$ – J. W. Tanner Apr 1 '19 at 1:52
• As for converting the recurrence, he just substituted $i+3$ in place of $i$. Your second question confuses me. Do you understand what the $E$ operator does? $E^2 F_i-E F_i-F_i= F_{i+2}-F_{i+1}-F_i$ by definition of the operator. That this is identically $0$ is just the definition of the Fibonacci numbers. – saulspatz Apr 1 '19 at 1:55
• I'm clear as to what the $E$ operator does, I'm just confused as to how it is identical to 0. – Grayson Apr 1 '19 at 2:00

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.$$