c7.tex.bak

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

Shifting a generating function isn't much harder.
To shift~$G(z)$ right by $m$~places, that is,
to form the generating function for the sequence
$\<0,\ldots, 0,\allowbreak g_0,g_1,\ldots\,\>=\<g_{n-m}\>$
with $m$~leading $0$'s,
we simply multiply by~$z^m$:
\begindisplay \advance\belowdisplayskip-3pt
z^m G(z)
	= \sum_n g_n\, z^{n+m}
	= \sum_n g_{n-m}\, z^n \,,
\qquad\hbox{integer $m\ge0$}.
\eqno\eqref|gf-shift-up|
\enddisplay
This is the operation we used (twice), along with addition,
to deduce the equation $(1 - z - z^2) F(z) = z$
on our way to finding a closed form for the Fibonacci numbers
in Chapter~6.

And to shift~$G(z)$ left $m$~places\dash---that is,
to form the generating function for the sequence
$\<g_m,g_{m+1},g_{m+2},\ldots\,\>=\<g_{n+m}\>$ with the first
$m$ elements discarded\dash---
we subtract off the first~$m$ terms
and then divide by~$z^m$:
\begindisplay \postdisplaypenalty=10000 \advance\belowdisplayskip-1pt
{G(z){-}g_0{-}g_1 z{-}\cdots{-}g_{m-1} z^{m-1}\over z^m}
	= \sum_{n \geq m} g_n z^{n-m}
	= \sum_{n \geq 0} g_{n+m} z^n.
\eqno
\enddisplay
(We can't extend this last sum over all~$n$ unless $g_0=\cdots=g_{m-1}=0$.)

Replacing the $z$ by a constant multiple
is another of our tricks:
\begindisplay \advance\belowdisplayskip-3pt
G(cz)
	= \sum_n g_n (cz)^n
	= \sum_n c^n g_n z^n \,;
\eqno
\enddisplay
this yields the generating function for
the sequence $\<c^n g_n\>$.
The special case $c = -1$ is particularly useful.

Often we want to bring down a factor of~$n$ into
\g I fear $d$generating-function $dz$'s.\g "!disease"
 the coefficient.
Differentiation is what lets us do that:
\begindisplay \advance\belowdisplayskip-3pt
G'(z)
	= g_1 + 2 g_2 z + 3 g_3 z^2 + \cdots
	= \sum_n (n+1) g_{n+1}\,z^n \,.
\eqno\eqref|gf-deriv|
\enddisplay
Shifting this right one place gives us a form
that's sometimes more useful,
\begindisplay \advance\belowdisplayskip-3pt
z G'(z)
	= \sum_n n g_n\,z^n \,.
\eqno
\enddisplay
This is the generating function for
the sequence $\<n g_n\>$. Repeated differentiation would allow us to multiply
$g_n$ by any desired polynomial in~$n$.

Integration, the inverse operation,
lets us divide the terms by~$n$:
\begindisplay
\int_0^z \! G(t) \, dt
	= g_0 z + {1\over 2} g_1 z^2 + {1\over 3} g_2 z^3 + \cdots
	= \sum_{n \geq 1} {1\over n} g_{n-1}\, z^n\,.
\eqno
\enddisplay
(Notice that the constant term is zero.) If we want the generating
function for $\<g_n/n\>$ instead of $\<g_{n-1}/n\>$,
we should first shift left one place, replacing $G(t)$ by $\bigl(G(t)-g_0\bigr)/t$
in the integral.

Finally, here's how we multiply generating functions together:
\begindisplay
F(z)@G(z)
	&= (f_0 + f_1 z + f_2 z^2 + \cdots\,)
			(g_0 + g_1 z + g_2 z^2 + \cdots\,) \cr
\noalign{\smallskip}
	&= (f_0 g_0) \,+\, (f_0 g_1 + f_1 g_0) z
					\,+\, (f_0 g_2 + f_1 g_1 + f_2 g_0) z^2
						\,+\, \cdots \cr
\noalign{\smallskip}
	&= \sum_n \Bigl( \sum_k f_k@g_{n-k} \Bigr) z^n \,.
\eqno
\enddisplay
As we observed in Chapter~5,
this gives the generating function for the sequence
$\<h_n\>$, the {\it"convolution"\/} of $\<f_n\>$
and~$\<g_n\>$. The sum
$h_n=\sum_k f_k g_{n-k}$ can also be written $h_n=\sum_{k=0}^n f_k g_{n-k}$,
because $f_k=0$ when $k<0$ and $g_{n-k}=0$ when $k>n$.
Multiplication/convolution is a little more complicated than the other operations,
but it's very useful\dash---%
so useful that we will spend all of Section~7.5 below
looking at examples of it.

Multiplication has several special cases that are worth
considering as operations in themselves.
We've already seen one of these:
When $F(z) = z^m$ we get
the shifting operation~\eq(|gf-shift-up|).
In that case the sum~$h_n$ becomes the single term~$g_{n-m}$,
because all $f_k$'s are~$0$ except for $f_m = 1$.

Another useful special case arises when $F(z)$ is the
familiar function ${1/(1-z)} = 1 + z + z^2 + \cdots\,$; then
all $f_k$'s (for $k \geq 0$) are~$1$
and we have the important formula
\begindisplay
{1\over 1-z} G(z)
	= \sum_n \biggl( \sum_{k\ge0} g_{n-k} \biggr) z^n 
	= \sum_n \biggl( \sum_{k\le n} g_k \biggr) z^n \,.
\eqno\eqref|gf-cum-sum|
\enddisplay
Multiplying a generating function by $1/(1-z)$
gives us the generating function for the cumulative sums
of the original sequence.

\topinsert
\table Generating function manipulations.\tabref|gf-manip|
\begindisplay\abovedisplayskip=-2pt \belowdisplayskip=6pt \openup7pt%
 \advance\displayindent-\parindent\advance\displaywidth\parindent
\alpha F(z) + \beta G(z)
 &= \sum_n (\alpha f_n + \beta g_n) z^n\cr
z^m G(z)
 &= \sum_n g_{n-m} \,z^n\,,\qquad\hbox{integer $m\ge0$}\cr
{G(z) - g_0 - g_1 z - \cdots - g_{m-1} z^{m-1}\over z^m}
 &= \sum_{n \geq 0} g_{n+m} \,z^n\,,\qquad\hbox{integer $m\ge0$}\cr
G(cz)
 &= \sum_n c^n g_n \,z^n \cr
G'(z)
 &= \sum_n (n+1) g_{n+1} \,z^n\cr
z G'(z)
 &= \sum_n n g_n \,z^n \cr
\int_0^z G(t) \, dt
 &= \sum_{n \geq 1} {1\over n} g_{n-1} \,z^n\cr
F(z)@G(z)
 &= \sum_n \biggl( \sum_k f_k g_{n-k} \biggr) z^n \cr
{1\over 1-z} G(z)
 &= \sum_n \biggl( \sum_{k\le n} g_k \biggr) z^n \cr
\enddisplay
\hrule width\hsize height.5pt
\kern4pt
\endinsert

\topinsert
\table Simple sequences and their generating functions.\tabref|gf-simp|
\kern3pt\openup5pt
\halign to\hsize{$\left\<#,\ldots\,\right\>\hfil$%
 \tabskip=2em plus 100pt&
 $\displaystyle\sum\nolimits_{n\ge0}#\,z^n\hfil$&
 $\displaystyle#\hfil$\tabskip=0pt\cr
\omit\strut sequence\hfil&\omit generating function\hfil&\omit closed form\hfil\cr
\noalign{\hrule width\hsize\kern5pt}
1,0,0,0,0,0&\[n=0]&1\cr
0,\ldots,0,1,0,0&\[n=m]&z^m\cr
1,1,1,1,1,1&&{1\over1-z}\cr
1,-1,1,-1,1,-1&(-1)^n&{1\over1+z}\cr
1,0,1,0,1,0&\[2\divides n]&{1\over 1-z^2}\cr
1,0,\ldots,0,1,0,\ldots,0,1,0&\[m\divides n]&{1\over 1-z^m}\cr
1,2,3,4,5,6&(n+1)&{1\over(1-z)^2}\cr
1,2,4,8,16,32&2^n&{1\over1-2z}\cr
1,4,6,4,1,0,0&{4\choose n}&(1+z)^4\cr
1,c,{c\choose2},{c\choose3}&{c\choose n}&(1+z)^c\cr
1,c,{c+1\choose2},{c+\2\choose 3}&{c{+}n{-}1\choose n}&{1\over(1-z)^c}\cr
1,c,c^2,c^3&c^n&{1\over1-cz}\cr
1,{m+1\choose m},{m+\2\choose m},{m+3\choose m}&{m{+}n\choose m}&{1\over(1-z)^{m+1}}\cr
0,1,{1\over2},{1\over3},{1\over4}&
 \omit$\displaystyle\sum\nolimits_{n\ge1}{1\over n}\,z^n\hfil$&
 \ln{1\over1-z}\cr
0,1,-{1\over2},{1\over3},-{1\over4}&
 \omit$\displaystyle\sum\nolimits_{n\ge1}{(-1)^{n+1}\over n}\,z^n\hfil$&
 \ln(1+z)\cr
1,1,{1\over2},{1\over6},{1\over24},{1\over120}&{1\over n!}&e^z\cr}
\kern6pt
\hrule width\hsize height.5pt
\kern1pt
\endinsert

Table |gf-manip| summarizes the operations we've discussed so far.
To use all these manipulations effectively
it helps to have a healthy repertoire
of generating functions in stock.
Table~|gf-simp| lists the simplest ones; we can use those to get started
and to solve quite a few problems.

Each of the generating functions in Table |gf-simp| is important enough
to be memorized. Many of them are special cases of the others, and many
of them can be derived quickly from the others by using the basic operations
\g\vskip-27pt Hint: If the sequence consists of binomial coefficients,
its generating function usually involves a binomial, $1\pm z$.\g
of Table~|gf-manip|; therefore the memory work isn't very hard.

For example, let's consider the sequence $\<1,2,3,4,\ldots\,\>$,
whose generating function $1/(1-z)^2$ is often useful. This
generating function
appears near the middle of Table~|gf-simp|, and it's also the special
case $m=1$ of $\<1,{m+1\choose m},\allowbreak{m+\2\choose m},\allowbreak
{m+3\choose m},\ldots\,\>$, which appears further down;
it's also the special case $c=2$ of the closely related
sequence $\<1,c,{c+1\choose2},{c+\2\choose3},
\ldots\,\>$. We can derive it from the generating function for
$\<1,1,1,1,\ldots\,\>$ by taking cumulative sums
as in \eq(|gf-cum-sum|); that is, by
dividing $1/(1-z)$ by $(1-z)$. Or we can derive it from
\g OK, OK, I'm convinced already.\g
$\<1,1,1,1,\ldots\,\>$ by differentiation, using \eq(|gf-deriv|).

The sequence $\<1,0,1,0,\ldots\,\>$ is another one whose generating
function can be obtained in many ways. We can obviously derive the
formula $\sum_nz^{2n}=1/(1-z^2)$ by substituting $z^2$ for $z$ in the
identity $\sum_nz^n=1/(1-z)$; we can also apply cumulative summation
to the sequence $\<1,-1,1,-1,\ldots\,\>$, whose generating function
is $1/(1+z)$, getting $1/(1+z)(1-z)=1/(1-z^2)$. And there's also a third
way, which is based on a general method for extracting the even-numbered
terms $\<g_0,0,g_2,0,g_4,0,\ldots\,\>$ of {\it any\/} given sequence:
If we add $G(-z)$ to $G(+z)$ we get
\begindisplay
G(z)+G(-z)=\sum_ng_n\bigl(1+(-1)^n\bigr)z^n=2\sum_n g_n\[\hbox{$n$ even}]z^n\,;
\enddisplay
therefore
\begindisplay
{G(z)+G(-z)\over2}=\sum_n g_{2n}\,z^{2n}\,.
\eqno\eqref|gf-even|
\enddisplay
The odd-numbered terms can be extracted in a similar way,
\begindisplay
{G(z)-G(-z)\over2}=\sum_n g_{2n+1}\,z^{2n+1}\,.
\eqno\eqref|gf-odd|
\enddisplay
In the special case where $g_n=1$ and $G(z)=1/(1-z)$, the generating function
for $\<1,0,1,0,\ldots\,\>$ is $\half\bigl(G(z)+G(-z)\bigr)=
\half\bigl({1\over1-z}+{1\over1+z}\bigr)={1\over1-z^{2\mathstrut}}$.

Let's try this extraction trick on the generating function for Fibonacci
numbers. We know that $\sum_nF_nz^n=z/(1-z-z^2)$; hence
\begindisplay
\sum_nF_{2n}z^{2n}&=\half\biggl({z\over1-z-z^2}+{-z\over1+z-z^2}\biggr)\cr
&=\half\biggl({z+z^2-z^3-z+z^2+z^3\over(1-z^2)^2-z^2}\biggr)
={z^2\over1-3z^2+z^4}\,.
\enddisplay
This generates the sequence $\<F_0,0,F_2,0,F_4,\ldots\,\>$; hence
the sequence of alternate $F$'s, $\advance\thinmuskip0mu minus 1mu
\<F_0,F_2,F_4,F_6,\ldots\,\>=\<0,1,3,8,\ldots\,\>$,
has a simple generating function:
\begindisplay
\sum_n F_{2n}z^n={z\over1-3z+z^2}\,.
\eqno\eqref|fib-gf-even|
\enddisplay

\beginsection 7.3 Solving Recurrences

Now let's focus our attention on one of the most important uses of generating
functions: the "solution" of "recurrence" relations.

Given a sequence $\<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 that are almost mechanical
enough to be programmed on a computer:

\nobreak\smallskip
\item{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}=\cdots=0$.

\smallbreak
\item{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_nz^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)$.

\smallbreak
\item{3} Solve the resulting equation, getting a closed form for~$G(z)$.

\smallbreak
\item{4} Expand $G(z)$ into a power series and read off the coefficient
of~$z^n$; this is a closed form for~$g_n$.

\nobreak\smallskip\noindent
This method works because the single function $G(z)$ represents the entire
sequence $\<g_n\>$ in such a way that many manipulations
are possible.

\subhead Example 1: Fibonacci numbers revisited.

For example, let's rerun the derivation of Fibonacci numbers from Chapter~6.
"!Fibonacci numbers, generating function"
In that chapter we were feeling our way, learning a new method; now we
can be more systematic. The given recurrence is
\begindisplay
g_0&=0\,;\qquad g_1=1\,;\cr
g_n&=g_{n-1}+g_{n-2}\,,\qquad\hbox{for $n\ge2$}.
\enddisplay
We will find a closed form for $g_n$ by using the four steps above.

Step 1 tells us to write the recurrence as a ``single equation'' for~$g_n$.
We could say
\begindisplay
g_n=\cases{0,&if $n\le0@$;\cr 1,&if $n=1$;\cr
 g_{n-1}+g_{n-2},&if $n>1$;\cr}
\enddisplay
but this is cheating. Step 1 really asks for a formula that doesn't
involve a case-by-case construction. The single equation
\begindisplay
g_n=g_{n-1}+g_{n-2}
\enddisplay
works for $n\ge2$, and it also holds when $n\le0$ (because we have $g_0=0$
and $g_{\rm negative}=0$). But when $n=1$ we get $1$~on the left
and $0$~on the right. Fortunately the problem is easy to fix, since
we can add $\[n=1]$ to the right; this adds~$1$ when $n=1$, and it makes
no change when $n\ne1$. So, we have
\begindisplay
g_n=g_{n-1}+g_{n-2}+\[n=1]\,;
\enddisplay