I have combinatorially found this recurrence for a class of Dyck paths:
$$f(n) = C_n – \sum_{k=1}^{n-1}\binom{n}{k}f(n-k)$$ where $C_n$ is the $n$-th Catalan Number.
Now I want to write the generating function of $f(n)$, but I am not sure how to set up it, can someone help me please?
Best Answer
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$$