# Find the generating function of f ( n ) = <munderover> &#x2211;<!-- ∑ --> <mrow

Find the generating function of $f\left(n\right)=\sum _{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-1{\right)}^{n-k}{C}_{k}$
I want to find the generating function of $f\left(n\right)=\sum _{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-1{\right)}^{n-k}{C}_{k}$, where ${C}_{k}$ is the k-th Catalan number. So, using the definition of an ordinary generating function:
$F\left(x\right)=\sum _{n\ge 0}\left(\sum _{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-1{\right)}^{n-k}{C}_{k}\right){x}^{n}$
recalling that: $C\left(x\right)=\sum _{n\ge 0}{C}_{n}{x}^{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?
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Alexia Hart
Explanation:
$\begin{array}{rl}F\left(x\right)& =\sum _{n\ge 0}\left(\sum _{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-1{\right)}^{n-k}{C}_{k}\right){x}^{n}\\ & =\sum _{k\ge 0}\left(-1{\right)}^{k}{C}_{k}\sum _{n\ge k}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-x{\right)}^{n}\\ & =\sum _{k\ge 0}\left(-1{\right)}^{k}{C}_{k}\frac{\left(-x{\right)}^{k}}{\left(1+x{\right)}^{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{array}$