I want to find the generating function of $f(n) = \sum_{k = 0}^n \binom{n}{k} (-1)^{n-k}C_{k}$, where $C_k$ is the $k$-th Catalan number. So, using the definition of an ordinary generating function:
$$F(x)=\sum_{n \ge 0} \biggl(\sum_{k = 0}^n \binom{n}{k} (-1)^{n-k}C_{k} \biggr)x^n$$
recalling that: $$C(x) =\sum_{n \ge 0}C_nx^n = \frac{1- \sqrt{1-4x}}{2x}$$
The first idea was to see $F(x)$ as a product of two formal series and I have already seen a proof in this regard where they use the theorem of residues, yet I am looking for something less refined. Any idea?
Best Answer
\begin{align} F(x) &= \sum_{n \ge 0} \left(\sum_{k = 0}^n \binom{n}{k} (-1)^{n-k}C_{k} \right)x^n \\ &= \sum_{k \ge 0} (-1)^k C_{k} \sum_{n \ge k} \binom{n}{k} (-x)^n \\ &= \sum_{k \ge 0} (-1)^k C_{k} \frac{(-x)^k}{(1+x)^{k+1}} \\ &= \frac{1}{1+x}\sum_{k \ge 0} C_{k} \left(\frac{x}{1+x}\right)^k \\ &= \frac{1}{1+x}\cdot \frac{1-\sqrt{1-4\cdot\frac{x}{1+x}}}{2\cdot\frac{x}{1+x}} \\ &= \frac{1-\sqrt{\frac{1-3x}{1+x}}}{2x} \end{align}