chap6.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\put(0,0){\squine(30.0,33.3333335,37.5,30.0,26.6666665,24.0)}
\put(0,0){\squine(37.5,40.9090905,45.0,24.0,21.818183,20.0)}
\put(0,0){\squine(45.0,48.46154,52.5,20.0,18.4615374,17.142857)}
\put(0,0){\squine(52.5,55.9999976,60.0,17.142857,16.0,15.0)}
\put(0,0){\squine(60.0,63.5294123,67.5,15.0,14.1176476,13.3333334)}
\put(0,0){\squine(67.5,71.052631,75.0,13.3333334,12.6315774,12.0)}
\put(0,0){\squine(75.0,78.57143,82.5,12.0,11.42857,10.9090909)}
\put(0,0){\squine(82.5,86.086953,90.0,10.9090909,10.4347837,10.0)}
\put(0,0){\squine(90.0,93.599997,97.5,10.0,9.5999994,9.2307693)}
\put(0,0){\squine(97.5,101.111122,105.0,9.2307693,8.8888885,8.5714285)}
\put(0,0){\squine(105.0,108.62068,112.5,8.5714285,8.2758633,8.0)}
\put(0,0){\squine(112.5,116.129034,120.0,8.0,7.74193513,7.5)}
\put(0,0){\squine(120.0,123.636362,127.5,7.5,7.2727271,7.0588235)}
\put(0,0){\squine(127.5,131.14286,135.0,7.0588235,6.85714376,6.6666667)}
\put(0,0){\squine(135.0,138.648645,142.5,6.6666667,6.48648757,6.31578946)}
\put(0,0){\squine(142.5,146.15385,150.0,6.31578946,6.1538444,6.0)}
\put(0,0){\squine(150.0,153.658527,157.5,6.0,5.8536586,5.71428573)}
\endpicture
\enddisplay
The area under the curve between $1$ and $n$, which is $\int_1^n\,dx/x=\ln n$,
is less than the area of the $n$~rectangles, which is $\sum_{k=1}^n1/k=H_n$.
Thus $\ln n<H_n$; this is a sharper result than we had in \thiseq.
And by placing the rectangles a little differently, we get a similar upper bound:
\g\noindent\llap{``}I now see a way too how y$\rm^e\!$ aggregate of y$\rm^e\!$ termes of
Musicall progressions may bee found (much after y$\rm^e\!$ same manner)
by Logarithms, but y$\rm^e\!$ calculations for finding out those rules
would bee still more troublesom.''\par\hfill\dash---I. "Newton" [|newton-harm|]\g
\begindisplay
\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,-10){\makebox(0,0){$x$}}
\put(30,0){\line(0,1){30}}
\put(60,0){\line(0,1){15}}
\put(90,0){\line(0,1){10}}
\put(120,0){\line(0,1){7.5}}
\put(150,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(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)}
\put(0,0){\squine(30.0,33.3333335,37.5,30.0,26.6666665,24.0)}
\put(0,0){\squine(37.5,40.9090905,45.0,24.0,21.818183,20.0)}
\put(0,0){\squine(45.0,48.46154,52.5,20.0,18.4615374,17.142857)}
\put(0,0){\squine(52.5,55.9999976,60.0,17.142857,16.0,15.0)}
\put(0,0){\squine(60.0,63.5294123,67.5,15.0,14.1176476,13.3333334)}
\put(0,0){\squine(67.5,71.052631,75.0,13.3333334,12.6315774,12.0)}
\put(0,0){\squine(75.0,78.57143,82.5,12.0,11.42857,10.9090909)}
\put(0,0){\squine(82.5,86.086953,90.0,10.9090909,10.4347837,10.0)}
\put(0,0){\squine(90.0,93.599997,97.5,10.0,9.5999994,9.2307693)}
\put(0,0){\squine(97.5,101.111122,105.0,9.2307693,8.8888885,8.5714285)}
\put(0,0){\squine(105.0,108.62068,112.5,8.5714285,8.2758633,8.0)}
\put(0,0){\squine(112.5,116.129034,120.0,8.0,7.74193513,7.5)}
\put(0,0){\squine(120.0,123.636362,127.5,7.5,7.2727271,7.0588235)}
\put(0,0){\squine(127.5,131.14286,135.0,7.0588235,6.85714376,6.6666667)}
\put(0,0){\squine(135.0,138.648645,142.5,6.6666667,6.48648757,6.31578946)}
\put(0,0){\squine(142.5,146.15385,150.0,6.31578946,6.1538444,6.0)}
\put(0,0){\squine(150.0,153.658527,157.5,6.0,5.8536586,5.71428573)}
\endpicture
\enddisplay
This time the area of the $n$ rectangles, $H_n$, is less than the area of
the first rectangle plus the area under the curve. We have proved that
\begindisplay \postdisplaypenalty=10000
\ln n<H_n<\ln n+1\,,\qquad\hbox{for $n>1$}.
\eqno\eqref|harm-betw-logs|
\enddisplay
We now know the value of $H_n$ with an error of at most~$1$.

``Second order'' harmonic numbers $H_n^{(2)}$ arise when we sum the
"!harmonic numbers, second order"
squares of the reciprocals, instead of summing simply the reciprocals:
\begindisplay
H_n^{(2)}=1+{1\over4}+{1\over9}+\cdots+{1\over n^2}=\sum_{k=1}^n{1\over k^2}\,.
\enddisplay
Similarly, we define harmonic numbers of order $r$ by summing $(-r)$th powers:
\begindisplay
H_n^{(r)}=\sum_{k=1}^n{1\over k^r}\,.
\eqno
\enddisplay
\tabref|nn:hn-gen|%
If $r>1$, these numbers approach a limit as $n\to\infty$; we noted in
exercise 2.|zetaf|
that this limit is conventionally called "Riemann"'s "zeta function":
\begindisplay
\zeta(r)=H_\infty^{(r)}=\sum_{k\ge1}{1\over k^r}\,.
\eqno
\enddisplay

"Euler" [|euler-harmonics|]
discovered a neat way to use generalized harmonic numbers to approximate
"!harmonic numbers, approximate values"
the ordinary ones, $H_n^{(1)}$. Let's consider the infinite series
\begindisplay
\ln\biggl({k\over k-1}\biggr)={1\over k}+{1\over2k^2}+{1\over3k^3}
 +{1\over4k^4}+\cdots\,,
\eqno
\enddisplay
which converges when $k>1$. The left-hand side is
$\ln k-\ln(k-1)$; therefore if we sum both sides
for $2\le k\le n$ the left-hand sum telescopes and we get
\begindisplay  \openup3pt
\ln n-\ln1&=\sum_{k=2}^n\biggl({1\over k}+{1\over2k^2}+{1\over3k^3}
 +{1\over4k^4}+\cdots\,\biggr)\cr
&\tightplus=\textstyle\bigl(H_n{-}1\bigr)+\half\bigl(H_n^{(2)}{-}1\bigr)
 +{1\over3}\bigl(H_n^{(3)}{-}1\bigr)+{1\over4}\bigl(H_n^{(4)}{-}1\bigr)+\cdots\,.
\enddisplay
Rearranging, we have an expression for the difference between $H_n$ and
$\ln n$:
\begindisplay
\textstyle H_n-\ln n=1-\half\bigl(H_n^{(2)}{-}1\bigr)
 -{1\over3}\bigl(H_n^{(3)}{-}1\bigr)-{1\over4}\bigl(H_n^{(4)}{-}1\bigr)-\cdots\,.
\enddisplay
When $n\to\infty$, the right-hand side approaches the limiting value
\begindisplay
\textstyle1-\half\bigl(\zeta(2){-}1\bigr)
 -{1\over3}\bigl(\zeta(3){-}1\bigr)-{1\over4}\bigl(\zeta(4){-}1\bigr)-\cdots\,,
\enddisplay
which is now known as {\it "Euler's constant"\/} and conventionally denoted
by the Greek letter~"$\gamma$". In fact, $\zeta(r)-1$ is approximately
\g\noindent\llap{``}Huius igitur quantitatis constantis\/ $C$ valorem deteximus,
quippe est\/ ${C=0,577218}$.''\par\hfill\dash---L. "Euler" [|euler-harmonics|]\g
$1/2^r$, so this infinite series converges rather rapidly and we can
compute the decimal value
\begindisplay
\gamma=0.5772156649\ldots\,.
\eqno
\enddisplay
Euler's argument establishes the limiting relation
\begindisplay
\lim_{n\to\infty}(H_n-\ln n)=\gamma\,;
\eqno
\enddisplay
thus $H_n$ lies
about 58\% of the way between the two extremes in \eq(|harm-betw-logs|).
We are gradually homing in on its value.

Further refinements are possible, as we will see in Chapter~9. We will
prove, for example, that
\begindisplay
H_n=\ln n+\gamma+{1\over2n}-{1\over12n^2}+{\epsilon_n\over120n^4}\,,
\qquad\hbox{$0<\epsilon_n<1$}.
\eqno
\enddisplay
This formula allows us to conclude that the millionth harmonic number is
\begindisplay
H_{1000000}\approx14.3927267228657236313811275\,,
\enddisplay
without adding up a million fractions. Among other things, this implies
that a stack of a million cards can overhang the edge of a table by more than
seven cardlengths.

What does \thiseq\
tell us about the "worm" on the "rubber band"? Since $H_n$ is
unbounded, the worm will definitely reach the end, when $H_n$ first
exceeds~$100$. Our approximation to $H_n$ says that this will happen
when $n$ is approximately
\begindisplay
e^{100-\gamma}\approx e^{99.423}\,.
\enddisplay
In fact, exercise 9.|worm-finale| proves that the critical value of~$n$
\g\vskip-17pt
 Well, they can't really go at it this long; the world will have ended
much earlier, when the "Tower of Brahma" is fully transferred.\g
is either $\lfloor e^{100-\gamma}\rfloor$ or
$\lceil e^{100-\gamma}\rceil$. We can imagine $W$'s triumph when he
crosses the finish line at last, much to $K$'s chagrin, some
287 decillion centuries after his long crawl began. (The rubber band
will have stretched to more than $10^{27}$ light years long; its
molecules will be pretty far apart.)

\beginsection 6.4 Harmonic Summation

Now let's look at some sums involving harmonic numbers, starting with a review
of a few ideas we learned in Chapter~2. We proved in \equ(2.|harm-sum|)
and \equ(2.|harm-sum+|) that
\begindisplay \openup1pt
\sum_{0\le k<n}H_k&=nH_n-n\,;\eqno\eqref|+harm-sum|\cr
\sum_{0\le k<n}kH_k&={n(n-1)\over2}H_n\;-\;{n(n-1)\over4}\,.\eqno\eqref|+harm-sum+|\cr
\enddisplay
Let's be bold and take on a more general sum, which includes both of these
as special cases: What is the value of
\begindisplay \advance\abovedisplayskip-1.1pt\advance\belowdisplayskip-1.1pt
\sum_{0\le k<n}{k\choose m}H_k\,,
\enddisplay
when $m$ is a nonnegative integer?

The approach that worked best for \eq(|+harm-sum|) and \eq(|+harm-sum+|) in
Chapter~2 was called {\it "summation by parts"}. We wrote the summand in the
form $u(k)\Delta v(k)$, and we applied the general identity
\begindisplay
\sum\nolimits_a^b u(x)\Delta v(x)\,\delta x=
u(x)v(x)\big\vert_a^b\;-\;\sum\nolimits_a^b v(x+1)\Delta u(x)\,\delta x\,.
\eqno
\enddisplay
Remember? The sum that faces us now, $\sum_{0\le k<n}{k\choose m}H_k$,
is a natural for this method because we can let
\begindisplay \openup4pt
u(k)&=H_k\,,}\hfill{\qquad \qquad\Delta u(k)&=H_{k+1}-H_k={1\over k+1}\,;\cr
v(k)&={k\choose m{+}1}\,,}\hfill{\qquad\qquad \Delta v(k)&={k{+}1\choose m{+}1}-
 {k\choose m{+}1}={k\choose m}\,.\cr
\enddisplay
(In other words, harmonic numbers have a simple $\Delta$
and binomial coefficients have
a simple $\Delta^{-1}$, so we're in business.) Plugging into \thiseq\ yields
\begindisplay
\sum_{0\le k<n}\!{k\choose m}H_k=\!\sum\nolimits_0^n{x\choose m}H_x\,\delta x
&={x\choose m{+}1}H_x\bigg\vert_0^n-\sum\nolimits_0^n{x{+}1\choose m{+}1}
 {\delta x\over x{+}1}\cr
&={n\choose m{+}1}H_n\,-\!\sum_{0\le k<n}\!{k{+}1\choose m{+}1}{1\over k{+}1}\,.\cr
\enddisplay
The remaining sum is easy, since we can absorb the $(k+1)^{-1}$ using
our old standby, equation \equ(5.|bc-absorb|):
\begindisplay
\sum_{0\le k<n}{k+1\choose m+1}{1\over k+1}
=\sum_{0\le k<n}{k\choose m}{1\over m+1}
={n\choose m+1}{1\over m+1}\,.
\enddisplay
Thus we have the answer we seek:
\begindisplay
\sum_{0\le k<n}{k\choose m}H_k={n\choose m+1}\biggl(H_n-{1\over m+1}\biggr)\,.
\eqno\eqref|harm-sum++|
\enddisplay
(This checks nicely
with \eq(|+harm-sum|) and \eq(|+harm-sum+|) when $m=0$ and $m=1$.)

The next example sum uses division instead of multiplication: Let us
try to evaluate
\begindisplay
S_n=\sum_{k=1}^n{H_k\over k}\,.
\enddisplay
If we expand $H_k$ by its definition, we obtain a double sum,
\begindisplay
S_n=\sum_{1\le j\le k\le n}{1\over j\cdot k}\,.
\enddisplay
Now another method from Chapter 2 comes to our aid; equation
\equ(2.|upper-triangle|) tells us that
\begindisplay
S_n=\half \Biggl(\biggl(\sum_{k=1}^n {1\over k}\biggr)^2
 +\sum_{k=1}^n {1\over k^2}\Biggr)
=\half\bigl(H_n^2+H_n^{(2)}\bigr)\,.
\eqno\eqref|harm/k|
\enddisplay
It turns out that we could also
have obtained this answer in another way if we had tried
to sum by parts (see exercise |sum-triangle-by-parts|).

Now let's try our hands at a more difficult problem [|ungar|], which doesn't
submit to summation by parts:
\begindisplay
U_n=\sum_{k\ge1}{n\choose k}{(-1)^{k-1}\over k}(n-k)^n\,,
\qquad\hbox{integer $n\ge1$}.
\enddisplay
(This sum doesn't explicitly mention harmonic numbers either;
\g(Not to give the answer away or anything.)\g
but who knows when they might turn up?)

We will solve this problem in two ways, one by grinding out the answer and
the other by being clever and/or lucky. First, the grinder's approach.
We expand $(n-k)^n$ by the binomial theorem, so that the troublesome
$k$ in the denominator will combine with the numerator:
\begindisplay
U_n&=\sum_{k\ge1}{n\choose k}{(-1)^{k-1}\over k}\sum_j{n\choose j}(-k)^jn^{n-j}\cr
&=\sum_j{n\choose j}(-1)^{j-1}n^{n-j}\sum_{k\ge1}{n\choose k}(-1)^k k^{j-1}\,.\cr
\enddisplay
This isn't quite the mess it seems, because the $k^{j-1}$ in the inner sum
is a polynomial in~$k$, and identity \equ(5.|nth-diff|) tells us that we are
simply taking the "$n$th difference" of this polynomial. Almost; first we must
clean up a few things. For one, $k^{j-1}$ isn't a polynomial if $j=0$; so we
will need to split off that term and handle it separately. For another,
we're missing the term $k=0$ from the formula for $n$th difference; that
term is nonzero when $j=1$, so we had better restore it (and subtract it out again).
The result is
\begindisplay
U_n&=\sum_{j\ge1}{n\choose j}(-1)^{j-1}n^{n-j}\sum_{k\ge0}{n\choose k}(-1)^kk^{j-1}\cr
&\qquad -\sum_{j\ge1}{n\choose j}(-1)^{j-1}n^{n-j}{n\choose 0}0^{j-1}\cr
\noalign{\vskip1pt}
&\qquad -{n\choose 0}n^n\sum_{k\ge1}{n\choose k}(-1)^kk^{-1}\,.\cr
\enddisplay
OK, now the top line (the only remaining double sum) is zero: It's
the sum of multiples of $n$th differences of polynomials of degree less
than~$n$,
and such $n$th differences are zero. The second line is zero except when
$j=1$, when it equals $-n^n$. So the third line is the only residual
difficulty; we have reduced the original problem to a much simpler sum:
\begindisplay
U_n=n^n(T_n-1)\,,\qquad\hbox{where }
T_n=\sum_{k\ge1}{n\choose k}{(-1)^{k-1}\over k}\,.
\eqno\eqref|tn-def|
\enddisplay
For example, $U_3={3\choose1}{8\over1}-{3\choose2}{1\over2}
={45\over2}$; $T_3={3\choose1}{1\over1}-{3\choose2}{1\over2}+{3\choose3}{1\over3}
={11\over6}$; hence $U_3=27(T_3-1)$ as claimed.

How can we evaluate $T_n$? One way is to replace $n\choose k$ by
${n-1\choose k}+{n-1\choose k-1}$, obtaining a simple recurrence for $T_n$
in terms of $T_{n-1}$. But there's a more instructive way: We had a
similar formula in \equ(5.|recip-bc|), namely
\begindisplay
\sum_k{n\choose k}{(-1)^k\over x+k}= {n!\over x(x+1)\ldots(x+n)}\,.
\enddisplay
\looseness=-1
If we subtract out the term for $k=0$ and set $x=0$, we get $-T_n$.
So let's do~it:
\begindisplay \ope