c7.tex.bak

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

this is the equation called for in Step 1.

Step 2 now asks us to transform the equation for $\<g_n\>$
into an equation for $G(z)=\sum_ng_nz^n$. The task is not difficult:
\begindisplay \openup3pt
G(z)=\sum_ng_nz^n
&=\sum_ng_{n-1}\,z^n+\sum_ng_{n-2}\,z^n+\sum_n\[n=1]z^n\cr
&=\sum_ng_n\,z^{n+1}+\sum_ng_n\,z^{n+2}\;+\;z\cr
&=z@ G(z)+z^2G(z)+z\,.\cr
\enddisplay
Step 3 is also simple in this case; we have
\begindisplay
G(z)={z\over1-z-z^2}\,,
\enddisplay
which of course comes as no surprise.

Step 4 is the clincher. We carried it out in Chapter~6 by having a
sudden flash of inspiration; let's go more slowly now, so that we can
get through Step~4 safely later, when we meet problems that are
more difficult. What is
\begindisplay
[z^n]\,{z\over 1-z-z^2}\,,
\enddisplay
the coefficient of
$z^n$ when $z/(1-z-z^2)$ is expanded in a power series? More generally,
if we are given any "rational function"
\begindisplay
R(z)={P(z)\over Q(z)}\,,
\enddisplay
 where $P$ and~$Q$
are polynomials, what is the coefficient $[z^n]\,R(z)$?

There's one kind of rational function whose coefficients are particularly nice,
namely
\begindisplay
{a\over(1-\rho z)^{m+1}}=\sum_{n\ge0}{m+n\choose m}a\rho^nz^n\,.
\eqno
\enddisplay
(The case $\rho=1$ appears in Table~|gf-simp|, and we can get the general
formula shown here by substituting $\rho z$ for~$z$.) A finite sum of functions
like \thiseq,
\begindisplay
S(z)=
{a_1\over(1-\rho_1z)^{m_1+1}}+
{a_2\over(1-\rho_2z)^{m_2+1}}+\cdots+
{a_l\over(1-\rho_lz)^{m_l+1}}\,,
\eqno\eqref|s-parts|
\enddisplay
also has nice coefficients,
\begindisplay
[z^n]\,S(z)&=
a_1{m_1+n\choose m_1}\rho_1^n+
a_2{m_2+n\choose m_2}\rho_2^n\cr
&\hskip12em+\cdots+
a_l{m_l+n\choose m_l}\rho_l^n\,.
\eqno
\enddisplay
We will show that every rational function $R(z)$ such that $R(0)\ne\infty$
can be expressed in the form
\begindisplay
R(z)=S(z)+T(z)\,,
\eqno\eqref|r-s-t|
\enddisplay
where $S(z)$ has the form \eq(|s-parts|) and $T(z)$ is a polynomial.
Therefore there is a closed form for the coefficients $[z^n]\,R(z)$.
Finding $S(z)$ and~$T(z)$ is equivalent to finding the
``"partial fraction expansion"'' of~$R(z)$.

Notice that $S(z)=\infty$ when $z$ has the values $1/\rho_1$,
\dots,~$1/\rho_l$. Therefore the numbers $\rho_k$ that we need to find,
if we're going to succeed in expressing $R(z)$ in the desired form
$S(z)+T(z)$, must be the reciprocals of the numbers $\alpha_k$ where
$Q(\alpha_k)=0$. (Recall that $R(z)=P(z)/Q(z)$, where $P$ and~$Q$ are
polynomials; we have $R(z)=\infty$ only if $Q(z)=0$.)

Suppose $Q(z)$ has the form
\begindisplay
Q(z)=q_0+q_1z+\cdots+q_mz^m\,,\qquad\hbox{where $q_0\ne0$ and $q_m\ne0$.}
\enddisplay
The ``reflected'' polynomial "!reflected polynomial"
\begindisplay
Q^{\rm R}(z)=q_0z^m+q_1z^{m-1}+\cdots+q_m
\enddisplay
has an important relation to $Q(z)$:
\begindisplay
&Q^{\rm R}(z)=q_0(z-\rho_1)\ldots(z-\rho_m)\cr
&\qquad\iff
 Q(z)=q_0(1-\rho_1z)\ldots(1-\rho_mz)\,.
\enddisplay
Thus, the roots of $Q^{\rm R}$ are the reciprocals of the roots of~$Q$,
and vice versa. We can therefore
find the numbers $\rho_k$ we seek by factoring
the reflected polynomial $Q^{\rm R}(z)$.

For example, in the Fibonacci case we have
\begindisplay
Q(z)=1-z-z^2\,;\qquad Q^{\rm R}(z)=z^2-z-1\,.
\enddisplay
The roots of $Q^{\rm R}$ can be found by setting $(a,b,c)=(1,-1,-1)$
in the quad\-ratic formula $\bigl(-b\pm\mskip-1mu
 \sqrt{\,b^{\mathstrut2}-4ac}\,\bigr)
/2a$; we find that they are
\begindisplay \postdisplaypenalty=10000
\phi={1+\sqrt5\over2}\And \phihat={1-\sqrt5\over2}\,.
\enddisplay
Therefore $Q^{\rm R}(z)=(z-\phi)(z-\phihat)$ and $Q(z)=(1-\phi z)(1-\phihat z)$.

Once we've found the $\rho$'s, we can proceed to find the partial fraction
expansion. It's simplest if all the roots are distinct, so let's consider that
special case first. We might as well state and prove the general result
formally:

\subhead Rational Expansion Theorem for Distinct Roots.

{\sl If\/ $R(z)=P(z)/Q(z)$, where $Q(z)=q_0(1-\rho_1z)\ldots(1-\rho_l z)$
and the numbers $(\rho_1,\ldots,\rho_l)$ are distinct, and if\/ $P(z)$
is a polynomial of degree less than~$l$, then}
\begindisplay
[z^n]\,R(z)=a_1\rho_1^n+\cdots+a_l\rho_l^n\,,\qquad
\hbox{where \ $a_k=\displaystyle{-\rho_k P(1/\rho_k)\over Q'(1/\rho_k)}$}.
\eqno\eqref|rat-distinct|
\enddisplay
Proof: Let $a_1$, \dots, $a_l$ be the stated constants. Formula \thiseq\
holds if $R(z)=P(z)/Q(z)$ is equal to
\begindisplay
S(z)={a_1\over1-\rho_1z}+\cdots+{a_l\over1-\rho_lz}\,.
\enddisplay
And we can prove that $R(z)=S(z)$ by showing that the function
$T(z)=R(z)-S(z)$ is not
\g Impress your parents by leaving the book open at this page.\g
infinite as $z\to1/\rho_k$. For this will show that the rational function~$T(z)$
is never infinite; hence $T(z)$ must be a polynomial. We also can show that
$T(z)\to0$ as $z\to\infty$; hence $T(z)$~must
be zero.

Let $\alpha_k=1/\rho_k$. To prove that $\lim_{z\to\alpha_k}T(z)\ne\infty$,
it suffices to show that $\lim_{z\to\alpha_k}\,(z-\alpha_k)T(z)=0$,
because $T(z)$ is a rational function of $z$.
Thus we want to show that
\begindisplay
\lim_{z\to\alpha_k}\,(z-\alpha_k)R(z)
=\lim_{z\to\alpha_k}\,(z-\alpha_k)S(z)\,.
\enddisplay
The right-hand limit equals
$\lim_{z\to\alpha_k}a_k(z-\alpha_k)/(1-\rho_kz)=-a_k/\rho_k$, because
$(1-\rho_kz)=-\rho_k(z-\alpha_k)$ and $(z-\alpha_k)/(1-\rho_jz)\to0$
for $j\ne k$. The left-hand limit is
\begindisplay
\lim_{z\to\alpha_k}\,(z-\alpha_k){P(z)\over Q(z)}=P(\alpha_k)\lim_{z\to\alpha_k}
{z-\alpha_k\over Q(z)}={P(\alpha_k)\over Q'(\alpha_k)}\,,
\enddisplay
by L'Hospital's rule. Thus the theorem is proved.

Returning to the Fibonacci example,
we have $P(z)=z$ and $Q(z)=1-z-z^2=(1-\phi z)(1-\phihat z)$;
hence $Q'(z)=-1-2z$, and
\begindisplay
{-\rho P(1/\rho)\over Q'(1/\rho)}={-1\over-1-2/\rho}={\rho\over\rho+2}\,.
\enddisplay
According to \eq(|rat-distinct|),
the coefficient of $\phi^n$ in $[z^n]\,R(z)$ is therefore $\phi/(\phi+2)=
1/\!\sqrt5@$; the coefficient of $\phihat^n$ is
$\phihat/(\phihat+2)=-1/\!\sqrt5$. So the theorem
tells us that $F_n=(\phi^n-\phihat^n)/\mskip-1mu
\sqrt5$, as in \equ(6.|fib-sol|).

When $Q(z)$ has repeated roots, the calculations become more difficult,
but we can beef up the proof of the theorem and prove the following
more general result:

\subhead General Expansion Theorem for Rational Generating Functions.

{\sl If\/ $R(z)=P(z)/Q(z)$, where\/ $Q(z)=q_0(1-\rho_1z)^{d_1}\ldots
(1-\rho_lz)^{d_l}$ and the numbers\/ $(\rho_1,\ldots,\rho_l)$ are
distinct, and if\/ $P(z)$ is a polynomial of degree less than\/
$d_1+\cdots+d_l$, then
\begindisplay
[z^n]\,R(z)=f_1(n)\rho_1^n\,+\,\cdots\,+\,f_l(n)\rho_l^n
\qquad\hbox{\rm for all $n\ge0$},
\eqno\eqref|gen-exp-thm|
\enddisplay
where each\/ $f_k(n)$ is a polynomial of degree\/ $d_k-1$ with
leading coefficient}
\begindisplay \tightplus \openup3pt
a_k&={(-\rho_k)^{d_k}P(1/\rho_k)d_k\over Q^{(d_k)}(1/\rho_k)}\cr
&={P(1/\rho_k)\over (d_k-1)!\,q_0\prod_{j\ne k}(1-\rho_j/\rho_k)^{d_j}}\,.
\eqno\eqref|gen-exp-a|
\enddisplay
This can be proved by induction on $\max(d_1,\ldots,d_l)$, using the fact that
\begindisplay
R(z)-{a_1(d_1-1)!\over(1-\rho_1z)^{d_1}}
-\cdots-{a_l(d_l-1)!\over(1-\rho_lz)^{d_l}}
\enddisplay
is a rational function whose denominator polynomial
is not divisible by\break ${(1-\rho_kz)^{d_k}}$ for any~$k$.

\subhead Example 2: A more-or-less random recurrence.

Now that we've seen some general methods, we're ready to tackle new problems.
Let's try to find a closed form for the recurrence
\begindisplay
g_0&=g_1=1\,;\cr
g_n&=g_{n-1}+2g_{n-2}+(-1)^n\,,\qquad\hbox{for $n\ge2$}.
\eqno\eqref|more-less-random|
\enddisplay
It's always a good idea to make a table of small cases first, and the
recurrence lets us do that easily:
\begindisplay \let\preamble=\tablepreamble
n&&0&1&2&3&4&5&6&7\cr
\noalign{\hrule}
(-1)^n&&1&-1&1&-1&1&-1&1&-1\cr
\noalign{\hrule}
g_n&&1&1&4&5&14&23&52&97\cr
\enddisplay
No closed form is evident, and this sequence isn't even listed in
"Sloane"'s {\sl Handbook\/}~[|sloane|];
so we need to go through the four-step process if we want to discover the solution.

Step 1 is easy, since we merely need to insert fudge factors to fix
things when $n<2$: The equation
\begindisplay
g_n=g_{n-1}+2g_{n-2}+(-1)^n\[n\ge0]+\[n=1]
\enddisplay
holds for all integers $n$. Now we can carry out Step 2:
\g\vskip30pt N.B.: The upper index on $\sum_{n=1}z^n$ is not missing!\g
\begindisplay
G(z)=\sum_ng_nz^n&=\!\sum_ng_{n-1}z^n+2\sum_ng_{n-2}z^n+\!\sum_{n\ge0}(-1)^nz^n
+\!\sum_{n=1}z^n\cr
&=zG(z)+2z^2G(z)+{1\over1+z}+z\,.\cr
\enddisplay
(Incidentally, we could also have used $-1\choose n$ instead of $(-1)^n\[n\ge0]$,
thereby getting $\sum_n{-1\choose n}z^n=(1+z)^{-1}$ by the binomial theorem.)
Step~3 is elementary algebra, which yields
\begindisplay
G(z)={1+z(1+z)\over(1+z)(1-z-2z^2)}={1+z+z^2\over(1-2z)(1+z)^2}\,.
\enddisplay
And that leaves us with Step 4.

The squared factor in the denominator is a bit troublesome,
since we know that repeated roots are more complicated than distinct roots;
but there it is.
We have two roots, $\rho_1=2$ and $\rho_2=-1$; the general expansion theorem
\eq(|gen-exp-thm|) tells us that
\begindisplay
g_n=a_12^n+(a_2n+c)(-1)^n
\enddisplay
for some constant~$c$, where
\begindisplay
a_1={1+1/2+1/4\over(1+1/2)^2}={7\over9}\,;\qquad
a_2={1-1+1\over1-2/(-1)}={1\over3}\,.
\enddisplay
(The second formula for $a_k$ in \eq(|gen-exp-a|) is easier to use than the
first one when the denominator has nice factors. We simply substitute
$z=1/\rho_k$ everywhere in $R(z)$, except in the factor where this gives zero,
and divide by $(d_k-1)!$; this gives the coefficient of $n^{d_k-1}\rho_k^n$.)
Plugging in $n=0$ tells us that the value of the remaining constant~$c$ had better
be $2\over9$; hence our answer is
\begindisplay
g_n=\textstyle{7\over9}2^n+\Bigl({1\over3}n+{2\over9}\Bigr)(-1)^n\,.
\eqno
\enddisplay
It doesn't hurt to check the cases $n=1$ and $2$, just to be sure that we didn't
foul up. Maybe we should even try $n=3$, since this formula looks weird.
But it's correct, all right.

Could we have discovered \thiseq\ by guesswork? Perhaps after tabulating a
few more values we may have observed that $g_{n+1}\approx2g_n$ when $n$~is
large. And with chutzpah and luck we might even have been able to smoke out
the constant $7\over9$. But it sure is simpler and more reliable to have
generating functions as a tool.

\subhead Example 3: Mutually recursive sequences.

Sometimes we have two or more recurrences that depend on each other.
Then we can form generating functions for both of them, and solve both
by a simple extension of our four-step method.

For example, let's return to the problem of $3\times n$ domino tilings
that we explored earlier this chapter. If we want to know only the total
number of ways, $U_n$, to cover a $3\times n$ rectangle with dominoes,
without breaking this number down into vertical dominoes versus
horizontal dominoes, we needn't go into as much detail as we did before.
We can merely set up the recurrences
\begindisplay \def\preamble{&\hfill$##$&${}##$\hfill\qquad}
U_0&=1\,,\qquad U_1=0\,;&V_0&=0\,,\qquad V_1=1\,;\cr
U_n&=2V_{n-1}+U_{n-2}\,,&V_n&=U_{n-1}+V_{n-2}\,,
\qquad\hbox{for $n\ge2$}.\cr
\enddisplay
Here $V_n$ is the number of ways to cover a $3\times n$ rectangle-minus-corner,
using $(3n-1)/2$ dominoes. These recurrences are easy to discover, if we
consider the possible domino configurations at the rectangle's
left edge, as before. Here are
the values of $U_n$ and $V_n$ for small~$n$:
"!Seaver, George Thomas"
\begindisplay \let\preamble=\tablepreamble
n&&0&1&2&3&4&5&6&7\cr
\noalign{\hrule}
U_n&&1&0&3&0&11&0&41&0\eqno\eqref|u-v-table|\cr
\noalign{\hrule}
V_n&&0&1&0&4&0&15&0&56\cr
\enddisplay

Let's find closed forms, in four steps.
First (Step~1), we have
\begindisplay
U_n=2V_{n-1}+U_{n-2}+\[n=0]\,,\qquad
V_n=U_{n-1}+V_{n-2}\,,
\enddisplay
for all $n$. Hence (Step~2),
\begindisplay
U(z)=2zV(z)+z^2U(z)+1\,,\,\qquad V(z)=zU(z)+z^2V(z)\,.
\enddisplay
Now (Step 3) we must solve two equations in two unknowns; but these are
easy, since the second equation yields $V(z)=zU(z)/(1-z^2)$; we find
\begindisplay
U(z)={1-z^2\over1-4