# Looking for a “cute” justification for a Catalan-type generating function

The Catalan numbers $$C_n=\frac1{n+1}\binom{2n}n$$ have the generating function $$c(x)=\frac{1-\sqrt{1-4x}}{2x}.$$ Let $$a\in\mathbb{R}^+$$. It seems that the following holds true $$\frac{c(x)^a}{\sqrt{1-4x}}=\sum_{n=0}^{\infty}\binom{a+2n}nx^n.$$

QUESTION. Why?

• You should consult known textbooks before asking a question dlmf.nist.gov/15.4.E18 – Nemo Jan 29 at 16:07
• Please provide some "cute" or "clever" proof. – T. Amdeberhan Jan 29 at 16:13
• It's known that $$c(x)^a = \sum_n \frac{a}{a+2n}\binom{a+2n}{n}x^n.$$ – Max Alekseyev Jan 29 at 21:42
• it is straightforward to get a differential equation of order 2 for the RHS (based on ${a+2n\choose n}(a+n)=(a+2n-1)(a+2n){a+2(n-1)\choose n-1}$) and check that LHS satisfies it and appropriate initial conditions. Not very clever, but quite a universal method. – Fedor Petrov Jan 29 at 22:52
• Another routine proof: observe that ${1 \over \sqrt{1-4x}}=(x\,C(x))^\prime$, and use Bürmann-Lagrange. – esg Jan 31 at 13:06

Here's a way to do it:

Recall that $$C_n$$ counts the number of lattice paths from $$(0,0)$$ to $$(2n,0)$$ taking only steps of the form $$(1,\pm 1)$$ that never goes below the $$x$$-axis; call this a Dyck path. Further, $$\frac{1}{\sqrt{1 - 4x}} = \sum \binom{2n}{n}x^k$$ which counts the total number of paths from $$(0,0)$$ to $$(2n,0)$$; call this a bridge. Also, $$\binom{a+2n}{n}$$ is the number of lattice paths (with the same step set) from $$(0,0)$$ to $$(2n+a,a)$$, since we have $$a + 2n$$ steps total with $$n$$ down steps (and thus $$a + n$$ up steps); call this an upward path.

Every upward path can be decomposed into:

• A bridge (up to the last time it hits $$0$$).

• A single up step

• A dyck path (up until the last time it hits $$1$$).

• another single step

• a dyck path

and so on.

This provides a bijection from a single bridge with an $$a$$-vector of Dyck paths. Since the generating function for a single bridge with $$a$$-vector of Dyck paths is exactly the left-hand-side of your equality, it must equal the right-hand side.

• As it stands such an argument would prove it only for integers $a>0$ — but that's enough because for each $n$ the equality of $x^n$ coefficients is a polynomial identity in $a$. – Noam D. Elkies Jan 31 at 4:53
• I'd say there's no question this meets the cuteness criterion. – Todd Trimble Feb 1 at 20:52

Combining comments of @esg and myself, we have $$\frac{c(x)^a}{\sqrt{1-4x}} = c(x)^a(xc(x))' = \frac{1}{(a+1)x^a}((xc(x))^{a+1})'$$ and thus $$[x^n]\ \frac{c(x)^a}{\sqrt{1-4x}} = \frac{1}{a+1}[x^{n+a}]\ ((xc(x))^{a+1})'=\frac{n+a+1}{a+1} [x^n]\ c(x)^{a+1}$$ $$= \frac{n+a+1}{a+1}\frac{a+1}{a+1+2n}\binom{a+1+2n}{n}=\binom{a+2n}{n}.$$

Let $$C_a(x)=\frac{c(x)^a}{\sqrt{1-4x}}$$ and $$B_a(x) =\sum_{n=0}^{\infty}\binom{a+2n}nx^n.$$

The identity $$c(x)=1+xc(x)^2$$ implies $$C_{a+1}(x)= C_{a}(x)+x C_{a+2}(x).$$

The recursion for the binomial coefficients implies $$B_{a+1}(x)= B_{a}(x)+x B_{a+2}(x)$$.

If we show that $$B_a(x)=C_a(x)$$ holds for $$a=1$$ then it holds for all positive integers.

This follows from $$B_1(x)=\frac{1}{2} \sum_{n=0}^{\infty}\binom{2+2n}{n+1}x^n= \frac{1}{2x}(B_0(x)-1)=C_1(x).$$