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

-
You should first write $a_n$ as a function of $n$ and then see what it can look like. In your case: $$\displaystyle a_n=3^n+\sum_{k=0}^{n-1}3^k{n-k \choose 2}$$ –  Dolma Apr 25 '13 at 13:15

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

-
At the third line of the block of equations, you have changed the sums to start at $n = 1$ instead of $n = 0$. If I understood it correctly, you just rewrote those sums from the previous line. But then $$\frac{1}{2}\sum_{n = 0}^\infty {n(n + 1)x^n}$$ turns into $$\frac{1}{2}\sum_{n = 1}^\infty {(n - 1)n x^{n - 1}} = \frac{1}{2}\sum_{n = 1}^\infty {nx^{n-1}} - \frac{1}{2}\sum_{n = 1}^\infty {n^2x^{n-1}}$$. What is wrong? –  David Čepelík Apr 26 '13 at 8:13
Huh, I see now. Both $n^2$ and $n$ are $0$ for $n = 0$. Sorry –  David Čepelík Apr 26 '13 at 13:34
Mhenni, it took me a long time to figure out what you were doing, but finally, I got it! Thanks a lot! –  David Čepelík Apr 26 '13 at 20:41
@David: You are welcome. All of us spend long time to understand things. It is natural. Good luck. –  Mhenni Benghorbal Apr 26 '13 at 20:50

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

-
Could you please explain to me what is the point of differentiating the equation? I get lost reading the second half of the answer. –  David Čepelík Apr 25 '13 at 14:06
Differentiating $\sum_{n=0}^\infty x^n=\frac{1}{1-x}$, you can get $\sum_{n=1}^\infty nx^{n-1}=\frac{1}{(1-x)^2}$. Differentiating $\sum_{n=1}^\infty nx^{n-1}=\frac{1}{(1-x)^2}$, you can get $\sum_{n=2}^\infty n(n-1)x^{n-2}=\frac{2}{(1-x)^3}$. –  xpaul Apr 25 '13 at 14:39
I see. I have never seen this before, so that's what confused me. –  David Čepelík Apr 25 '13 at 14:43

Hint Let $F:=\sum_0^\infty a_n x^n$. Consider $a_n x^n= 3 a_{n-1}x^{n}+C_n^2 x^n$.

-

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

-

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}

-