generating functions

The basic generating function has the form:

    \[ \boxed{G(z) = g_0+g_1 z+g_2 z^2 +g_3 z^3 +g_4 z^4 + \dotsb = \sumzn{g_n}} \]

G(z), or G for short, is the generating function for the sequence \seqd{g_0,g_1,g_2}, also called \angb{g_n}. The coefficient g_n of z^n in G is denoted [z^n]G(z).

There are two kinds of “closed form” in generatingfunctionology.

  • a closed form for G(z) , expressed in terms of z, and
  • a closed form for g_n , expressed in terms of n.

e.g. the generating function for Fibonacci numbers has the closed form z/(1-z-z^2); the Fibonacci numbers themselves have the closed form (\phi^n-\hat{\phi}^n)/\sqrt{5}.

Solving recurrences – THE METHOD

Given a sequence \angb{g_n} that satisfies a given recurrence, we seek a closed form for g_n in terms of n. A solution to this problem via generating functions proceeds in four steps:

  1. Write down a single equation that expresses g_n in terms of other elements of the sequence. This equation should be valid for all integers n, assuming that g_{{}^\_1}=g_{{}^\_2}=\dotsb=0.
  2. Multiply both sides of the equation by z^n and sum over all n. This gives, on the left, the sum \sum_n g_n z^n, which is the generating function G(z). The right-hand side should be manipulated so that it becomes some other expression involving G(z).
  3. Solve the resulting equation, getting a closed form for G(z).
  4. To find an exact formula, a closed form for the sequence:
    • Expand G(z) into a power series and read off the coefficient of z^n.
    • If G is a rational function (quotient of two polynomials)
      • expand in partial fractions and handle the terms separately.
      • OR: If the roots of the denominator polynomial are all different, use the rational expansion theorem below.

The “routine stunt”

    \[ \boxed{\sumn nx^n = \sumn x (\ddx) x^n = x (\ddx) \sumn  x^n = x (\ddx) \fr{1-x}=\frac{x}{(1-x)^2}}\]

Expanding partial fractions
e.g. Expand A(x) = \dfrac{1-2x+2x^2}{(1-x)^2(1-2x)}.
This will be expandable in the form \dfrac{A}{(1-x)^2}+\dfrac{B}{1-x}+\dfrac{C}{1-2x}.
To find A, multiply both sides by (1-x)^2 and let x=1. \To A=-1
To find C, multiply both sides by 1-2x and let x=1/2. \To C=2
To find B, substitute in x=0 and use the values of A and C to find B. \To B=0
So A(x)= \dfrac{-1}{(1-x)^2}+ \dfrac{2}{1-2x}

Rational expansion theorem for distinct roots

If R(z)=P(z)/Q(z), where Q(z)=q_0(1-\rho_1 z)\dots(1-\rho_m z) and the roots (\rho_1,\dots,\rho_m) are distinct, and if P(z) is a polynomial of degree less than m, then

    \[\boxed{[z^n] R(z)=a_1\rho_1^n+\dotsb+a_m\rho_m^n \text{, where } a_k=\frac{-\rho_k P(1/\rho_k)}{Q'(1/\rho_k)}}\]


    \[\boxed{[z^n] R(z)=\sum_{k=1}^m \frac{-\rho_k^{n+1} P(1/\rho_k)}{Q'(1/\rho_k)}}\]

When Q(z) is quadratic, i.e. m=2, the equation becomes

    \[\boxed{[z^n] R(z) = -\rho_1^{n+1}\frac{P(1/\rho_1)}{Q'(1/\rho_1)}-\rho_2^{n+1}\frac{P(1/\rho_2)}{Q'(1/\rho_2)}}\]

Basic generating function manipulations

    \begin{align*} \alpha F(z)+\beta G(z) &= \sum_{n}(\alpha f_n+\beta g_n)z^n\\ z^m G(z) &= \sum_n g_{n-m} z^n, \text{ integer } m\ges 0\\ \frac{G(z)-g_0-g_1 z-\dotsb -g_{m-1}z^{m-1}}{z^m} &= \sumzn{g_{n+m}}, \text{ integer } m\ges 0\\ G(cz) &= \sum_n c^n g_n z^n\\ G'(z) &= \sum_n (n+1)g_{n+1}z^n\\ zG'(z) &= \sum_n n g_n z^n\\ \int_0^z G(t) \,\mathrm{d}t &= \snge{1} \fr{n}g_{n-1}z^n\\ F(z)G(z) &= \sum_n \left(\sum_k f_k g_{n-k}\right)z^n\\ \fr{1-z}G(z) &= \sum_n\left(\sum_{k \les n} g_k\right)z^n\\ \end{align*}

The calculus of ordinary power series generating functions

Definition. The symbol f \ops \anzi means that the series f is the ordinary power series (‘ops’) generating function for the sequence \anzi, i.e. f=\sum_n a_n z^n.

Shifting the subscript by 1. \To the series changes by difference quotient (f-a_0)/x

    \[\sumzn{a_{n+1}} = \fr{z} \sum_{m \ges 1} a_m z^m = \frac{f(z)-f(0)}{z}.\]

Therefore f \ops \anzi \To \dfrac{f-a_0}{z} \ops \azi{n+1}.
Shift subscript by 2 \To Iterate the difference quotient operation.

    \[ \azi{n+2} \ops \frac{\big((f-a_0)/z\big)-a}{z} = \frac{f-a_0-a_1z}{z^2}.\]

e.g. the Fibonacci recurrence relation F_{n+2}=F_{n+1}+F_n (n \ges 0,F_0=0,F_1=1) translates directly into \dfrac{f-x}{x^2}=\dfrac{f}{x}+f.

Rule 1. Shifting subscript. If f \ops \anzi, then, for integer h \geq 0,

    \[ \boxed{\azi{n+h} \ops \frac{f-a_0-a_1z-\dotsb-a_{h-1}z^{h-1}}{z^h}}\]

Multiplying terms by n and its powers. \sum_n n a_n x^n=xf'. To multiply the nth member of a sequence by n causes its ops generating function to be multiplied by x(\ddx), which we will write as xD. i.e.

    \[f \ops \anzi \To (xDf) \ops \zi{na_n}.\]

What generates \zi{n^2a_n} ? (xD)^2f. In general,

    \[(xD)^kf \ops \{n^ka_n\}_{n \ges 0}. \]

What generates \{(3-7n^2)a_n\}_{n \ges 0} ?
Do the same thing to xD that is done to n: (3-7(xD)^2)f.

Rule 2. If f \ops \anzi, and P is a polynomial,

    \[\boxed{P(xD)f \ops \{P(n)a^n\}_{n \ges 0}.}\]

Find = \sum_{n \ges 0} (n^2+4n+5)/n! (The terms are 5,10,\frac{17}{2},\frac{13}{3},\frac{37}{24},\frac{5}{12}\dots)
The answer is the value at x=1 of the power series (ignoring convergence issues).

    \begin{align*} \{(xD)^2+4(xD)+5\}e^x&=\{x^2+x\}e^x+4xe^x+5e^x\\ &=(x^2+5x+5)e^x\\ &=11e.\\ \end{align*}

Find a closed formula for the sum of the squares of the first N positive integers.
Begin with the fact that \sum_{n=0}^N x^n=\dfrac{x^{N+1}-1}{x-1}. To obtain the desired series, apply (xD)^2 to both sides, then set x=1.

    \begin{align*} \sum_{n=1}^N n^2 &= (xD)^2 \left\{ \frac{x^{N+1}-1}{x-1} \right\} \text{ when } x=1.\\ &=\text{..then a miracle occurs..}\\ &=\frac{N(N+1)(2N+1)}{6} \end{align*}

Rule 3. Multiplication of two gfs. If f \ops \anzi and g \ops \zi{b_n}, then

    \[\boxed{fg \ops \left\{\sum_{r=0}^n a_r b_{n-r} \right\}_{n=0}^\infty }\]

If f,g,h are three series that generate sequences a,b and c,

    \[fgh \ops \left\{\sum_{r+s+t=n} a_r b_s c_t \right\}_{n=0}^\infty\]

Rule 4. Powers of a series. If f \ops \anzi, then for a positive integer k,

    \[ \boxed{ f^k \ops \left\{ \sum_{n_1+n_2+\dotsb+n_k=n} a_{n_1}a_{n_2}\dotsb a_{n_k} \right\}_{n=0}^\infty }\]

Example. Find f(n,k), the number of ways a nonnegative integer n can be written as an ordered sum of k nonnegative integers.
e.g. f(4,2)=5, because 4=4+0=3+1=2+2=1+3=0+4.
Consider the power series 1/(1-x)^k. Since 1/(1-x) \ops \{1\}, by Rule 4 we have

    \[ 1/(1-x)^k \ops \{ f(n,k)\}_{n=0}^\infty\]

Since \sum_k \binom{n}{k} x^k =(1+x)^n, f(n,k)=\binom{n+k-1}{n}.

If f \ops \anzi, what sequence does \dfrac{f(x)}{1-x} generate?

    \begin{align*} \frac{f(x)}{1-x}&=(a_0+a_1x+a_2x^2+\dotsb)(1+x+x^2+\dotsb)\\ &=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+(a_0+a_1+a_2+a_3)x^3+\dotsb \end{align*}

Rule 5. Dividing by 1-x. If f \ops \anzi then

    \[ \boxed{\frac{f}{1-x} \ops \left\{ \sum_{j=0}^n a_j\right\}_{n \ges 0}} \]

i.e. dividing by 1-x replaces the generated sequence by the sequence of its partial sums.


Concrete Mathematics – Knuth, Graham, Patashnik, 2nd Ed., Ch. 7
generatingfunctionology – Herbert Wilf – read online

Leave a Reply

Your email address will not be published. Required fields are marked *