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.

## Best Answer

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.