Alternative proof of an intereting identity of Catalan's Numbers and central binomial coefficients

Question

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.

Answer 1

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

Answer 2

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.