chap2.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

"!arithmetic progression"
$\alpha=\beta=a$, $\gamma=b$, and the answer is
$aA(n)+aB(n)+bC(n)=a(n+1)+b(n+1)n/2$.

Conversely, many recurrences can be reduced to sums; therefore the
special methods for evaluating sums that we'll be learning later
in this chapter will help us solve recurrences that might otherwise
be difficult. The "Tower of Hanoi" recurrence is a case in point:
\begindisplay
T_0&=0\,;\cr
T_n&=2T_{n-1}+1\,,\qquad\hbox{for $n>0$}.\cr
\enddisplay
It can be put into the special form \eq(|sum-rec|)
if we divide both sides by $2^n$:
\begindisplay
T_0/2^0&=0;\cr
T_n/2^n&=T_{n-1}/2^{n-1}+1/2^n\,,\qquad\hbox{for $n>0$}.\cr
\enddisplay
Now we can set $S_n=T_n/2^n$, and we have
\begindisplay
S_0&=0;\cr
S_n&=S_{n-1}+2^{-n}\,,\qquad\hbox{for $n>0$}.\cr
\enddisplay
It follows that
\begindisplay
S_n=\sum_{k=1}^n 2^{-k}.
\enddisplay
(Notice that we've left the term for $k=0$ out of this sum.)
The sum of the geometric series $2^{-1}+2^{-2}+\cdots+2^{-n}=
(\half )^1+(\half )^2+\cdots+(\half )^n$ will be derived
later in this chapter; it turns out to be $1-(\half )^n$.
Hence $T_n=2^nS_n=2^n-1$.

We have converted $T_n$ to $S_n$ in this derivation by noticing that
the recurrence could be divided by $2^n$. This trick
is a special case of a general technique
that can reduce virtually any "recurrence" of the form
\begindisplay
a_nT_n=b_nT_{n-1}+c_n
\eqno\eqref|sum-factor-rec|
\enddisplay
to a sum. The idea is to multiply both sides by a
{\it"summation factor"},~$s_n$:
\begindisplay
s_na_nT_n=s_nb_nT_{n-1}+s_nc_n\,.
\enddisplay
This factor $s_n$ is cleverly chosen to make
\begindisplay
s_nb_n=s_{n-1}a_{n-1}\,.
\enddisplay
Then if we write $S_n=s_na_nT_n$ we have a sum-recurrence,
\begindisplay
S_n=S_{n-1}+s_nc_n\,.
\enddisplay
Hence
\begindisplay
S_n=s_0a_0T_0+\sum_{k=1}^n s_kc_k=s_1b_1T_0+\sum_{k=1}^n s_kc_k\,,
\enddisplay
and the solution to the original recurrence \thiseq\ is
\begindisplay
T_n={1\over s_na_n}\biggl(s_1b_1T_0+\sum_{k=1}^n s_kc_k\biggr)\,.
\eqno\eqref|sum-factor-sol|
\enddisplay
\g(The value of $s_1$ cancels out, so it can be anything but~zero.)\g
For example, when $n=1$ we get $T_1=(s_1b_1T_0+s_1c_1)/s_1a_1=(b_1T_0+c_1)/a_1$.

But how can we be clever enough to find the right $s_n$? No problem:
The relation $s_n=s_{n-1}a_{n-1}/b_n$ can be unfolded to
tell us that the fraction
\begindisplay
s_n={a_{n-1}a_{n-2}\ldots a_1\over b_nb_{n-1}\ldots b_2}\,,
\eqno\eqref|sum-factor|
\enddisplay
or any convenient constant
 multiple of this value, will be a suitable summation factor.
For example, the Tower of Hanoi recurrence has $a_n=1$ and $b_n=2$;
the general method we've just derived says that $s_n=2^{-n}$ is a good
thing to multiply by, if we want to reduce the recurrence to a sum.
We don't need a brilliant flash of inspiration to discover this multiplier.

We must be careful, as always, not to divide by zero. The summation-factor
method works whenever all the $a$'s and all the $b$'s are nonzero.

Let's apply these ideas to a recurrence that arises in the study of
``"quicksort",\qback'' one of the most important methods for "sorting"
\g(Quicksort was invented by "Hoare" in 1962~[|hoare|].)\g
data inside a computer. The average number of comparison steps made by
quicksort when it is applied to $n$ items in random order satisfies the
recurrence
\begindisplay
\eqalign{C_0&=0\,;\cr
   C_n	&= n+1+{2\over n}\sum_{k=0}^{n-1}C_k\,, \qquad\hbox{for $n>0$.}\cr
}\eqno\eqref|quicksort-rec|
\enddisplay
Hmmm. This looks much scarier than the recurrences we've seen before;
it includes a sum over all previous values, and a division by~$n$.
Trying small cases gives us some data ($C_1=2$, $C_2=5$, $C_3={26\over3}$)
but doesn't do anything to quell our fears.

We can, however, reduce the complexity of \thiseq\
systematically, by first getting rid of the division and then
getting rid of the $\sum$ sign. The idea is to
multiply both sides by~$n$, obtaining the relation
\begindisplay
nC_n=n^2+n+2\sum_{k=0}^{n-1}C_k\,,\qquad\hbox{for $n>0$};
\enddisplay
hence, if we replace $n$ by $n-1$,
\begindisplay
(n-1)C_{n-1}=(n-1)^2+(n-1)+2\sum_{k=0}^{n-2}C_k\,,\qquad\hbox{for $n-1>0$}.
\enddisplay
We can now subtract the second equation from the first, and the $\sum$ sign
disappears:
\begindisplay
nC_n-(n-1)C_{n-1}=2n+2C_{n-1}\,,\qquad\hbox{for $n>1$}.
\enddisplay
It turns out that this relation also holds when $n=1$, because $C_1=2$.
Therefore the original recurrence for $C_n$ reduces to a much simpler one:
\begindisplay
C_0&=0\,;\cr
nC_n&=(n+1)C_{n-1}+2n\,,\qquad\hbox{for $n>0$}.
\enddisplay
Progress.
We're now in a position to apply a summation factor, since this recurrence
has the form of \eq(|sum-factor-rec|) with $a_n=n$, $b_n=n+1$, and $c_n=2n$.
The general method described on the preceding page
tells us to multiply the recurrence
through by some multiple of
\begindisplay
s_n={a_{n-1}a_{n-2}\ldots a_1\over b_nb_{n-1}\ldots b_2}=
{(n-1)\cdot(n-2)\cdot\ldots\cdot1\over(n+1)\cdot n\cdot\ldots\cdot3}=
{2\over(n+1)n}\,.
\enddisplay
The solution, according to
\g We started with a $\sum$ in the recurrence, and worked hard
to get rid of it. But then after applying a summation factor,
we came up with another $\sum$. Are sums good, or bad, or what?\g
\eq(|sum-factor-sol|), is therefore
\begindisplay
C_n=2(n+1)\sum_{k=1}^n{1\over k+1}\,.
\enddisplay

The sum that remains is very similar to a quantity that arises frequently
in applications. It arises so often, in fact, that we give it a special name
and a special notation:
\begindisplay
H_n=1+\half +\cdots+{1\over n}=\sum_{k=1}^n {1\over k}\,.
\eqno\eqref|h-def|
\enddisplay
\tabref|nn:hn|%
The letter $H$ stands for ``harmonic''; $H_n$ is a {\it "harmonic number"},
so called because the $k$th harmonic produced by a "violin" string
is the fundamental tone produced by a string that is~$1/k$ times as long.

We can complete our study of the quicksort recurrence \eq(|quicksort-rec|)
by putting $C_n$ into closed form; this will be possible if we can
express $C_n$ in terms of $H_n$. The sum in our formula for $C_n$ is
\begindisplay
\sum_{k=1}^n{1\over k+1}=\sum_{1\le k\le n}{1\over k+1}\,.
\enddisplay
We can relate this to $H_n$ without much difficulty
 by changing $k$ to $k-1$ and revising the
boundary conditions:
\begindisplay \openup2pt
\sum_{1\le k\le n}{1\over k+1}&=\sum_{1\le k-1\le n}{1\over k}\cr
 &=\sum_{2\le k\le n+1}{1\over k}\cr
 &=\biggl(\sum_{1\le k\le n}{1\over k}\biggr) -{1\over 1}+{1\over n+1}
 = H_n-{n\over n+1}\,.\cr
\enddisplay
Alright! We have found the sum needed to complete the
\g But your spelling is alwrong.\g
 solution to \eq(|quicksort-rec|):
The average number of comparisons made by quicksort when it is applied to
$n$~randomly ordered items of data is
\begindisplay
C_n=2(n+1)H_n-2n\,.\eqno
\enddisplay
As usual, we check that small cases are correct: $C_0=0$, $C_1=2$, $C_2=5$.

\beginsection 2.3 Manipulation of Sums

The key to success with sums is an ability to change one $\sum$ into another
\g\vskip-38pt Not to be confused with finance.\g
that is simpler or closer to some goal. And it's easy to do this by learning
a few basic rules of transformation and by practicing their use.

Let $K$ be any finite set of integers. Sums over the elements of $K$ can be
transformed by using three simple rules:
\begindisplay
\sum_{k\in K} ca_k&=c\sum_{k\in K}a_k\,;&\qquad\hbox{(distributive law)}
 \eqno\eqref|dist-law|\cr
\noalign{\smallskip}
\sum_{k\in K}(a_k+b_k)&=\sum_{k\in K}a_k+\sum_{k\in K}b_k\,;
 &\qquad\hbox{(associative law)}
 \eqno\eqref|assoc-law|\cr
\noalign{\smallskip}
\sum_{k\in K}a_k&=\sum_{p(k)\in K}a_{p(k)}\,.
 &\qquad\hbox{(commutative law)}
 \eqno\eqref|comm-law|\cr
\enddisplay
The "distributive law" allows us to move constants in and out of a $\sum$.
The "associative law" allows us to break a $\sum$ into two parts, or to
combine two $\sum$'s into one. The "commutative law" says that we can
reorder the terms in any way we please; here $p(k)$ is any permutation
\g Why not call it permutative instead of commutative?\g
of the set of all integers.
For example, if $K=\{-1,0,+1\}$ and if $p(k)=-k$, these three laws
tell us respectively that
\begindisplay
&ca_{-1}+ca_0+ca_1=c(a_{-1}+a_0+a_1)\,;&\qquad\hbox{(distributive law)}\cr
\noalign{\vskip2pt}
&(a_{-1}+b_{-1})+(a_0+b_0)+(a_1+b_1)\cr
&\quad=(a_{-1}+a_0+a_1)+(b_{-1}+b_0+b_1)\,;
 &\qquad\hbox{(associative law)}\cr
\noalign{\vskip2pt}
&a_{-1}+a_0+a_1=a_1+a_0+a_{-1}\,.&\qquad\hbox{(commutative law)}\cr
\enddisplay

"Gauss"'s trick in Chapter 1 can be viewed as an application of these three
basic laws. Suppose we want to compute the general sum of an
{\it"arithmetic progression"},
\begindisplay
S=\sum_{0\le k\le n}(a+bk)\,.
\enddisplay
By the commutative law we can replace $k$ by $n-k$,
\g This is something like changing variables inside an integral, but easier.\g
 obtaining
\begindisplay
S=\sum_{0\le n-k\le n}\bigl(a+b(n-k)\bigr)=
\sum_{0\le k\le n}(a+bn-bk)\,.
\enddisplay
These two equations can be added by using the associative law:
\begindisplay
2S=\sum_{0\le k\le n}\bigl((a+bk)+(a+bn-bk)\bigr)
  =\sum_{0\le k\le n}(2a+bn)\,.
\enddisplay
And we can now apply the distributive law and evaluate a trivial sum:
\g ``What's one and one and one and one and one and one and one and one
and one and~one?''\par
``I don't know,'' said~"Alice".\par ``I lost count.''\par % from Chapter 9
``She can't do Addition.''\par\hfill\kern-4pt\dash---Lewis "Carroll"~[|alice-looking|]\g %
\begindisplay
2S=(2a+bn)\sum_{0\le k\le n}1 = (2a+bn)(n+1)\,.
\enddisplay
Dividing by 2, we have proved that
\begindisplay
\sum_{k=0}^n(a+bk)=\textstyle(a+\half bn)(n+1)\,.\eqno\eqref|arith-sum|
\enddisplay
The right-hand side can be remembered as the average of the
first and last terms,
namely $\half \bigl(a+(a+bn)\bigr)$, times the number of terms,
namely $(n+1)$.

It's important to bear in mind that the function $p(k)$ in the general
commutative law \eq(|comm-law|)
is supposed to be a permutation of all the integers. In other words,
for every integer~$n$ there should be exactly one integer~$k$ such that
$p(k)=n$. Otherwise the commutative law might fail; exercise~|bad-perm|
illustrates this with a vengeance. Transformations like $p(k)=k+c$
or $p(k)=c-k$, where $c$~is an integer constant, are always
permutations, so they always work.

On the other hand, we can relax the permutation restriction a little
"!commutative law, relaxed"
bit: We need to require only that there be exactly one integer~$k$ with
$p(k)=n$ when $n$ is an element of the index set~$K$. If $n\notin K$
(that is, if $n$ is not in~$K$), it doesn't matter how often $p(k)=n$ occurs,
because such $k$ don't take part in the sum.
Thus, for example, we can argue that
\begindisplay
\sum\twoconditions{k\in K}{k{\rm\ even}}a_k=
\sum\twoconditions{n\in K}{n{\rm\ even}}a_n=
\sum\twoconditions{2k\in K}{2k{\rm\ even}}a_{2k}=
\sum_{2k\in K}a_{2k}\,,
\eqno\eqref|even-trick|
\enddisplay
since there's exactly one $k$ such that $2k=n$ when $n\in K$ and $n$ is even.

"Iverson's convention", which allows us to obtain the values $0$ or~$1$
from logical statements in the middle of a formula, can be used
together with the distributive, associative, and commutative laws to deduce
\g Additional, eh?\g
additional properties of sums. For example, here is an important rule for
combining different sets of indices:
If $K$ and $K'$ are any sets of integers, then
\begindisplay
\sum_{k\in K}a_k\;+\;\sum_{k\in K'}a_k\;=\;\sum_{k\in K\cap K'}a_k\;+\;
 \sum_{k\in K\cup K'}a_k\,.
\eqno\eqref|set-sum|
\enddisplay
This follows from the general formulas
\begindisplay
\sum_{k\in K}a_k\;=\;\sum_k a_k\,\[k\in K]
\eqno
\enddisplay
and
\begindisplay
\[k\in K]+\[k\in K']=\[k\in K\cap K']+\[k\in K\cup K']\,.
\eqno
\enddisplay
Typically we use rule \eq(|set-sum|) either to combine two almost-disjoint
index sets, as in
\begindisplay
\sum_{k=1}^m a_k\;+\;\sum_{k=m}^n a_k\;=\;a_m\;+\;\sum_{k=1}^n a_k\,,
\qquad\hbox{for $1\le m\le n$};
\enddisplay
or to split off a single term from a sum, as in
\g\vskip15pt(The two sides of \eq(|set-sum|) have been switched here.)\g
\begindisplay
\sum_{0\le k\le n}a_k\;=\;a_0\;+\;\sum_{1\le k\le n}a_k\,,
\qquad\hbox{for $n\ge0$}.
\eqno
\enddisplay

This operation of splitting off a term is the basis of a
{\it"perturbation method"\/} that often allows us to evaluate a
sum in closed form. The idea is to start with an unknown sum
and call it $S_n$:
\begindisplay
S_n=\sum_{0\le k\le n}a_k\,.
\enddisplay
(Name and conquer.)
Then we rewrite $S_{n+1}$ in two ways, by splitting off both its
last term and its first term:
\begindisplay \openup2pt
S_n+a_{n+1}=\sum_{0\le k\le n+1}a_k&=a_0+\sum_{1\le k\le n+1}a_k\cr
&=a_0+\sum_{1\le k+1\le n+1}a_{k+1}\cr
&=a_0+\sum_{0\le k\le n}a_{k+1}\,.\eqno\eqref|perturb-setup|\cr