Verifying Touchard's Identity

Question

$$C_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor}{n\choose 2k}\cdot C_k\cdot 2^{n-2k}$$ where $C_n$ are the Catalan numbers.

I think we start by diving both sides by $2^n$, but unsure of where to go from there

Answer 1

Notice that $2^{-2k}\binom{n}{2k}\binom{2k}{k}=\binom{n/2}{k}\cdot \binom{n/2-1/2}{k}$. So

$$A_n=\sum_{k=0}^{\lfloor n/2 \rfloor}2^n \cdot 2^{-2k}\cdot \binom{n}{2k}\binom{2k}{k}\cdot\dfrac{1}{k+1}=2^n\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n/2}{k}\cdot \binom{n/2-1/2}{k}\cdot\dfrac{1}{k+1}$$

Without loss of generality, suppose $n/2 \in \mathbb{N}$. By Vandermonde's identity, we have

$$A_n=\dfrac{2^n}{n/2+1} \cdot \binom{n+1/2}{n/2}=\dfrac{1}{n+2}\binom{2(n+1)}{n+1}=C_{n+1}$$

Answer 2

Here is a proof using the method by Wilf from Generatingfunctionology.

Suppose we are trying to show that $$C_{n+1} = 2^n \sum_{k=0}^{\lfloor n/2 \rfloor} {n\choose 2k} C_k 2^{-2k}$$ where $C_n = \frac{1}{n+1}{2n\choose n}$ is the $n$-th Catalan number.

Recall the Catalan number recurrence $$C_{n+1} = \sum_{k=0}^n C_k C_{n-k}$$ which implies for the generating function $C(z)$ of these numbers that $$\frac{C(z)-1}{z} = C(z)^2$$ which has solutions $$C_{1,2}(z) = \frac{1\pm \sqrt{1-4z}}{2z}$$ of which the second one is analytic at zero so that $$C(z) = \frac{1- \sqrt{1-4z}}{2z}.$$

Following Wilf we introduce the generating function $D(z)$ where $$D(z) = \sum_{n\ge 0} z^n 2^n \sum_{k=0}^{\lfloor n/2 \rfloor} {n\choose 2k} C_k 2^{-2k} = \sum_{k\ge 0} C_k 2^{-2k} \sum_{n\ge 2k} {n\choose 2k} z^n 2^n \\ = \sum_{k\ge 0} C_k 2^{-2k} \sum_{n\ge 0} {n+2k\choose 2k} z^{n+2k} 2^{n+2k} = \sum_{k\ge 0} C_k z^{2k} \sum_{n\ge 0} {n+2k\choose 2k} z^n 2^n \\ = \sum_{k\ge 0} C_k z^{2k} \frac{1}{(1-2z)^{2k+1}}.$$

This gives that $$D(z) = \frac{1}{1-2z} \frac{1-\sqrt{1-4z^2/(1-2z)^2}}{2z^2/(1-2z)^2} \\ = \frac{(1-2z)^2}{1-2z} \frac{1-\sqrt{1-4z^2/(1-2z)^2}}{2z^2} = (1-2z) \frac{1-\sqrt{1-4z^2/(1-2z)^2}}{2z^2} \\= \frac{1-2z-\sqrt{(1-2z)^2-4z^2}}{2z^2} = \frac{1-2z-\sqrt{1-4z}}{2z^2}.$$

On the other hand $$\sum_{n\ge 0} C_{n+1} z^n = \frac{C(z)-1}{z} = \frac{1}{z} \left(\frac{1- \sqrt{1-4z}}{2z} -1 \right) \\ = \frac{1}{z} \left(\frac{1- 2z -\sqrt{1-4z}}{2z}\right) = \frac{1- 2z -\sqrt{1-4z}}{2z^2}.$$

We have equality, QED.