chap5.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

and multiply both sides by~$y^r$.

We have proved the binomial theorem only when $r$ is a nonnegative integer,
by using a combinatorial interpretation. We can't deduce the general
case from the nonnegative-integer case
by using the polynomial argument, because the sum is
infinite in the general case.
But when $r$ is arbitrary,
we can use "Taylor" series and the theory of complex variables:
\begindisplay
f(z)
&={f(0)\over0!}z^0+{f'(0)\over1!}z^1+{f''(0)\over2!}z^2+\cdots\,\cr
&=\sum_{k\ge0}{f^{(k)}(0)\over k!}z^k\,.
\enddisplay
The derivatives of the function $f(z)=(1+z)^r$ are easily evaluated; in fact,
$f^{(k)}(z)=r\_k\,(1+z)^{r-k}$. Setting $z=0$ gives \thiseq.

We also need to prove that the infinite sum converges, when $\vert z\vert
\g(Chapter 9 tells the meaning of\/~$O$.)\g
<1$. It does, because ${r\choose k}=O(k^{-1-r})$ by
equation \eq(|f-def-lim|) below.

\topinsert
\setbox0=\hbox{$\biggr)$}
\def\\#1{\displaystyle{n\choose#1}\kern-\wd0}
\table "Pascal's triangle, extended upward".\tabref|pascal-triangle-up|
\offinterlineskip
\halign to\hsize{\strut$\hfil#$\quad&\vrule#\kern-5pt\tabskip10pt plus 100pt&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
\kern-3pt\hfil$#$&
 \hfil$#$&
\kern-3pt\hfil$#$&
 \hfil$#$&
\kern-3pt\hfil$#$&
 \hfil$#$&
\kern-3pt\hfil$#$&
 \hfil$#$\tabskip2pt\cr
\omit&height 4pt\cr
n &&\\0&\\1&\\2&\\3\kern.1em&\\4\kern.25em&\\5\kern.25em&\\6\kern.25em&
 \\7\kern.4em&\\8\kern.45em&\\9\kern.45em&\\{10}\kern.45em\cr
\omit&height 3pt\cr
\noalign{\hrule width\hsize}
\omit&height 3pt\cr
-4&& 1 &-4 & 10 &-20 & 35 &-56 & 84 &-120 & 165 &-220 & 286\cr
-3&& 1 &-3 & 6 &-10 & 15 &-21 & 28 &-36 & 45 &-55 & 66\cr
-2&& 1 &-2 & 3 &-4 & 5 &-6 & 7 &-8 & 9 &-10 & 11\cr
-1&& 1 &-1 & 1 &-1 & 1 &-1 & 1 &-1 & 1 &-1 & 1\cr
0 && 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
\omit&height 2pt\cr}
\hrule width\hsize height.5pt
\kern4pt
\endinsert

Now let's look more closely at the values of $n\choose k$ when $n$ is
a negative integer. One way to approach these values is to use the
addition law \eq(|bc-addition|) to fill in the entries that lie
above the numbers in Table~|pascal-triangle|, thereby obtaining
Table~|pascal-triangle-up|.
For example, we must have ${-1\choose0}=1$, since
 ${@0@\choose0}
={-1\choose0}+{-1\choose-1}$ and ${-1\choose-1}=0$; then we must have
${-1\choose1}=-1$, since ${0\choose1}={-1\choose1}+{-1\choose0}$; and so on.

All these numbers are familiar. Indeed, the rows and columns
of Table~|pascal-triangle-up| appear
as columns in Table~|pascal-triangle| (but minus the minus signs).
So there must be
a connection between the values of $n\choose k$ for negative~$n$
and the values for positive~$n$. The general rule is
\begindisplay
{r \choose k}
	= (-1)^k {k-r-1 \choose k} \,, \qquad\hbox{integer $k$};
\eqno\eqref|negate-upper|
\enddisplay
it is easily proved, since
\begindisplay
r\_k&=r(r-1)\ldots(r-k+1)\cr
&=(-1)^k(-r)(1-r)\ldots(k-1-r)=(-1)^k(k-r-1)\_k
\enddisplay
when $k\ge0$, and both sides are zero when $k<0$.

Identity \thiseq\
is particularly valuable because it holds without any restriction.
(Of course, the lower index must be an integer so that the
binomial coefficients are defined.) The transformation in \thiseq\ is
called {\it"negating the upper index"}, or ``"upper negation".\qback''

But how can we remember this important formula? The other identities
we've seen\dash---symmetry, absorption, addition, etc.\dash---are pretty
simple, but this one looks rather messy. Still, there's a mnemonic
\g You call this a mnemonic? I'd~call it pneumatic\dash---\par
"!pneumathic comment"
full of air.\par It does help me remember, though.\g
that's not too bad: To negate
the upper index, we begin by writing down
$(-1)^k$, where $k$ is the lower index. (The lower index
doesn't change.) Then we immediately write $k$ again, twice, in both
lower and upper index positions. Then we negate the original upper index
by {\it subtracting\/} it from the new upper index. And we complete the job by
{\it subtracting\/}~$1$ more (always subtracting, not adding, because this is
a negation process).

Let's negate the upper index twice in succession, for practice. We get
\g(Now is a good time to do warmup exercise~|-1-choose-k|.)\g
\begindisplay \openup3pt
{r\choose k}
&=(-1)^k{k-r-1\choose k}\cr
&=(-1)^{2k}{k-(k-r-1)-1\choose k}={r\choose k}\,,
\enddisplay
\looseness=-1
so we're right back where we started. This is probably not what the
framers of the identity intended; but it's reassuring to know
\g It's also frustrating, if we're trying to get somewhere else.\g
that we haven't gone astray.

Some applications of \thiseq\ are, of course, more useful than this.
We can use upper negation, for example, to move quantities between upper and
lower index positions. The identity has a symmetric formulation,
\begindisplay
(-1)^m{-n-1\choose m}=(-1)^n{-m-1\choose n}\,,\qquad\hbox{integers $m,n\ge0$},
\eqno\eqref|bc-switch|
\enddisplay
which holds because both sides are equal to ${m+n\choose n}$.

Upper negation can also be used to derive the following interesting sum:
\begindisplay
\sum_{k \leq m} {r \choose k} (-1)^k
	&= {r \choose 0} - {r \choose 1} + \cdots +
					(-1)^m {r \choose m} \cr
	&= (-1)^m {r-1 \choose m} \,, \qquad\hbox{integer $m$.}
\eqno\eqref|bc-alt-sum|
\enddisplay
The idea is to negate the upper index, then apply
\eq(|bc-sum-both|), and negate again:
\g\vskip.5in(Here double negation helps, because we've "sandwich"ed
another operation in between.)\g
\begindisplay \openup3pt
 \sum_{k \leq m} {r \choose k} (-1)^k
	&= \sum_{k \leq m} {k-r-1 \choose k}\cr
\noalign{\smallskip}
	&= {-r+m \choose m}\cr
	&= (-1)^m {r-1 \choose m} \,.
\enddisplay
This formula gives us a partial sum
of the $r$th row of Pascal's triangle, provided that
the entries of the row have been given alternating signs.
For instance, if $r=5$ and $m=2$ the formula gives
$1 - 5 + 10 = 6 = (-1)^2 {4 \choose 2}$.

Notice that if $m \geq r$, \thiseq\ gives the alternating sum of the entire row,
and this sum is zero when $r$ is a positive integer. We proved this before,
"!Pascal's triangle, row sums"
when we expanded $(1-1)^r$ by the binomial theorem;
it's interesting to know that the "partial sums" of this expression can
also be evaluated in closed form.

How about the simpler partial sum,
\begindisplay
\sum_{k\le m}{n\choose k}={n\choose 0}+{n\choose1}+\cdots+{n\choose m}\,;
\eqno\eqref|bc-partial|
\enddisplay
surely if we can evaluate the corresponding sum with alternating signs,
we ought to be able to do this one? But no; there is no closed form
for the partial sum of a row of Pascal's triangle. We can do columns\dash---%
that's \eq(|bc-sum-upper|)\dash---but not rows. Curiously, however,
there is a way to partially sum the row elements if they have been multiplied
by their distance from the center:
\begindisplay
\sum_{k\le m}{r\choose k}\Bigl({r\over 2}-k\Bigr)={m+1\over2}{r\choose m+1},
 \qquad\hbox{integer $m$}.
\eqno\eqref|bc-partial-k|
\enddisplay
(This formula is easily verified by induction on $m$.)
The relation between these partial sums
with and without the factor of~$(r/2-k)$ in the summand
is analogous to the relation between the "integral"s
\begindisplay
 \int_{-\infty}^\alpha  x e^{-x^2} dx
		= - {\textstyle\half} e^{-\alpha^2}\quad\And\quad
	\int_{-\infty}^\alpha e^{-x^2} dx \,.
\enddisplay
The apparently more complicated integral on the left,
with the factor of~$x$, has a closed form,
while the simpler-looking integral on the right,
without the factor, has none.
\g(Well, the right-hand integral is ${}\kern2pt\half\sqrt\pi
(1+\mathop{\rm erf}\alpha)$, a constant plus a multiple of
the ``"error function"'' of~$\alpha$, if we're willing to accept that
as a closed form.)\g
 Appearances can be deceiving. "!cliches"

Near the end of this chapter, we'll study a method by which it's possible
to determine whether or not there is a closed form for the partial
sums of a given series involving binomial coefficients, in a fairly general
setting. This method is capable of discovering identities \eq(|bc-alt-sum|) and
\eq(|bc-partial-k|), and it also will tell us that \eq(|bc-partial|)
is a dead end.

Partial sums of the binomial series lead to a curious relationship of another
kind:
\begindisplay
\sum_{k\le m}{m{+}r\choose k}x^ky^{m-k}=
 \sum_{k\le m}{-r\choose k}(-x)^k(x+y)^{m-k}\,,\,\enspace\hbox{integer $m$}.
\eqno\eqref|partial-binomial|
\enddisplay
This identity isn't hard to prove by induction: Both sides are zero when
$m<0$ and~$1$ when $m=0$. If we let $S_m$ stand for the
sum on the left, we can apply the addition formula \eq(|bc-addition|)
and show easily that
\begindisplay \openup 4pt
S_m=
\sum_{k\le m}{m-1+r\choose k}x^ky^{m-k}
+\sum_{k\le m}{m-1+r\choose k-1}x^ky^{m-k}\,;
\enddisplay
and
\begindisplay
&\sum_{k\le m}{m-1+r\choose k}x^ky^{m-k}=yS_{m-1}+{m-1+r\choose m}x^m\,,\cr
&\sum_{k\le m}{m-1+r\choose k-1}x^ky^{m-k}=xS_{m-1}\,,\cr
\enddisplay
when $m>0$. Hence
\begindisplay
S_m=(x+y)S_{m-1}+{-r\choose m}(-x)^m\,,
\enddisplay
and this recurrence is satisfied also by the right-hand side of \thiseq.
By induction, both sides must be equal; QED.

But there's a neater proof. When $r$ is an integer in the range $0\ge r\ge-m$,
the binomial theorem tells us that both sides of \thiseq\ are
$(x+y)^{m+r}y^{-r}$. And since both sides are polynomials in~$r$ of degree
$m$~or less, agreement at $m+1$ different values is enough (but just
barely!) to prove equality in general.

It may seem foolish to have an identity where one sum equals another. Neither
side is in closed form. But sometimes one side turns out to be easier to
evaluate than the other. For example, if we set $x=-1$ and $y=1$, we get
\begindisplay
\sum_{k\le m}{m+r\choose k}(-1)^k={-r\choose m}\,,\qquad\hbox{integer $m\ge0$},
\enddisplay
an alternative form of identity \eq(|bc-alt-sum|). And if we set $x=y=1$
and $r=m+1$, we get
\begindisplay
\sum_{k\le m}{2m+1\choose k}=\sum_{k\le m}{m+k\choose k}2^{m-k}\,.
\enddisplay
The left-hand side sums just half of the binomial coefficients with upper
index $2m+1$, and these are equal to their counterparts in the other half
because Pascal's triangle has left-right symmetry. Hence the left-hand side
is just $\half 2^{2m+1}=2^{2m}$. This yields a formula that is quite
unexpected, "!unexpected sum"
\g(There's a nice combinatorial proof of this formula~[|world-series|].)\g
\begindisplay
\sum_{k\le m}{m+k\choose k}2^{-k}=2^m\,,\qquad\hbox{integer $m\ge0$}.
\eqno\eqref|half/2|
\enddisplay
Let's check it when $m=2$:\quad ${\2\choose0}+\half{3\choose1}+{1\over4}
 {4\choose2}=1+{3\over2}+{6\over4}=4$. Astounding.

\smallbreak
So far we've been looking either at binomial coefficients
by themselves or at sums of terms in which there's only one binomial coefficient
per term. But many of the challenging problems we face
involve products of two or more binomial coefficients,
so we'll spend the rest of this section considering how to
deal with such cases.

Here's a handy rule that often helps to simplify the
product of two binomial coefficients:
\begindisplay
{r \choose m} {m \choose k}
	= {r \choose k} {r-k \choose m-k} \,,
					\qquad\hbox{integers $m$, $k$.}
\eqno\eqref|bc-tc|
\enddisplay
We've already seen the
special case~$k=1$; it's the absorption identity~\eq(|bc-absorb-k|).
Although both sides of \thiseq\ are products of binomial coefficients,
one side often is easier to sum because of interactions with the
rest of a formula. For example, the left side uses $m$ twice,
the right side uses it only once. Therefore we usually want to replace
${r\choose m}{m\choose k}$ by
${r \choose k} {r-k \choose m-k}$ when summing on~$m$.

Equation \thiseq\ holds primarily because of cancellation between
$m!$'s in the factorial representations of $r\choose m$ and $m\choose k$.
If all variables are integers and $r\ge m\ge k\ge0$, we have
\begindisplay \openup3pt
{r \choose m} {m \choose k}
	&= {r!\over m!\,(r-m)!} \, {m!\over k!\,(m-k)!} \cr
	&= {r!\over k!\,(m-k)!\,(r-m)!} \cr
	&= {r!\over k!\,(r-k)!} \, {(r-k)!\over (m-k)!\,(r-m)!}
	 = {r \choose k} {r-k \choose m-k} \,.
\enddisplay
That was easy.
\g Yeah, right.\g
 Furthermore, if $m<k$ or $k<0$, both sides of \thiseq\ are
zero; so the identity holds for all integers $m$~and~$k$.
Finally, the polynomial argument extends its validity to all real~$r$.

A binomial coefficient ${r\choose k}=r!/(r-k)!\,k!$
 can be written
in the form $(a+b)!/a!\,b!$ after a suitable renaming of variables.
Similarly, the quantity in the middle of the derivation above,
$r!/k!\,(m-k)!\,(r-m)!$,
can be written in the form $(a+b+c)!/a!\,b!\,c!$.
This is a ``"trinomial" coefficient,\qback'' which arises in the
``trinomial theorem'':
\begindisplay \openup3pt
(x+y+z)^n
	&= \sum\twoconditions{0 \leq a,b,c \leq n}{a+b+c = n}
		\!{(a+b+c)!\over a!\,b!\,c!} x^a y^b z^c \cr
	&= \sum\twoconditions{0 \leq a,b,c \leq n}{a+b+c = n}
		{a+b+c \choose b+c}{b+c \choose c} x^a y^b z^c \,.
\enddisplay
So ${r \choose m} {m \choose k}$ is really a trinomial coefficient in disguise.
\g\vskip-60pt
\noindent\llap{``}Excogitavi autem olim mirabilem regulam pro numeris coefficientibus
potestatum, non tantum a binomio\/ $x+y$, sed et a trinomio\/ $x+y+z$,
imo a polynomio quocunque, ut data potentia gradus cujuscunque v.\ gr.\
decimi, et potentia in ejus valore comprehensa, ut\/~$x^5y^3z^2$, possim
statim assignare numerum coefficientem, quem habere debet, sine ulla
Tabula jam calculata.''\par\hfill\kern-4pt
 \dash---G.\thinspace W\kern-1pt.\thinspace"Leibniz"~[|leibniz|]\g
Trinomial coefficients pop up occasionally in applications, and we can
conveniently write them as