# Eikonal Blog

## 2012.11.26

### Generating functions

Recently I have been rereading the Herbert S. Wilf’s free online book Generatingfunctionologyhttp://www.math.upenn.edu/~wilf/DownldGF.html. It is choke-full of interesting results.

## Definitions

For a number series ${\bf a} :\equiv \{a_n|n\in\{0,\infty\}\}$ one defines following generating functions (GFs):

• Ordinary Power Series GF (OPSGF): $OPSGF[a](x) :\equiv \sum_{n=0}^\infty a_n x^n \leftrightarrow_{opsgf} {\bf a}$;
• Exponential Series GF (EGF): $EGF[a](x) :\equiv \sum_{n=0}^\infty a_n \frac{x^n}{n!} \leftrightarrow_{egf} {\bf a}$;
• Dirichlet GF (DGF): $DGF(x;s) :\equiv \sum_n \frac{a_n}{n^s} x^n \leftrightarrow_{dgf} {\bf a}$;
• Lambert GF (LGF): $LGF(x) :\equiv \sum_n \frac{a_n}{1-x^n} x^n \leftrightarrow_{lgf} {\bf a}$;
• Bell GF (BGF): $BGF(x;s) :\equiv \sum_n a_{p^n} x^n \leftrightarrow_{bgf} {\bf a}$;
• Poisson GF (PGF): $PGF(x;s) :\equiv \sum_n \frac{a_n}{n!} x^n e^{-x} = e^{-x} EGF(x) \leftrightarrow_{pgf} {\bf a}$;

## Simple results

• $\{a_n=n\} \leftrightarrow_{opsgf} f(x) = \frac{x}{(1-x)^2}$.
• $\{a_n=n^2\} \leftrightarrow_{opsgf} f(x) = \frac{x(x+1)}{(1-x)^3}$.
• $\{a_n=b^n\} \leftrightarrow_{opsgf} f(x) = \frac{1}{1-b x}$.
• $\{a_n=n\} \leftrightarrow_{egf} f(x) = x e^{x}$.
• $\{a_n=n^2\} \leftrightarrow_{egf} f(x) = x(x+1)e^{x}$.
• $\{a_n=b^n\} \leftrightarrow_{egf} f(x) = e^{b x}$.
• For Fibonacci numbers $\{F_n|F_{n+1} = F_n + F_{n-1} | f_0 = F_1 = 1\}$ one has: $OPSGF(x) = \frac{x}{1-x-x^2}$, leading to $F_n = \frac{r_+^n-(r_-^n}{\sqrt{5}}$ ($r_\pm = \frac{1\pm\sqrt{5}}{2}$).
• $\{a_n|a_{n+1}=2 a_n + 1| a_0=0\} \leftrightarrow_{opsgf} OPSGF = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x}$; which leads to $a_n=2^n - 1$.
• For $a_{n+1} = 2 a_n + n$, $alatex _0=1$ one has: $OPSGF = \frac{2}{1-2x} - \frac1{(1-x)^2}$ leading to
$a_n = 2^{n-1} - n - 1$.

Define $[x^n]f(x)$ as the coefficient next to $x^n$ in power series $f(x)$. Examples and properties:

• $[x^n] e^x = \frac1{n!}$,
• $[x^n] \frac1{1-ax} = a^n$,
• $[x^n] (1+x)^s = \binom{s}{n}$,
• $[x^n] \{x^m f(x)\} = [x^{n-m}] f(x)$,
• $[\lambda x^n] f(x) = \frac1{\lambda} [x^n]f(x)$,
• $\left[\frac{x^n}{n!}\right] e^x = 1$.

For binomial coeficients:

• $\sum_{k=0}^{\infty} \binom{n}{k} x^k = (1+x)^n$,
• $\sum_{n=0}^{\infty} \binom{n}{k} y^n = \frac{y^k}{(1-y)^{k+1}}$,
• $\binom{n}{k} = [x^k y^n] \frac1{1 - y (1+x)}$.

Some orthogonal polynomials:

• Tchebitshev polynomials generating function: $\sum_{n=0}^\infty \frac{z^n}{n!} T_n(x) = e^{zx}\cos(z\sqrt{1-x^2})$.
• Legendre polynomials generating function: $\frac1{(1-2tz+z^2)^{\frac12}} = \sum_{n=0}^\infty P_n(t)z^n$.
• Generating function for associated Legendre polynomials: $(1-2tc+t^2)^{\alpha} = |1-t e^{i\theta}|^{2\alpha} = \sum_{n=0}^\infty t^n P_n^{\alpha}(c)$.

## Dirichlet series generating functions

• For $a_n=1$: $DGF = \zeta(s)$.
• For $a_n=\mu(n)$ (the Moebius function): $DGF = \frac1{\zeta(s)}$.
• For $a_n=d(n)=\sigma_0(n)$ (the zeroth-order divisor function): $DGF = \zeta(s)^2$.
• For $a_n=\sigma_k(n)$ (the $k$th-order divisor function): $DGF = \zeta(s)\zeta(s-k)$.
• For $a_n=\phi(n)$ (the totient function): $DGF = \frac{\zeta(s-1)}{\zeta(s)}$.
• For $a_n=H(n)$ (the number of ordered factorizations): $DGF = \frac{1}{2 - \zeta(s)}$.
• For $a_n=\frac12 [1-(-1)^n]$: $DGF = \lambda(s)$ (the Dirichlet lambda function).

Moebius inversion formula:

• If two DGF series $A(s)$ and $B(s)$ have coefficient relation $a_n = \sum_{d|n} b_d$, then $A(s) = B(s) \zeta(s)$, and $b_n = \sum_{d|n} \mu\left(\frac{n}{d}\right) a_d$.
• If $a_n = \sum_{d|n} b_d$, then $b_n = \sum_{d|n} \mu\left(\frac{n}{d}\right) a_d$.