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

As I said in my comment, you have:
$$\displaystyle a_n=3^n+\sum_{k=0}^{n-1}3^k{n-k \choose 2}$$
You can rewrite this as:
$$\displaystyle a_n=3^n+\sum_{k=1}^{n}3^{n-k}{k \choose 2}=3^n+3^n\sum_{k=1}^{n}3^{-k}{k \choose 2}=3^n\left(1+\sum_{k=1}^{n}\left(\frac{1}{3}\right)^{k}{k \choose 2}\right)$$
Also you have:
$$\displaystyle\sum_{k=1}^\infty \left(\frac{1}{3}\right)^{k}{k \choose 2}=\sum_{k=0}^\infty \left(\frac{1}{3}\right)^{k}{k \choose 2}=\dfrac{\left(\frac{1}{3}\right)^{2}}{\left(1-\frac{1}{3}\right)^{3}}=\frac{3}{8}$$
