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}$.)
Best Answer
Let $A(x)=\sum_{n=0}^\infty a_nx^n$. Then \begin{eqnarray} A(x)&=&1+\sum_{n=1}^\infty a_{n}x^n\\ &=&1+\sum_{n=1}^\infty (3a_{n-1}+\frac{1}{2}n(n-1))x^n\\ &=&1+3xA(x)+\frac{1}{2}\sum_{n=1}^\infty n(n-1)x^n. \end{eqnarray} Note $\sum_{n=0}^\infty x^n=\frac{1}{1-x}$ for $|x|<1$. Differentiating this twice, you can give $$ \sum_{n=2}^\infty n(n-1)x^{n-2}=\frac{2}{(1-x)^3}. $$ Thus $$ A(x)=1+3xA(x)+\frac{x^2}{(1-x)^3} $$ from which you can get $A(x)$.