Identity for Catalan numbers

Question

Assume $C_{n}=\frac{1}{n+1} \binom{2n}{n}$ the Catalan numbers. I want to prove the following identity with generating functions. $$C_{n+1}=\sum\limits_{k=0}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{2k}2^{n-2k}C_k$$

I know that the generating function for the Catalan numbers is $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ and I can prove the following $C_{n+1}=\sum\limits_{k=0}^{n}C_kC_{n-k}$. I tried to use those two results to derive the identity above but did not succeed so far. I'm not really sure if I approach this problem the right way, especially because I don't know how to obtain the floor function for the upper bound of the sum indexing.

Answer 1

Consider the generating functions $$F(x)=\sum_{n=0}^\infty C_{n+1}x^n = \frac{1}{x}(\sum_{n=0}^\infty C_nx^n-1)=\frac{1-\sqrt{1-4x}-2x}{2x^2}$$ and $$G(x)=\sum_{n=0}^\infty\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}2^{n-2k}C_kx^n$$ We want to show these are equal. We first note that for $k>\lfloor\frac{n}{2}\rfloor$, $\binom{n}{2k}=0$, so we can replace the inner sum in $G$ with an infinite sum $$G(x)=\sum_{n=0}^\infty\sum_{k=0}^{\infty}\binom{n}{2k}2^{n-2k}C_kx^n$$ Swapping the order of summation, and using that $$\sum_{n=0}^\infty \binom{n}{m}z^n=\frac{z^m}{(1-z)^{m+1}}$$ we find $$G(x)=\sum_{k=0}^\infty C_k\frac{2^{2k}x^{2k}}{2^{2k}(1-2x)^{2k+1}}=\frac{1}{1-2x}\sum_{k=0}^\infty C_k\left(\frac{x^2}{(1-2x)^2}\right)^k$$. Letting $q=\frac{x^2}{(1-2x)^2}$, this sum is precisely the generating function of the Catalan numbers, so we get $$G(x)=\frac{1}{1-2x}\frac{1-\sqrt{1-4q}}{2q}$$ which when you fill in $q=\frac{x^2}{(1-2x)^2}$ and do some algebra, gives exactly $F(x)$. So $F(x)=G(x)$ and your identity holds.

Answer 2

We may also use

$$C_n = {2n\choose n} - {2n\choose n+1}.$$

getting for the RHS of the sum

$$\sum_{k=0}^{\lfloor n/2 \rfloor} {n\choose 2k} 2^{n-2k} {2k\choose k} - \sum_{k=0}^{\lfloor n/2 \rfloor} {n\choose 2k} 2^{n-2k} {2k\choose k+1}.$$

Now for the first piece we have

$${n\choose 2k} {2k\choose k} = \frac{n!}{(n-2k)! \times k! \times k!} = {n\choose k} {n-k\choose k}.$$

This yields

$$\sum_{k=0}^{\lfloor n/2 \rfloor} {n\choose k} 2^{n-2k} {n-k\choose n-2k} \\ = [z^n] (1+z)^n \sum_{k=0}^{\lfloor n/2 \rfloor} {n\choose k} 2^{n-2k} \frac{z^{2k}}{(1+z)^k}.$$

The coefficient extractor enforces the range and we get

$$[z^n] (1+z)^n \sum_{k\ge 0} {n\choose k} 2^{n-2k} \frac{z^{2k}}{(1+z)^k} \\ = 2^n [z^n] (1+z)^n \left(1+\frac{z^{2}}{4(1+z)}\right)^n \\ = \frac{1}{2^n} [z^n] (z+2)^{2n} = {2n\choose n}.$$

Working with the second piece we find for $k\ge 1$

$${n\choose 2k} {2k\choose k+1} = \frac{n!}{(n-2k)! \times (k-1)! \times (k+1)!} = {n\choose k-1} {n-k+1 \choose k+1}.$$

This yields (the term at $k=0$ is zero)

$$\sum_{k=1}^{\lfloor n/2 \rfloor} {n\choose k-1} 2^{n-2k} {n-k+1\choose n-2k} \\ = [z^n] (1+z)^{n+1} \sum_{k=1}^{\lfloor n/2 \rfloor} {n\choose k-1} 2^{n-2k} \frac{z^{2k}}{(1+z)^k} \\ = \frac{1}{4} [z^n] (1+z)^{n+1} \frac{z^2}{1+z} \sum_{k=0}^{\lfloor n/2 \rfloor - 1} {n\choose k} 2^{n-2k} \frac{z^{2k}}{(1+z)^k} \\ = \frac{1}{4} [z^{n-2}] (1+z)^{n} \sum_{k=0}^{\lfloor (n-2)/2 \rfloor} {n\choose k} 2^{n-2k} \frac{z^{2k}}{(1+z)^k} .$$

The coefficient extractor once more enforces the range and we get

$$\frac{1}{4} [z^{n-2}] (1+z)^{n} \sum_{k\ge 0} {n\choose k} 2^{n-2k} \frac{z^{2k}}{(1+z)^k} \\ = 2^{n-2} [z^{n-2}] (1+z)^n \left(1+\frac{z^{2}}{4(1+z)}\right)^n \\ = \frac{1}{2^{n+2}} [z^{n-2}] (z+2)^{2n} = {2n\choose n+2}.$$

Collecting the two pieces we find

$$\left(\frac{(n+1)^2}{(2n+2)(2n+1)} - \frac{(n+1)n(n-1)}{(2n+2)(2n+1)(n+2)}\right) {2n+2\choose n+1} \\ = \left(\frac{(n+2)(n+1)^2}{(2n+2)(2n+1)(n+2)} - \frac{(n+1)n(n-1)}{(2n+2)(2n+1)(n+2)}\right) {2n+2\choose n+1}.$$

Now

$$(n+2)(n+1)^2-(n+1)n(n-1) = (2n+2)(2n+1)$$

so we indeed obtain

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n+2} {2n+2\choose n+1} = C_{n+1}}$$

as claimed.