# 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 :)

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