Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

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

share|cite|improve this question

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.