<s>[INST] Solve the following recursive relation by using generating functions $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.
 [/INST] 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
$$
</s>