chap2.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

%Chapter 2 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac
\refin bib
\refin chap5

\pageno=21
\beginchapter 2 Sums

"SUMS" ARE EVERYWHERE in mathematics, so we need basic tools to handle them.
This chapter develops
the notation and general techniques
that make summation user-friendly.

\beginsection 2.1 Notation

In Chapter 1 we encountered the sum
of the first~$n$ integers, which we wrote out as
$1+2+3+\cdots+(n-1)+n$.
The `$\,\cdots\,$' in such formulas
tells us to complete the pattern established
by the surrounding terms.
Of course we have to watch out for sums like $1 + 7 + \cdots + 41.7$,
which are meaningless without a mitigating context.
On the other hand, the inclusion of terms like $3$ and $(n-1)$ was a
bit of overkill; the pattern would presumably have been clear if we
had written simply $1+2+\cdots+n$. Sometimes we might even be so bold as to write
just $1+\cdots+n$.

We'll be working with sums of the general form
\begindisplay
a_1 + a_2 + \cdots + a_n \,,
\eqno\eqref|3dots-sum|
\enddisplay
where each $a_k$ is a number
that has been defined somehow.
This notation has the advantage that we can ``see'' the whole sum,
"!..." "!three dots (...)" "!ellipsis (...)"
almost as if it were written out in full, if we have a good enough imagination.

 Each element~$a_k$
of a sum is called a {\it "term"}.
\g A term is how long this course lasts.\g
The terms are often specified implicitly as formulas
that follow a readily perceived pattern, and in such cases we must sometimes
write them in an expanded form
so that the meaning is clear. For example, if
\begindisplay
1+2+\cdots+2^{n-1}
\enddisplay
is supposed to denote a sum of $n$ terms, not of $2^{n-1}$, we should
write it more explicitly as
\begindisplay
2^0+2^1+\cdots+2^{n-1}.
\enddisplay

The three-dots notation
\g \noindent\llap{``}Le signe $\sum_{i=1}^{i=\infty}$ indique que l'on~doit
donner au nombre entier $i$ toutes ses valeurs $1$, $2$, $3$, \dots,
et prendre la somme des termes.''\par
\noindent\hfill\dash---J. "Fourier" [|fourier|]\g
has many uses, but it can be ambiguous and a bit
long-winded. Other alternatives are available, notably the delimited form
\begindisplay
\sum_{k=1}^n a_k\,,
\eqno\eqref|delim-sum|
\enddisplay
\looseness=-1
which is called "Sigma-notation"
because it uses the Greek letter $\sum$ (uppercase sigma).
This notation tells us to include in the sum precisely
those terms~$a_k$ whose index~$k$ is an integer that lies
between the lower and upper limits 1~and~$n$, inclusive.
In words, we ``sum over $k$, from~$1$ to~$n$.''
Joseph Fourier introduced this delim\-ited $\sum$-"notation" in 1820,
and it soon took the mathematical world by storm.

Incidentally,
the quantity after $\sum$ (here~$a_k$) is called the {\it "summand"}.

 The "index variable"~$k$
is said to be {\it bound\/} to the $\sum$ sign in \thiseq, because the
"!bound variables"
$k$ in $a_k$ is unrelated to appearances of~$k$ outside the Sigma-notation.
Any other letter
\g Well, I wouldn't want to use $a$ or $n$ as the index variable instead of~$k$
in \thiseq; those letters are ``"free variables"'' that do have meaning outside
the $\sum$ here.\g
could be substituted for~$k$ here without changing the
meaning of \thiseq. The letter $i$ is often used (perhaps because it stands
for ``index''), but we'll generally sum on $k$ since it's wise to keep
$i$ for $\sqrt{-1}$.

It turns out that a generalized Sigma-notation is even
more useful than the delimited form: We simply write one or more
conditions under the $\sum$, to specify the set of indices over which
summation should take place. For example, the sums in \eq(|3dots-sum|) and
\eq(|delim-sum|) can also be written as
\begindisplay
\sum_{1 \le k \le n} a_k \,.
\eqno\eqref|gen-sum|
\enddisplay
In this particular example there isn't much difference between the
new form and \eq(|delim-sum|), but the general form allows us to
take sums over "index set"s that aren't restricted to consecutive integers.
For example, we can express the sum of the squares of all odd positive
integers below~100 as follows:
\begindisplay
 \sum\twoconditions{1 \le k < 100}{k \rm\ odd} k^2 \,\,.
\enddisplay
The delimited equivalent of this sum,
\begindisplay
 \sum_{k=0}^{49} (2k+1)^2 \,,
\enddisplay
is more cumbersome and less clear.
Similarly, the sum of reciprocals of all prime numbers between $1$ and~$N$
is
\begindisplay
\sum\twoconditions{p \leq N}{p \rm\ prime}{1\over p} \,;
\enddisplay
the delimited form would require us to write
\begindisplay
\sum_{k=1}^{\pi(N)}{1\over p_k}\,,
\enddisplay
where $p_k$ denotes the $k$th prime and $\pi(N)$ is the number of
primes $\le N$.
(Incidentally, this sum gives the approximate average
number of distinct "prime factors" of a random integer near~$N$, since
about $1/p$ of those integers are divisible by~$p$.
Its value for large~$N$ is approximately $\ln\ln N+M$, where
$M\approx0.2614972128476427837554268386086958590515666$ is "Mertens"'s
constant~[|mertens-M|];
$\ln x$ stands for the natural logarithm of~$x$, and $\ln\ln x$ stands
for $\ln(\ln x)$.)

The biggest advantage of general Sigma-notation is that
we can manipulate it more easily than the delimited form.
\g The summation symbol looks like a distorted pacman.\g
For example, suppose we want to change the index variable~$k$ to~$k+1$.
With the general form, we have
\begindisplay
 \sum_{1 \leq k \leq n} a_k
	= \sum_{1 \leq k+1 \leq n} a_{k+1} \,;
\enddisplay
it's easy to see what's going on, and we can do the substitution almost
without thinking. But with the delimited form, we have
\begindisplay
 \sum_{k=1}^n a_k
	= \sum_{k=0}^{n-1} a_{k+1} \,;
\enddisplay
it's harder to see what's happened, and we're more likely to make a mistake.

On the other hand, the delimited form isn't completely useless.
It's nice and tidy, and we can write it quickly because \eq(|delim-sum|)
\g A tidy sum.\g
has seven symbols compared with \eq(|gen-sum|)'s eight.
Therefore we'll often use $\sum$ with upper and lower delimiters
when we state a problem or present a result, but we'll
prefer to work with relations-under-$\sum$ when we're manipulating a sum
whose index variables need to be transformed.

The $\sum$ sign occurs more than 1000 times in this book,
\g That's nothing. You should see how many times {\char6} appears
in The~Iliad.\g
 so we should be
sure that we know exactly what it means. Formally, we write
\begindisplay
\sum_{P(k)}a_k\eqno
\enddisplay
as an abbreviation for the sum of all terms $a_k$ such that $k$ is an
integer satisfying a given "property" $P(k)$. (A ``property $P(k)$'' is
any statement about $k$ that can be either true or false.)
 For the time being, we'll
assume that only finitely many integers~$k$ satisfying~$P(k)$ have
$a_k\ne0$; otherwise infinitely many nonzero numbers are being added
together, and things can get a bit tricky. At the other extreme, if
$P(k)$ is false for all integers~$k$, we have an ``empty'' sum;
the value of an "empty sum" is defined to be zero.

A slightly modified form
of \thiseq\ is used when a sum appears within the text of a paragraph
rather than in a displayed equation: We write `$\sum_{P(k)}a_k$', attaching
property~$P(k)$ as a subscript of~$\sum$, so that the formula won't
stick out too much. Similarly, `$\sum_{k=1}^na_k$' is a convenient
alternative to \eq(|delim-sum|) when we want to confine the notation
to a single line.

People are often tempted to write
\begindisplay\advance\abovedisplayskip-3pt\advance\belowdisplayskip-3pt
\sum_{k=2}^{n-1}k(k-1)(n-k)\qquad\hbox{instead of}
 \qquad\sum_{k=0}^{n}k(k-1)(n-k)
\enddisplay
because the terms for $k=0$, $1$, and $n$ in this sum are zero. Somehow it
seems more efficient to add up $n-2$ terms instead of $n+1$ terms.
But such temptations should be resisted; "efficiency" of computation is
not the same as efficiency of understanding!  We will find it advantageous
to keep upper and lower bounds
on an index of summation as simple as possible, because
sums can be manipulated much more easily when the bounds
are simple. Indeed, the form $\sum_{k=2}^{n-1}$ can even be dangerously
ambiguous, because its meaning is not at all clear when $n=0$ or $n=1$
(see exercise~|backward-delim|). Zero-valued terms cause no harm, and they often
"!0, not considered harmful"
save a lot of trouble.

So far the "notation"s we've been discussing are quite standard, but now we
are about to make a radical departure from tradition. Kenneth~E. "Iverson"
introduced a wonderful idea in his programming language APL
[|APL|, page~11; see also |knuth-tnn|],
and we'll see that it greatly simplifies many of the things we want to
do in this book. The idea is simply to enclose a true-or-false statement
in brackets, and to say that the result is $1$ if the statement is true,
\tabref|nn:iverson|%
\g Hey: The ``"Kronecker delta"'' that I've seen in other
books (I~mean $\delta_{kn}$, which is
$1\mskip-1mu$~if $@{k=n}$, \
 $0$~otherwise) is just a special case of Iverson's
convention: We can write $\[k=n]$ instead.\g
$0$ if the statement is false. For example,
\begindisplay
\[p{\rm\ prime}] =\cases{1,&if $p$ is a prime number;\cr
	0,&if $p$ is not a prime number.\cr}
\enddisplay
Iverson's convention allows us to express sums with no constraints whatever
on the index of summation, because we can rewrite \thiseq\ in the form
\begindisplay \advance\belowdisplayskip-3pt
\sum_k a_k\bigi[P(k)\bigr]\,.
\eqno
\enddisplay
If $P(k)$ is false, the term $a_k\bigi[P(k)\bigr]$ is zero, so we can
safely include it among the terms being summed. This makes it easy to
manipulate the index of summation, because we don't have to fuss
with boundary conditions.
\g\noindent\llap{``}I am often surprised by new, important applications
 [of this notation].''\par\hskip0pt plus 1fill minus 3pt
\dash---B.~de~"Finetti"~[|de-finetti|]\looseness=-1\g

A slight technicality needs to be mentioned: Sometimes $a_k$ isn't defined
for all integers~$k$. We get around this difficulty
 by assuming that $\bigi[P(k)\bigr]$
is ``very strongly zero'' when $P(k)$ is false; it's so much zero, it makes
"!zero, strongly"
$a_k\bigi[P(k)\bigr]$ equal to zero even when $a_k$ is undefined.
For example, if
we use Iverson's convention to write the sum of reciprocal primes $\le N$ as
\begindisplay
\sum_p\[p{\rm\ prime}]\[p\le N]/p\,,
\enddisplay
there's no problem of division by zero when $p=0$, because our convention
tells us that $\[0{\rm\ prime}]\[0\le N]/0=0$.

Let's sum up what we've discussed so far about sums. There are two
good ways to express a sum of terms: One way uses `$\,\cdots\,$', the
other uses `$\,\sum\,$'. The three-dots form often suggests useful
manipulations, particularly the combination of adjacent terms, since we
might be able to spot a simplifying pattern if we let the whole sum
hang out before our eyes. But too much detail can also be overwhelming.
Sigma-notation is compact, impressive to family and friends, and
\g\dots\ and it's less likely to lose points on an exam for ``lack
of rigor.\qback''\g
often suggestive of manipulations that are not obvious in three-dots form.
When we work with Sigma-notation, zero terms are not generally harmful;
"!0, not considered harmful"
in fact, zeros often make $\sum$-manipulation easier.

\beginsection 2.2 Sums and Recurrences

OK, we understand now how to express sums with fancy notation.
But how does a person actually go about finding the value of a sum?
One way is to observe that there's an intimate relation between
sums and "recurrence"s. The sum
\begindisplay
S_n=\sum_{k=0}^n a_k
\enddisplay
is equivalent to the recurrence
\g(Think of\/ $S_n$ as not just a single number, but as a
sequence defined for all $n\ge0$.)\g
\begindisplay
\eqalign{S_0&=a_0\,;\cr
   S_n	&= S_{n-1} + a_n\,, \qquad\hbox{for $n>0$.}\cr
}\eqno\eqref|sum-rec|
\enddisplay
Therefore we can evaluate sums in closed form by using the methods
we learned in Chapter~1 to solve recurrences in closed form.

For example, if $a_n$ is equal to a constant plus a multiple of~$n$,
the sum-recurrence \eq(|sum-rec|) takes the following general form:
\begindisplay
\eqalign{R_0&=\alpha\,;\cr
   R_n	&= R_{n-1} + \beta + \gamma n\,, \qquad\hbox{for $n>0$.}\cr
}\eqno\eqref|abc-rec|
\enddisplay
Proceeding as in Chapter 1, we find $R_1=\alpha+\beta+\gamma$,
$R_2=\alpha+2\beta+3\gamma$, and so on; in general the solution can be
written in the form
\begindisplay
R_n=A(n)@\alpha+B(n)@\beta+C(n)@\gamma\,,
\eqno
\enddisplay
where $A(n)$, $B(n)$, and $C(n)$ are the coefficients of dependence on
the general parameters $\alpha$, $\beta$, and $\gamma$.

The "repertoire method" tells us to try plugging in simple functions of~$n$ for
$R_n$, hoping to find constant parameters $\alpha$, $\beta$, and $\gamma$
where the solution is especially simple.
Setting $R_n=1$ implies $\alpha=1$, $\beta=0$, $\gamma=0$; hence
\begindisplay
A(n)=1\,.
\enddisplay
Setting $R_n=n$ implies $\alpha=0$, $\beta=1$, $\gamma=0$; hence
\begindisplay
B(n)=n\,.
\enddisplay
Setting $R_n=n^2$ implies $\alpha=0$, $\beta=-1$, $\gamma=2$; hence
\begindisplay
2C(n)-B(n)=n^2
\enddisplay
and we have $C(n)=(n^2+n)/2$. Easy as pie.
\g Actually easier;~$\pi\,{=}\kern-4pt$\smallskip
\hskip-\mathsurround$\sum_{n\ge0}\kern-1.8pt{8\over(4n+1)(4n+3)}$\kern-1pt
.\kern-3.5pt\null\g

Therefore if we wish to evaluate
\begindisplay
\sum_{k=0}^n(a+bk)\,,
\enddisplay
the sum-recurrence \eq(|sum-rec|) boils down to \eq(|abc-rec|) with