# Recurrence equation for central trinomial coefficients

I've come across the following exercise:

Give a recurrence equation for the central coefficients $(a_n)$, where for all $n$, $a_n$ is the coefficient of $X^n$ in $(1+X+X^2)^n$.

Here's what I've tried so far: I introduced $b_k^{(n)}$, the coefficient of $X^k$ in $P_n(X) = (1+X+X^2)^n$, such that $P_n(X) = \sum\limits_{k=0}^{\infty}b_k^{(n)}X^k$, and noted that $\forall n, a_n = b_n^{(n)}$. Also $\forall n, b_k^{(n+1)} = b_k^{(n)} + b_{k-1}^{(n)} + b_{k-2}^{(n)}$. I reasoning on the derivative of $P_n$, but to no avail. I noted that the $b_k^{(n)}$ coefficients were symmetric around $k = n$, but that didn't really help.

So I calculated the first few terms, $1, 3, 7, 19, 51, 141, \ldots$. That didn't really help. At this point I started searching the web for info, and found a reference on MathWorld and on the OEIS. The former gives a recurrence equation, $(n+1)a_{n+1} = (2n + 1)a_n + 3na_{n-1}$, but I can't see where it comes from...

Hope you help!
Clément.

PS: This is not homework, but regardless I'd rather be given pointers instead of a full solution. Although I couldn't figure this out all by myself, I'd love to at least participate in the solution :)

-

If you develop the trinomial power, you can find a sum formula with two binomial coefficients, for example

$$\sum_k \binom nk \binom{n-k}k$$

A standard way to go from a binomial sum to a recurrence relation is Zeilberger's algorithm. See for example the book A=B by Petkovsek, Wilf and Zeilberger.

-
Right, but it surprises me that you need to find an explicit formula for the coefficients before searching for a recurrence equation... +1 anyway. – Clément Mar 19 '12 at 0:16
You need some expression for extracting the coefficient. A sum, or a path integral, or generating functions. The sum above is very close to the definition of trinomial coefficients. It is just a way to see that Zeilberger's algorithm is applicable. – Phira Mar 19 '12 at 11:52
I was hoping for a combinatorial proof actually, one which would involve counting objects or elements. – Clément Mar 19 '12 at 12:11

Here's how Euler did it: L. Euler, Observationes Analyticae, Novi Commentarii Acad. Sci. Petropolitanae, 11 (1765) 124-143. The recurrence equation is derived under "Problema 2", beginning on p. 129.

-