Lucian Maddox

Answered

2022-07-13

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

Answer & Explanation

billyfcash5n

Expert

2022-07-14Added 17 answers

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(z)=\sum _{n\ge 0}\frac{f(n)}{n!}{z}^{n}$

Step 2

Then we have

$\begin{array}{rl}G(z)& =\left(\sum _{n\ge 0}\frac{{C}_{n}}{n!}{z}^{n}\right)-\sum _{n\ge 0}\frac{1}{n!}(\sum _{k=1}^{n-1}{\textstyle (}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}f(n-k)){z}^{n}\\ & ={e}^{2z}({I}_{0}(2z)-{I}_{1}(2z))-\sum _{n\ge 0}(-\frac{f(0)}{n!}-\frac{f(n)}{n!}+\sum _{k=0}^{n}\frac{f(n-k)}{k!(n-k)!}){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}({I}_{0}(2z)-{I}_{1}(2z))+f(0){e}^{z}+G(z)-{e}^{z}G(z)& \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(0)={C}_{0}=1$, we obtain from (3):

$\overline{){\displaystyle G(z)=1+{e}^{z}({I}_{0}(2z)-{I}_{1}(2z))}}$

If you were after the ordinary generating function

$F(z)=\sum _{n\ge 0}f(n){z}^{n}$

you can obtain it, if it converges, from the exponential one here, including $F(z)={\int}_{0}^{+\mathrm{\infty}}G(zt){e}^{-t}dt$

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\ge 0}\frac{f(n)}{n!}{z}^{n}$

Step 2

Then we have

$\begin{array}{rl}G(z)& =\left(\sum _{n\ge 0}\frac{{C}_{n}}{n!}{z}^{n}\right)-\sum _{n\ge 0}\frac{1}{n!}(\sum _{k=1}^{n-1}{\textstyle (}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}f(n-k)){z}^{n}\\ & ={e}^{2z}({I}_{0}(2z)-{I}_{1}(2z))-\sum _{n\ge 0}(-\frac{f(0)}{n!}-\frac{f(n)}{n!}+\sum _{k=0}^{n}\frac{f(n-k)}{k!(n-k)!}){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}({I}_{0}(2z)-{I}_{1}(2z))+f(0){e}^{z}+G(z)-{e}^{z}G(z)& \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(0)={C}_{0}=1$, we obtain from (3):

$\overline{){\displaystyle G(z)=1+{e}^{z}({I}_{0}(2z)-{I}_{1}(2z))}}$

If you were after the ordinary generating function

$F(z)=\sum _{n\ge 0}f(n){z}^{n}$

you can obtain it, if it converges, from the exponential one here, including $F(z)={\int}_{0}^{+\mathrm{\infty}}G(zt){e}^{-t}dt$

Most Popular Questions