Some recurrent formula for Catalan numbers

Question

Recently, I noticed the following recurrent formula for Catalan numbers involving binomial coefficients: $$ C_{n+1} = \sum_{i=0}^n (-1)^{n+i} \binom{i+1}{n+1-i} C_i. $$ I have checked it for small values of n. This formula appears to be similar to the famous formula $C_{n+1}=\sum_{i=0}^{n}C_i C_{n-i}$. But I don't have an idea how to prove it. Can you help me please?

Answer 1

I find it helpful to rewrite the identity as

$$\begin{align*} C_{n+1}&=\sum_{k\ge 0}(-1)^k\binom{n+1-k}{k+1}C_{n-k}\tag{1}\\ &=(n+1)C_n-\binom{n}2C_{n-1}+\binom{n-1}3C_{n-2}-+\ldots\;; \end{align*}$$

No upper limit is needed on the summation, since the binomial coefficients are eventually $0$.

$C_n$ is the number of rooted binary trees with $n$ nodes; each of these has $n+1$ open slots at which a leaf can be added. Thus, to build one of the $C_{n+1}$ trees on $n+1$ nodes we can add a leaf in any one of $n+1$ places to any of the $C_n$ trees on $n$ nodes. This produces $(n+1)C_n$ trees on $n+1$ nodes, but some of them are duplicates.

For example, consider one of the $C_{n-1}$ trees on $n-1$ nodes. There are $\binom{n}2$ ways to pick two of the vacant slots at which a leaf can be added, and each such pair produces a tree on $n+1$ nodes in two ways, one for each of the two possible orders in which the two leaves can be added. Thus, the figure $(n+1)C_n$ overcounts by $\binom{n}2C_{n-1}$, and $(n+1)C_n-\binom{n}2C_{n-1}$ is a better estimate of $C_{n+1}$.

This analysis rapidly gets a bit awkward, however. Instead of trying to pursue it directly, let $T$ be a binary tree on $n+1$ nodes, and let $\ell$ be the number of leaves of $T$. $T$ is an extension of $\ell$ different $n$-trees (i.e., binary trees on $n$ nodes) by addition of a single leaf. It is an extension of $\binom\ell2$ different $(n-1)$-trees by the simultaneous addition of $2$ leaves. And in general for $k=1,\ldots,\ell$ it is the extension of $\binom\ell k$ different $(n+1-k)$-trees by the simultaneous addition of $k$ leaves.

For $k=0,\ldots,\ell-1$ let $\mathscr{T}_k$ be the set of $(n-k)$-trees of which $T$ is an extension by simultaneous addition of leaves, so that $|\mathscr{T}_k|=\binom\ell{k+1}$. Each member of $\mathscr{T}_0$ is counted once in $(n+1)C_n$, the $k=0$ term of $(1)$. Each member of $\mathscr{T}_1$ is counted once in $\binom{n}2C_{n-1}$, the absolute value of the $k=1$ term of $(1)$. And in general each member of $\mathscr{T}_k$ is counted once in $\binom{n+1-k}{k+1}C_{n-k}$. Thus, the summation in $(1)$ counts $T$

$$\sum_{k=0}^{\ell-1}(-1)^k\binom\ell{k+1}=\sum_{k=0}^{\ell}(-1)^{k+1}\binom\ell k-\left(-\binom\ell0\right)=0+1=1$$

time. This is the case for each binary tree on $n+1$ nodes, so the summation must indeed yield $C_{n+1}$.

Answer 2

The most compact way to state this identity appears to be

$$\sum_{q=\lfloor (n+1)/2\rfloor}^{n+1} (-1)^{q} {q+1\choose n+1-q} C_q = 0.$$

Note that with $q\le n+1$ a non-negative integer $(q+1)^\underline{n+1-q} = 0$ when $n+1-q > q+1$ or $n\gt 2q$ or $n\ge 2q+1.$ This is $\lfloor (n-1)/2 \rfloor \ge q$ or $\lfloor (n+1)/2\rfloor \gt q.$ Hence we may lower the starting index to zero:

$$\sum_{q=0}^{n+1} (-1)^{q} {q+1\choose n+1-q} C_q = 0.$$

This is

$$[z^{n+1}] \sum_{q=0}^{n+1} (-1)^{q} z^q (1+z)^{q+1} C_q $$

Here the coefficient extractor enforces the upper limit of the sum and we get

$$[z^{n+1}] \sum_{q\ge 0} (-1)^{q} z^q (1+z)^{q+1} C_q \\ = [z^{n+1}] \sum_{q\ge 0} (-1)^{q} z^q (1+z)^{q+1} [w^q] \frac{1-\sqrt{1-4w}}{2w} \\ = - [z^{n+1}] (1+z) \frac{1-\sqrt{1+4z(1+z)}}{2z(1+z)} \\ = - [z^{n+1}] \frac{1-\sqrt{(1+2z)^2}}{2z} = - [z^{n+1}] (-1) = 0.$$

This is the claim.