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.

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.
