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?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ You should consult known textbooks before asking a question dlmf.nist.gov/15.4.E18 $\endgroup$
    – Nemo
    Commented Jan 29, 2020 at 16:07
  • 1
    $\begingroup$ Please provide some "cute" or "clever" proof. $\endgroup$
    – T. Amdeberhan
    Commented Jan 29, 2020 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
    Commented Jan 29, 2020 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
    Commented Jan 29, 2020 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
    Commented Jan 31, 2020 at 13:06

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Jan 31, 2020 at 4:53
  • 1
    $\begingroup$ I'd say there's no question this meets the cuteness criterion. $\endgroup$
    – Todd Trimble
    Commented Feb 1, 2020 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}.$$

Improve this answer
$\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).$

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .