 # Generating Function of Riordan numbers I would like to find generating function of f(n), where f(n) Joshua Foley 2022-07-08 Answered
Generating Function of Riordan numbers
I would like to find generating function of f(n), where f(n) is defined as following: $f\left(n\right)=\sum _{k}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-1{\right)}^{n-k}{C}_{k}\text{.}$
With ${C}_{k}=\frac{1}{k+1}\left(\genfrac{}{}{0}{}{2k}{k}\right)$ (${C}_{k}$ is the ${k}^{th}$ Catalan's number).
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it SweallySnicles3
Step 1
We have for the sum
$\sum _{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-1{\right)}^{n-k}{C}_{k}=\sum _{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-1{\right)}^{k}{C}_{n-k}\phantom{\rule{0ex}{0ex}}=\left[{z}^{n}\right]\frac{1-\sqrt{1-4z}}{2z}\sum _{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left(-1{\right)}^{k}{z}^{k}=\left[{z}^{n}\right]\frac{1-\sqrt{1-4z}}{2z}\left(1-z{\right)}^{n}\phantom{\rule{0ex}{0ex}}=\phantom{\rule{thickmathspace}{0ex}}\underset{z}{\mathrm{r}\mathrm{e}\mathrm{s}}\phantom{\rule{thickmathspace}{0ex}}\frac{1}{{z}^{n+1}}\left(1-z{\right)}^{n}\frac{1-\sqrt{1-4z}}{2z}.$
Step 2
Now put $z/\left(1-z\right)=w$ so that $z=w/\left(1+w\right)$ and $dz=1/\left(1+w{\right)}^{2}\phantom{\rule{thickmathspace}{0ex}}dw$ to find
$\phantom{\rule{thickmathspace}{0ex}}\underset{w}{\mathrm{r}\mathrm{e}\mathrm{s}}\phantom{\rule{thickmathspace}{0ex}}\frac{1}{{w}^{n+1}}\left(1+w\right)\frac{1-\sqrt{1-4w/\left(1+w\right)}}{2w/\left(1+w\right)}\frac{1}{\left(1+w{\right)}^{2}}\phantom{\rule{0ex}{0ex}}=\phantom{\rule{thickmathspace}{0ex}}\underset{w}{\mathrm{r}\mathrm{e}\mathrm{s}}\phantom{\rule{thickmathspace}{0ex}}\frac{1}{{w}^{n+1}}\frac{1+w-\sqrt{\left(1+w{\right)}^{2}-4w\left(1+w\right)}}{2w\left(1+w\right)}\phantom{\rule{0ex}{0ex}}=\phantom{\rule{thickmathspace}{0ex}}\underset{w}{\mathrm{r}\mathrm{e}\mathrm{s}}\phantom{\rule{thickmathspace}{0ex}}\frac{1}{{w}^{n+1}}\frac{1+w-\sqrt{1-2w-3{w}^{2}}}{2w\left(1+w\right)}.$
It follows that the desired OGF is $\frac{1+w-\sqrt{1-2w-3{w}^{2}}}{2w\left(1+w\right)}.$.

We have step-by-step solutions for your answer!