Identity for Catalan numbers 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.
 A: 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.
A: 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.
