2022-07-13

Generating function of $f\left(n\right)={C}_{n}-\sum _{k=1}^{n-1}\left(\genfrac{}{}{0}{}{n}{k}\right)f\left(n-k\right)$.

billyfcash5n

Expert

Step 1
There are multiple types of generating functions (ordinary, exponential etc.). Your question is non-specific, so we'll go for the exponential generating function since the second part of the recurrence function looks like a binomial convolution.
So let's compute
$G\left(z\right)=\sum _{n\ge 0}\frac{f\left(n\right)}{n!}{z}^{n}$
Step 2
Then we have
$\begin{array}{rl}G\left(z\right)& =\left(\sum _{n\ge 0}\frac{{C}_{n}}{n!}{z}^{n}\right)-\sum _{n\ge 0}\frac{1}{n!}\left(\sum _{k=1}^{n-1}\left(\genfrac{}{}{0}{}{n}{k}\right)f\left(n-k\right)\right){z}^{n}\\ & ={e}^{2z}\left({I}_{0}\left(2z\right)-{I}_{1}\left(2z\right)\right)-\sum _{n\ge 0}\left(-\frac{f\left(0\right)}{n!}-\frac{f\left(n\right)}{n!}+\sum _{k=0}^{n}\frac{f\left(n-k\right)}{k!\left(n-k\right)!}\right){z}^{n}& \phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\text{(1)}\\ & ={e}^{2z}\left({I}_{0}\left(2z\right)-{I}_{1}\left(2z\right)\right)+f\left(0\right){e}^{z}+G\left(z\right)-{e}^{z}G\left(z\right)& \phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\text{(2)}\end{array}$
where (1) uses the generating function for Catalan numbers, and in (2) we use the formula for the product of two series (Cauchy product). Here ${I}_{0}$ and ${I}_{1}$ represent the modified Bessel functions of the first kind.
Step 3
Using $f\left(0\right)={C}_{0}=1$, we obtain from (3):
$\overline{)G\left(z\right)=1+{e}^{z}\left({I}_{0}\left(2z\right)-{I}_{1}\left(2z\right)\right)}$
If you were after the ordinary generating function
$F\left(z\right)=\sum _{n\ge 0}f\left(n\right){z}^{n}$
you can obtain it, if it converges, from the exponential one here, including $F\left(z\right)={\int }_{0}^{+\mathrm{\infty }}G\left(zt\right){e}^{-t}dt$

Do you have a similar question?