Generating function of $f(n) = C_n - \sum_{k=1}^{n-1}\binom{n}{k}f(n-k)$

Solution 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(z)=\sum_{n\geq 0} \frac {f(n)} {n!}z^n$$ Then we have $$\begin{split} G(z)&=\left(\sum_{n\geq 0}\frac{C_n}{n!}z^n\right)-\sum_{n\geq 0}\frac 1 {n!}\left(\sum_{k=1}^{n-1}{n\choose k}f(n-k)\right)z^n\\ &=e^{2z}\left( I_0(2z) - I_1(2z)\right) - \sum_{n\geq 0}\left(-\frac{f(0)}{n!}-\frac{f(n)}{n!}+\sum_{k=0}^{n}\frac{f(n-k)}{k!(n-k)!}\right)z^n&\,\,\,\,\,\,\text{(1)}\\ &=e^{2z}\left( I_0(2z) - I_1(2z)\right)+ f(0)e^z+G(z)- e^zG(z)&\,\,\,\,\,\,\text{(2)}\\ \end{split}$$ 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.

Using $f(0)=C_0=1$, we obtain from $(3)$: $$\boxed{G(z)=1+e^z\left( I_0(2z) - I_1(2z)\right)}$$

If you were after the ordinary generating function $$F(z)=\sum_{n\geq 0}f(n)z^n$$ you can obtain it, if it converges, from the exponential one here, including $$F(z)=\int_0^{+\infty}G(zt)e^{-t}dt$$