Solve the following recursive relation by using generating functions

Question

$a_n - 9a_{n-1} + 26a_{n-2} - 24a_{n-3} = 0, n \ge 3, a_0 = 0, a_1 = 1,a_2 = 10$

I have tried solving it by the normal way, but I have no idea how to solve it by generating functions. Please give me a detailed answer.

Answer 1

Check Wilf's "generatingfunctionology". Write the recurrence without subtraction in indices: $$ a_{n + 3} - 9 a_{n + 2} + 26 a_{n + 1} - 24 a_n = 0 $$ Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply by $z^n$, sum over $n \ge 0$ and recognize sums like: $$ \sum_{n \ge 0} a_{n + m} z^n = \frac{A(z) - a_0 - a_1 z - \ldots - a_{r - 1} z^{r - 1}}{z^{r - 1}} $$ to get: $$ \frac{A(z) - z - 10 z^2}{z^3} - 9 \frac{A(z) - z}{z^2} + 26 \frac{A(z)}{z} - 24 A(z) = 0 $$ Solving for $A(z)$, written as partial fractions: $$ A(z) = \frac{5}{2} \cdot \frac{1}{1 - 4 z} - \frac{4}{3} \cdot \frac{1}{1 - 3 z} + \frac{3}{2} \cdot \frac{1}{1 - 2 z} $$ Everything in sight is a geometric series: $$ a_n = \frac{5}{2} \cdot 4^n - \frac{4}{3} \cdot 3^n + \frac{3}{2} \cdot 2^n $$