<s>[INST] 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}$.)
 [/INST] A related problem. Assume $ F(x) = \sum_{n=0}^{\infty}a_n x^n $, then
$$ a_n = {n \choose 2} + 3a_{n - 1} \implies a_{n+1} = {n+1 \choose 2} + 3a_{n}$$
$$ \sum_{n=0}^{\infty} a_{n+1} x^n = \frac{1}{2}\sum_{n=0}^{\infty}n(n+1)x^n + 3\sum_{n=0}^{\infty}a_{n}x^n  $$
$$ \implies \sum_{n=1}^{\infty} a_{n} x^{n-1} = \frac{1}{2}\sum_{n=1}^{\infty}nx^{n}+\frac{1}{2}\sum_{n=1}^{\infty}n^2x^{n} +3F(x) $$
$$ \implies \frac{1}{x}F(x)-\frac{a_0}{x}-3F(x) = \frac{1}{2}\sum_{n=1}^{\infty}nx^{n}+\frac{1}{2}\sum_{n=1}^{\infty}n^2x^{n}  $$
$$\implies \left(\frac{1}{x}-3 \right)F(x)=\frac{1}{x}+\frac{1}{2}\frac{x}{(x-1)^2}-\frac{1}{2}\frac{x(x+1)}{(x-1)^3} $$
$$ \implies \left(\frac{1}{x}-3 \right)F(x)=\frac{1}{x}-\frac{x}{(x-1)^3} $$
$$ \implies F(x)=\frac{x}{1-3x}\left(  \frac{1}{x}-\frac{x}{(x-1)^3} \right). $$
</s>