4

Some time ago i got from Polya's Urn Scheme that for the n-th Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ and the central binomial coefficient takes place the identity $$\sum_{n = 0}^\infty\frac{C_{n+k}}{4^n} = 2\binom{2k}{k}$$

I'm looking for a non-probabilistic proof of that result.

Sil
  • 16,612
Tom Keen
  • 615
  • 2
  • 8
  • 3
    That equation makes no sense. The left side is a function of $n$; the right side is a function of $k$. [Also, what's CBC? To me, that's the Canadian Broadcasting Corporation.] – Gerry Myerson Nov 19 '21 at 03:34
  • The verb in this context is "to prove", not "to proof". – Arturo Magidin Nov 19 '21 at 03:45
  • 1
    Fixed, thanks, that is the effect of the 'very first time' – Tom Keen Nov 19 '21 at 04:04
  • 2
    If there is a generating functions proof, you'd probably want to show that $\sum_{k = 0}^{\infty}\sum_{n = 0}^{\infty}\tfrac{C_{n+k}}{4^n}x^k = \sum_{k = 0}^{\infty}2\binom{2k}{k}x^k$. The right side is $\tfrac{2}{\sqrt{1-4x}}$. The left side is obviously tougher, but swapping the order of the summation, or summing the terms in a different order would be my first guess. – JimmyK4542 Nov 19 '21 at 04:16
  • @JimmyK4542 i already tried that and unfortunately i got nothing, thanks anyway – Tom Keen Nov 19 '21 at 04:20
  • You don't want a probability answer, but how about bijective enumeration? If you accepted probability and had a copy of Feller available, probability of SRW to not return to 0 before time $2n$ calculated by partitioning-and-summing over the first time to return to 0: being time $2n$, $2n+2$, etc. – Shannon Starr Jan 04 '22 at 20:07

2 Answers2

7

We want to show $$ \frac{2}{4^k}\binom{2k}{k}=\sum_{n = 0}^\infty\frac{C_{n+k}}{4^{n+k}}= \sum_{n = k}^\infty\frac{C_{n}}{4^{n}}. \tag{1}$$

Notice the following property (which can be verified for example by writing out the factorials, see also this answer): $$ \frac{C_n}{4^n}=2\left[\frac{1}{4^n}\binom{2n}{n}-\frac{1}{4^{n+1}}\binom{2n+2}{n+1}\right]. $$ Hence the partial sum of RHS in $(1)$ telescopes to $$ \sum_{n = k}^{m-1}\frac{C_{n}}{4^{n}}=\frac{2}{4^k}\binom{2k}{k}-\frac{2}{4^{m}}\binom{2m}{m}. $$

Hence $$ \sum_{n = k}^\infty\frac{C_{n}}{4^{n}}=\lim_{m\to \infty}\sum_{n = k}^{m-1}\frac{C_{n}}{4^{n}}=\frac{2}{4^k}\binom{2k}{k}. $$

We have used $\frac{2}{4^{m}}\binom{2m}{m} \to 0$ as $m \to \infty$ which can be shown for example by the Stirling's formula, see also some other ways in Determine $\lim\limits_{n \to \infty}{{n} \choose {\frac{n}{2}}}\frac{1}{2^n}$, where each $n$ is even.

Sil
  • 16,612
4

The Catalan numbers generating function power series multiplied by $x$ is $$ \frac{1-\sqrt{1-4x}}2 = \sum_{n=0}^\infty C_n x^{n+1}. \tag{1} $$ Substitute $\,y\,$ for $\,x\,$ and subtract both equations to get $$ \frac{1-\sqrt{1-4y}}2- \frac{1-\sqrt{1-4x}}2 = \sum_{n=0}^\infty C_n (y^{n+1}-x^{n+1}). \tag{2} $$ Divide both sides by $\,y-x\,$ and express $\,\frac{y^{n+1}-x^{n+1}}{y-x}\,$ as a sum to get $$ \frac{\sqrt{1-4x}-\sqrt{1-4y}}{2(y-x)} = \sum_{n=0}^\infty C_n \frac{y^{n+1}-x^{n+1}}{y-x} = \sum_{n=0}^\infty C_n\sum_{m=0}^n y^m x^{n-m}. \tag{3} $$ Simplify the left side and change summation indices on the right to get $$ \frac2{\sqrt{1-4y}+\sqrt{1-4x}} = \sum_{k=0}^\infty\sum_{n=0}^\infty C_{n+k}\,y^n x^k. \tag{4}$$ Substitute $\,y=\frac14\,$ and expand $\,\frac2{\sqrt{1-4x}}\,$ with binomial coefficients to get $$ \frac2{\sqrt{1-4x}} = \sum_{k=0}^\infty 2\binom{2k}{k}x^k = \sum_{k=0}^\infty\sum_{n=0}^\infty\frac{C_{n+k}}{4^n} x^k. \tag{5}$$ Finally, equate corresponding coefficients of $\,x^k\,$ to get $$ 2\binom{2k}{k} = \sum_{n=0}^\infty\frac{C_{n+k}}{4^n}. \tag{6} $$

Somos
  • 35,251
  • 3
  • 30
  • 76