3
$\begingroup$

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

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Right, but it surprises me that you need to find an explicit formula for the coefficients before searching for a recurrence equation... +1 anyway. $\endgroup$ – Clément Mar 19 '12 at 0:16
  • $\begingroup$ 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. $\endgroup$ – Phira Mar 19 '12 at 11:52
  • $\begingroup$ I was hoping for a combinatorial proof actually, one which would involve counting objects or elements. $\endgroup$ – Clément Mar 19 '12 at 12:11
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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