chap6.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\begindisplay
\Sscr_t(z)^x=x\sum_{n\ge0}\sigma_n(x+tn)\,z^n\,.
\eqno
\enddisplay
Therefore we can obtain general "convolution formulas" for Stirling
"!Stirling numbers, convolutions"
numbers, as we did for binomial coefficients in Table~|conv-table|;
the results appear in Table~|stirling-convolutions|.
When a sum of Stirling numbers doesn't
fit the identities of Table |stirling-id1| or~|stirling-id2|,
Table~|stirling-convolutions| may be just the ticket. (An example appears
later in this chapter, following equation \eq(|stirl-bern|).
Exercise 7.|general-conv-principles| discusses the
general principles of convolutions based on identities like 
\eq(|stirl-poly-gf|) and \thiseq.)

\beginsection 6.3 Harmonic Numbers

It's time now to take a closer look at "harmonic numbers", which we first met
back in Chapter~2:
\begindisplay
H_n=1+{1\over2}+{1\over3}+\cdots+{1\over n}=\sum_{k=1}^n{1\over k}\,,
\quad\hbox{integer $n\ge0$}.
\eqno
\enddisplay
These numbers appear
so often in the analysis of algorithms that computer
scientists need a special notation for them. We use $H_n$, the `$H$' standing
for ``harmonic,\qback'' since a tone of wavelength $1/n$ is called the
$n$th harmonic of a tone whose wavelength is~$1$. The first few values
look like this:
\begindisplay \let\preamble=\tablepreamble \let\strut=\bigstrut%
 \postdisplaypenalty=10000
n&&0&1&2&3&4&5&6&7&8&9&10\cr
\noalign{\hrule}
H_n&&0&1&{3\over2}&{11\over6}&{25\over12}&{137\over60}&{49\over20}&{363\over140}
&{761\over280}&{7129\over2520}&{7381\over2520}\cr
\enddisplay
%The numerators and denominators don't obey any especially
% memorable patterns, so it is pointless to list further values.
Exercise~|prove-h-not-int| shows that $H_n$ is never an integer when $n>1$.

Here's a card trick, based on an idea by R.\thinspace T. Sharp~[|sharp-stack|],
that illustrates how the harmonic numbers arise naturally
in simple situations. Given $n$ cards and a table, we'd like to create
"!card stacking" "!stacking cards"
the largest possible overhang by stacking the cards up over the table's
edge, subject to the laws of "gravity":
\g\vskip.5in \tabref|table-joke| This must be \-Table~|table-joke|.\g
\begindisplay
\unitlength=4pt
\beginpicture(70,18)(-73,-5)
 \put(0,10){\line(-1,0){20.5}}
\put(0,10){\line(0,-1)1}
 \put(0,9){\line(-1,0){30.5}}
\put(-20.5,10){\line(0,-1)1}
  \put(-26.5,11.5){\vector(4,-1)5}
  \put(-30,13){\makebox(0,0){card $1$}}
\put(-10,9){\line(0,-1)1}
 \put(-10,8){\line(-1,0){25.5}}
\put(-30.5,9){\line(0,-1)1}
  \put(-36.5,10.5){\vector(4,-1)5}
  \put(-40,12){\makebox(0,0){card $2$}}
\put(-15,8){\line(0,-1)1}
 \put(-15,7){\line(-1,0){23.833}}
\put(-35.5,8){\line(0,-1)1}
\put(-18.333,7){\line(0,-1)1}
 \put(-18.333,6){\line(-1,0){23.000}}
\put(-38.833,7){\line(0,-1)1}
\put(-20.833,6){\line(0,-1)1}
 \put(-20.833,5){\line(-1,0){22.500}}
\put(-41.333,6){\line(0,-1)1}
\put(-22.833,5){\line(0,-1)1}
 \put(-22.833,4){\line(-1,0){22.167}}
\put(-43.333,5){\line(0,-1)1}
\put(-24.500,4){\line(0,-1)1}
 \put(-24.500,3){\line(-1,0){21.929}}
\put(-45.000,4){\line(0,-1)1}
\put(-25.929,3){\line(0,-1)1}
 \put(-25.929,2){\line(-1,0){21.750}}
\put(-46.429,3){\line(0,-1)1}
\put(-27.179,2){\line(0,-1)1}
 \put(-27.179,1){\line(-1,0){21.611}}
\put(-47.679,2){\line(0,-1)1}
\put(-28.290,1){\line(0,-1)1}
 \put(-28.290,0){\line(-1,0){44.710}}
\put(-48.790,1){\line(0,-1)1}
  \put(-54.790,2.5){\vector(4,-1)5}
  \put(-59.790,3){\makebox(0,0){card $n$}}
\put(-29.290,0){\line(0,-1)6}
\put(0,8){\line(0,-1){12}}
\put(-10,7){\line(0,-1){3}}
\put(-15,6){\line(0,-1){5}}
\put(-7,6){\vector(-1,0)3} \put(-3,6){\vector(+1,0)3}
\put(-5,6){\makebox(0,0){$\mathstrut d_2$}}
\put(-9.5,3){\vector(-1,0){5.5}} \put(-5.5,3){\vector(+1,0){5.5}}
\put(-7.5,3){\makebox(0,0){$\mathstrut d_3$}}
\put(-18.645,-2){\vector(-1,0){10.645}}
\put(-11.045,-2){\vector(+1,0){11.045}}
\put(-14.645,-2){\makebox(0,0){$\mathstrut d_{n+1}$}}
\put(-50,-4){\makebox(0,0){table}}
\endpicture
\enddisplay
To define the problem a bit more, we require the
edges of the cards to be parallel to the edge of the table;
otherwise we could increase the overhang by rotating the cards
so that their corners stick out a little farther. And to make the
answer simpler, we assume that each card is $2$~units long.

With one card, we get maximum overhang when its center of gravity
is just above the edge of the table. The center of gravity is in the
middle of the card, so we can create half a cardlength, or $1$~unit,
of overhang.

With two cards, it's not hard to convince ourselves that we get maximum
overhang when the center of gravity of the top card is just above the
edge of the second card, and the center of gravity of both cards
combined is just above the edge of the table. The joint center of
gravity of two cards will be in the middle of their common part,
so we are able to achieve an additional half unit of overhang.

This pattern suggests a general method, where we place cards so that
the center of gravity of the top~$k$ cards lies just above the edge of the
$k+1$st card (which supports those top~$k$). The
table plays the role of the $n+1$st~card. To
express this condition algebraically, we can let $d_k$ be the distance
from the extreme edge of the top card to the corresponding edge
of the $k$th card from the top. Then $d_1=0$, and we want to make
$d_{k+1}$ the center of gravity of the first $k$ cards:
\begindisplay
d_{k+1}={(d_1+1)+(d_2+1)+\cdots+(d_k+1)\over k}\,,\quad\hbox{for $1\le k\le n$}.
\eqno\eqref|card-stack-rec|
\enddisplay
(The center of gravity of $k$ objects, having respective weights $w_1$,
\dots,~$w_k$ and having respective centers of gravity at
positions $p_1$, \dots~$p_k$, is at position $(w_1p_1+\cdots+w_kp_k)/
(w_1+\cdots+w_k)$.) We can rewrite this recurrence in two equivalent forms
\begindisplay
kd_{k+1}&=k+d_1+\cdots+d_{k-1}+d_k\,,\qquad&\hbox{$k\ge0@$};\cr
(k-1)d_k&=k-1+d_1+\cdots+d_{k-1}\,,\qquad&\hbox{$k\ge1$}.\cr
\enddisplay
\setmathsize{(k-1)d_k=k+d_1+\cdots+d_{k-1}+d_k\,,\qquad}%
Subtracting these equations tells us that
\begindisplay
\mathsize{kd_{k+1}-(k-1)d_k=1+d_k\,,}\hbox{$k\ge1$};
\enddisplay
hence $d_{k+1}=d_k+1/k$. The second card will be offset half a unit
past the third, which is a third of a unit past the fourth, and so on.
The general formula
\begindisplay
d_{k+1}=H_k\eqno
\enddisplay
follows by induction, and if we set $k=n$ we get $d_{n+1}=H_n$ as the total
overhang when $n$ cards are stacked as described.

Could we achieve greater overhang by holding back, not pushing each card
to an extreme position but storing up ``potential gravitational
energy'' for a later advance?
No; any well-balanced card placement has
\begindisplay
d_{k+1}\le{(1+d_1)+(1+d_2)+\cdots+(1+d_k)\over k}\,,\qquad\hbox{$1\le k\le n$}.
\enddisplay
Furthermore $d_1=0$.
It follows by induction that $d_{k+1}\le H_k$.

Notice that it doesn't take too many cards for the top one to be completely
past the edge of the table. We need an overhang of more than one cardlength,
which is $2$~units. The first harmonic number to exceed~$2$ is $H_4={25\over12}$,
so we need only four cards.

And with 52 cards we have an $H_{52}$-unit overhang,
\g Anyone who actually tries to achieve this maximum overhang with 52 cards
is probably not dealing with a full deck\dash---%
or maybe he's~a real joker.\g
which turns out to be $H_{52}/2\approx2.27$ cardlengths. (We will soon
learn a formula that tells us how to compute an approximate value of $H_n$
for large~$n$ without adding up a whole bunch of fractions.)

\smallbreak
An amusing problem called the ``"worm" on the "rubber band"'' shows harmonic
numbers in another guise. A slow but persistent worm, $W$, starts at one
end of a meter-long rubber band and crawls one centimeter per minute toward
the other end. At the end of each minute, an equally persistent keeper
of the band, $K$, whose sole purpose in life is to frustrate~$W$,
stretches it one meter.
"!Kafkaesque scenario"
Thus after one minute of crawling, $W$~is $1$~centimeter from the start
and $99$~from the finish; then $K$ stretches it one meter. During the
stretching operation $W$ maintains his relative position, $1$\% from the
start and $99$\% from the finish; so $W$~is now $2\,$cm from the starting
point and $198\,$cm from the goal. After $W$ crawls for
another minute the score is
$3\,$cm traveled and $197$ to go; but $K$ stretches, and the distances
become $4.5$ and $295.5$. And so on. Does the worm ever reach the finish?
\g Metric units make this problem more scientific.\g
He keeps moving, but the goal seems to move away even faster. (We're
assuming an infinite longevity for $K$ and~$W$, an infinite elasticity of
the band, and an infinitely tiny worm.)

Let's write down some formulas. When $K$ stretches the rubber band, the fraction
of it that $W$ has crawled stays the same. Thus he crawls $1/100$th of it
the first minute, $1/200$th the second, $1/300$th the third, and so on.
After $n$~minutes the fraction of the band that he's crawled is
\begindisplay
{1\over100}\biggl({1\over1}+{1\over2}+{1\over3}+\cdots+{1\over n}\biggr)
={H_n\over100}\,.
\eqno\eqref|worm-ratio|
\enddisplay
So he reaches the finish if $H_n$ ever surpasses~$100$.

We'll see how to estimate $H_n$ for large~$n$ soon; for now, let's simply
check our analysis by considering how ``Superworm'' would perform in the
same situation. Superworm, unlike~$W$,
can crawl $50\,$cm per minute; so she will crawl
$H_n/2$ of the band length after $n$~minutes,
according to the argument we just
gave. If our reasoning is correct, Superworm should finish before $n$
reaches~$4$, since $H_4>2$. And yes, a simple calculation shows that
Superworm has only $33{1\over3}\,$cm left to travel after three minutes
have elapsed. She finishes in 3~minutes and 40~seconds flat.
\g A flatworm, eh?\g

Harmonic numbers appear also in Stirling's triangle. Let's try to
find a closed form for $n\brack2$, the number of permutations of
$n$~objects that have exactly two~cycles. Recurrence \eq(|stirl1-rec|)
tells us that
\begindisplay \openup3pt
{n+1\brack2}&=n{n\brack2}+{n\brack1}\cr
&=n{n\brack2}+(n-1)!\,,\qquad\hbox{if $n>0$};\cr
\enddisplay
and this recurrence is a natural candidate for the "summation factor"
technique of Chapter~2:
\begindisplay
{1\over n!}{n+1\brack 2}={1\over (n-1)!}{n\brack 2}+{1\over n}\,.
\enddisplay
Unfolding this recurrence tells us that ${1\over n!}{n+1\brack2}=H_n$; hence
\begindisplay
{n+1\brack2}=n!H_n\,.
\eqno\eqref|stirl-harmonic|
\enddisplay

We proved in Chapter 2 that the harmonic series $\sum_k1/k$ diverges,
which means that $H_n$ gets arbitrarily large as $n\to\infty$. But
our proof was indirect; we found that a certain infinite sum
\equ(2.|double-harmonic|) gave different answers when it was rearranged,
hence $\sum_k1/k$ could not be bounded. The fact that $H_n\to\infty$
seems counter-intuitive, because it implies among other things that
a large enough stack of cards will overhang a table by a mile or more,
and that the worm $W$ will eventually reach the end of his rope.
Let us therefore take a closer look at the size of~$H_n$ when $n$~is large.

The simplest way to see that $H_n\to\infty$ is probably to group its
terms according to powers of~$2$. We put one term into group~$1$,
two terms into group~$2$,
four into group~$3$,
eight into group~$4$, and so on:
\begindisplay \def\\#1{{\hbox to0pt{\hss$\scriptstyle{\rm group\ }#1$\hss}}}
&\underbrace{{1\over 1}}_\\1
	+\, \underbrace{{1\over 2} {+} {1\over 3}}_\\2
	\,+\, \underbrace{{1\over 4} {+} {1\over 5} {+} {1\over 6}
		{+} {1\over 7}}_\\3
\,+\, \underbrace{{1\over 8} {+} {1\over 9} {+} {1\over 10}
		{+} {1\over 11} {+} {1\over 12} {+} {1\over 13}
		{+} {1\over 14} {+} {1\over 15}}_\\4
	\,+\, \cdots \,.
\enddisplay
Both terms in group~$2$ are between $1\over4$ and $\half$, so the sum of that
group is between $2\cdt{1\over4}=\half$ and $2\cdt\half=1$. All four terms
in group~$3$ are between $1\over8$ and~$1\over4$, so their sum is also
between $\half$ and~$1$. In fact, each of the $2^{k-1}$ terms in group~$k$
is between $2^{-k}$ and $2^{1-k}$; hence the sum of each individual group is
between $\half$ and~$1$.

This grouping procedure tells us that if $n$ is in group~$k$, we must
have $H_n>k/2$ and $H_n\le k$ (by induction on~$k$). Thus $H_n\to\infty$,
and in fact
\begindisplay
{\lfloor \lg n\rfloor+1\over2}<H_n\le\lfloor\lg n\rfloor+1\,.
\eqno
\enddisplay
We now know $H_n$ within a factor of $2$. Although the harmonic numbers
approach infinity, they approach it only logarithmically\dash---that is,
\g We should call them the worm numbers, they're so~slow.\g
quite slowly.

Better bounds can be found with just a little more work and a dose of
calculus. We learned in Chapter~2 that $H_n$ is the discrete analog of
the continuous function $\ln n$. The natural "logarithm" is defined as the
area under a curve, so a geometric comparison is suggested:
\begindisplay
\tabref|nn:ln|
\unitlength=1pt
\beginpicture(210,75)(-20,-10)
\put(0,0){\vector(0,1){60}}
\put(0,0){\vector(1,0){210}}
\put(-10,60){\makebox(0,0){$f(x)$}}
\put(210,-15){\makebox(0,0){$x$}}
\put(30,0){\line(0,1){30}}
\put(60,0){\line(0,1){30}}
\put(90,0){\line(0,1){15}}
\put(120,0){\line(0,1){10}}
\put(150,0){\line(0,1){7.5}}
\put(180,0){\line(0,1){6}}
\put(30,30){\line(1,0){30}}
\put(60,15){\line(1,0){30}}
\put(90,10){\line(1,0){30}}
\put(120,7.5){\line(1,0){30}}
\put(150,6){\line(1,0){30}}
\put(0,-10){\makebox(0,0){$\mathstrut 0$}}
\put(30,-10){\makebox(0,0){$\mathstrut 1$}}
\put(60,-10){\makebox(0,0){$\mathstrut 2$}}
\put(90,-10){\makebox(0,0){$\mathstrut 3$}}
\put(120,-10){\makebox(0,0){$\mathstrut \ldots$}}
\put(150,-10){\makebox(0,0){$\mathstrut n$}}
\put(180,-10){\makebox(0,0){$\mathstrut n{+}1$}}
\put(35,50){\makebox(0,0){$f(x)=1/x$}}
\put(0,0){\squine(22.5,25.7142859,30.0,40.0,34.2857146,30.0)}