Finding generating function for the recurrence $a_0 = 1$, $a_n = {n \choose 2} + 3a_{n - 1}$ I am trying to find generating function for the recurrence:


*

*$a_0 = 1$,

*$a_n = {n \choose 2} + 3a_{n - 1}$ for every $n \ge 1$.


It looks like this:


*

*$a_0 = 1$

*$a_1 = {1 \choose 2} + 3$

*$a_2 = {2 \choose 2} + 3{1 \choose 2} + 9$

*$a_3 = {3 \choose 2} + 3{2 \choose 2} + 9{1 \choose 2} + 27$

*$a_4 = {4 \choose 2} + 3{3 \choose 2} + 9{2 \choose 2} + 27 {1 \choose 2} + 81$


I know what the generating function of the sequence $3 ^n = (1, 3, 9, 27, 81, \dots)$ is, as well as what the generating functions for some sequences of combinatorial numbers are, but how do I split the sequence up into these pieces I know?
(The problem is those combinatorial numbers "move right" every time. If they were growing left-to-right along with their coefficients, it would be much easier. And there is no constant difference between $a_i$ and $a_{i + 1}$.)

Sneaky. Write your recurrence without subtractions in indices, i.e.:
$$
a_{n + 1} = 3 a_n + \binom{n + 1}{2}
$$
Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums, particularly:
\begin{align}
\sum_{n \ge 0} \binom{n + 1}{2} z^n
  &= z \sum_{n \ge 0} \binom{n + 1}{2} z^{n - 1} \\
  &= z \sum_{n \ge 0} \binom{n + 2}{2} z^n \\
  &= \frac{z}{(1 - z)^3}
\end{align}
so that:
$$
\frac{A(z) - a_0}{z} = 3 A(z) + \frac{z}{(1 - z)^3}
$$
Using $a_0 = 1$ and solving as partial fractions:
$$
A(z) = \frac{11}{8 (1 - 3 z)}
         - \frac{1}{2 (1 - z)^3}
         + \frac{1}{4 (1 - z)^2}
         - \frac{1}{8 (1 - z)}
$$
We can read off the coefficients here:
\begin{align}
a_n &= \frac{11}{8} \cdot 3^n
         - \frac{1}{2} \binom{-3}{n} (-1)^n
         + \frac{1}{4} \binom{-2}{n} (-1)^n
         - \frac{1}{8} \\
    &= \frac{11 \cdot 3^n - 1}{8}
         - \frac{1}{2} \binom{n + 3 - 1}{3 - 1}
         + \frac{1}{4} \binom{n + 2 - 1}{2 - 1} \\
    &= \frac{11 \cdot 3^n - 1}{8}
         - \frac{1}{2} \cdot \frac{(n + 2) (n + 1)}{2!}
         + \frac{1}{4} \cdot \frac{n + 1}{1!} \\
    &= \frac{11 \cdot 3^n - 2 n^2 - 4 n - 3}{8}
\end{align}
