8
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ You should consult known textbooks before asking a question dlmf.nist.gov/15.4.E18 $\endgroup$ – Nemo Jan 29 at 16:07
  • 1
    $\begingroup$ Please provide some "cute" or "clever" proof. $\endgroup$ – T. Amdeberhan Jan 29 at 16:13
  • $\begingroup$ It's known that $$c(x)^a = \sum_n \frac{a}{a+2n}\binom{a+2n}{n}x^n.$$ $\endgroup$ – Max Alekseyev Jan 29 at 21:42
  • 3
    $\begingroup$ 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. $\endgroup$ – Fedor Petrov Jan 29 at 22:52
  • 1
    $\begingroup$ Another routine proof: observe that ${1 \over \sqrt{1-4x}}=(x\,C(x))^\prime $, and use Bürmann-Lagrange. $\endgroup$ – esg Jan 31 at 13:06
10
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Noam D. Elkies Jan 31 at 4:53
  • 1
    $\begingroup$ I'd say there's no question this meets the cuteness criterion. $\endgroup$ – Todd Trimble Feb 1 at 20:52
4
$\begingroup$

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}.$$

$\endgroup$
3
$\begingroup$

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).$

$\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.