chap5.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

&	= r {r-1 \choose k} \,.&\qquad\hbox{(by symmetry)}
\enddisplay

\looseness=-1
But wait a minute.
We've claimed that the identity holds
for {\it all\/} real~$r$,
yet the derivation we just gave holds only
when $r$ is a positive integer.
(The upper index $r-1$ must be
a nonnegative integer if we're
to use the symmetry property \eq(|bc-symmetry|) with impunity.)
Have we been "cheating"?
No. \g(Well, not here anyway.)\g
It's true that the derivation is valid only for positive integers~$r@$;
but we can claim that the identity holds for all values of~$r$,
because both sides of \thiseq\ are polynomials in~$r$ of degree~$k+1$.
A nonzero polynomial of degree~$d$ or less can have at most $d$~distinct zeros;
therefore
the difference of two such polynomials, which also has degree~$d$ or less,
cannot be zero at more than $d$~points unless it is identically zero.
In other words, if two polynomials of degree~$d$ or less agree at more than
$d$ points, they must agree everywhere. We have shown that
$(r-k) {r \choose k}=r {r-1 \choose k}$ whenever $r$ is a positive
integer; so these two polynomials agree at infinitely many points, and
they must be identically equal.

The proof technique in the previous paragraph,
which we will call the {\it"polynomial argument"},
is useful for extending many identities from integers to reals;
we'll see it again and again. Some equations, like the
symmetry identity \eq(|bc-symmetry|),
are not identities between polynomials, so we can't always use
this method. But many identities do have the necessary form.

For example, here's another polynomial identity, perhaps the most
important binomial identity of all, known as the {\it"addition formula"}:
\begindisplay
{r \choose k}
	= {r-1 \choose k} + {r-1 \choose k-1} \,, \qquad\hbox{integer $k$.}
\eqno\eqref|bc-addition|
\enddisplay
When $r$ is a positive integer,
the addition formula tells us that every number in Pas\-cal's triangle
is the sum of two numbers in the previous row,
one directly above it and the other just to the left.
And the formula applies also when $r$ is negative, real, or complex;
the only restriction is that $k$ be an integer, so that
the binomial coefficients are defined.

One way to prove the addition formula is to assume that $r$
is a positive integer and to use the
"combinatorial interpretation".
Recall that $r \choose k$ is the number of possible
$k$-element subsets chosen from an $r$-element set.
If we have a set of $r$~"eggs" that includes exactly one bad egg,
there are $r\choose k$ ways to select $k$ of the eggs. Exactly
$r-1\choose k$ of these selections involve nothing but good eggs;
and $r-1\choose k-1$ of them contain the bad egg, because such
selections have $k-1$ of the $r-1$ good eggs.
Adding these two numbers together gives~\eq(|bc-addition|).
This derivation
assumes that $r$ is a positive integer, and that $k\ge0$.
But both sides of the identity are zero when $k<0$, and the polynomial argument
establishes \thiseq\ in all remaining cases.

We can also derive \thiseq\ by adding together the two absorption identities
\eq(|bc-absorb-r-k|)~and~\eq(|bc-absorb-k|):
\begindisplay
(r-k) {r \choose k} + k {r \choose k}
= r {r-1 \choose k} + r {r-1 \choose k-1}\,;
\enddisplay
the left side is $r{r\choose k}$, and we can divide through by~$r$.
This derivation is valid for everything but~$r=0$,
and it's easy to check that remaining case.

Those of us who tend not to discover such slick proofs,
or who are otherwise into tedium,
might prefer to derive \thiseq\ by
a straightforward manipulation of the definition.
If $k>0$,
\begindisplay \openup3pt
{r-1 \choose k} + {r-1 \choose k-1}
	&= {(r-1)\_k\over k!}
		+ {(r-1)\_{k-1}\over (k-1)!} \cr
	&= {(r-1)\_{k-1}\,(r-k)\over k!}
		+ {(r-1)\_{k-1}\,k\over k!} \cr
	&= {(r-1)\_{k-1}\,r\over k!} ={r\_k\over k!}={r \choose k} \,.
\enddisplay
Again, the cases for $k\le0$ are easy to handle.

We've just seen three rather different proofs of the addition formula.
This is not surprising;
binomial coefficients have many useful properties,
several of which are bound to lead to proofs
of an identity at hand.

The addition formula is essentially a recurrence for the numbers
of Pascal's triangle, so we'll see that it is especially useful for proving other
identities by induction. We can also get a new identity immediately
by unfolding the recurrence. For example,
\begindisplay \openup4pt
{5 \choose 3}
	&= {4 \choose 3} + {4 \choose 2} \cr
	&= {4 \choose 3} + {3 \choose 2} + {3 \choose 1} \cr
	&= {4 \choose 3} + {3 \choose 2} + {2 \choose 1}
			+ {2 \choose 0} \cr
	&= {4 \choose 3} + {3 \choose 2} + {2 \choose 1}
			+ {1 \choose 0} + {1 \choose -1} \,.
\enddisplay
Since ${1 \choose -1} = 0$, that term disappears and we can stop. This
method yields the general formula
\begindisplay
\sum_{k \leq n} {r+k \choose k}
	&= {r \choose 0} + {r+1 \choose 1} + \cdots + {r+n \choose n}\cr
	&= {r+n+1 \choose n} \,, \qquad\hbox{integer $n$.}
\eqno\eqref|bc-sum-both|
\enddisplay
Notice that we don't need the lower limit~$k \geq 0$ on the index of summation,
"!parallel summation"
because the terms with~$k<0$ are~zero.

This formula expresses one binomial coefficient as the sum of others
whose upper and lower indices stay the same distance apart.
We found it by repeatedly expanding
the binomial coefficient with the smallest lower index: first
$5 \choose 3$, then $4 \choose 2$, then $3 \choose 1$, then $\2 \choose 0$.
What happens if we unfold the other way, repeatedly
expanding the one with largest lower index? We get
\begindisplay \openup4pt
{5 \choose 3}
	&= {4 \choose 3} + {4 \choose 2} \cr
	&= {3 \choose 3} + {3 \choose 2} + {4 \choose 2} \cr
	&= {2 \choose 3} + {2 \choose 2} + {3 \choose 2}
			+ {4 \choose 2} \cr
	&= {1 \choose 3} + {1\choose 2} + {2 \choose 2} + {3 \choose 2}
			+ {4 \choose 2} \cr
	&= {0 \choose 3} + {0 \choose 2} + {1 \choose 2}
			+ {2 \choose 2} + {3 \choose 2} + {4 \choose 2} \,.
\enddisplay
Now $0 \choose 3$ is zero
(so are $0 \choose 2$ and~$1 \choose 2$, but these make the identity nicer),
and we can spot the general pattern:
\begindisplay
\sum_{0 \leq k \leq n} {k \choose m}
	&= {0 \choose m} + {1 \choose m} + \cdots + {n \choose m}\cr
	&= {n+1 \choose m+1} \,, \qquad\hbox{integers $m,n \geq 0$.}
\eqno\eqref|bc-sum-upper|
\enddisplay
This identity, which we call {\it"summation on the upper index"},
"!upper summation"
expresses a binomial coefficient as the sum of others
whose lower indices are constant.
In this case the sum needs the lower limit~$k \geq 0$,
because the terms with~$k<0$ {\it aren't\/} zero.
Also, $m$~and~$n$ can't in general be negative.

Identity~\eq(|bc-sum-upper|) has an interesting "combinatorial interpretation".
If we want to choose $m+1$ tickets from a set of $n+1$ tickets numbered
$0$~through~$n$, there are $k\choose m$ ways to do this when the largest
ticket selected is number~$k$.

We can prove both \eq(|bc-sum-both|)~and~\eq(|bc-sum-upper|)
by induction using the addition formula,
but we can also prove them from each other.
For example, let's prove~\eq(|bc-sum-both|) from~\eq(|bc-sum-upper|);
our proof will illustrate
some common binomial coefficient manipulations.
Our general plan will be to
massage the left side $\sum {r+k \choose k}$ of~\eq(|bc-sum-both|)
so that it
looks like the left side $\sum {k \choose m}$ of~\eq(|bc-sum-upper|);
then we'll invoke that identity,
replacing the sum by a single binomial coefficient;
finally we'll transform that coefficient
into the right side of~\eq(|bc-sum-both|).

We can assume for convenience
that $r$~and~$n$ are nonnegative integers;
the general case of \eq(|bc-sum-both|) follows from this special case,
by the polynomial argument.
Let's write $m$ instead of~$r$, so
that this variable looks more like a nonnegative integer. 
The plan can now be carried out systematically as follows:
\begindisplay \openup 3pt
\sum_{k \leq n} {m+k \choose k}
	&= \sum_{-m \leq k \leq n}  {m+k \choose k} \cr
	&= \sum_{-m \leq k \leq n}  {m+k \choose m} \cr
	&= \sum_{0 \leq k \leq m+n} {k \choose m} \cr
	&= {m+n+1 \choose m+1}
\;	 =\;{m+n+1 \choose n} \,.
\enddisplay
Let's look at this derivation blow by blow.
The key step is in the second line, where we apply the symmetry
law \eq(|bc-symmetry|) to replace $m+k\choose k$ by $m+k\choose m$.
We're allowed to do this only when $m+k\ge0$, so our first step
restricts the
range of~$k$ by discarding the terms with~$k<-m$.
(This is legal because those terms are zero.)
Now we're almost ready to apply \eq(|bc-sum-upper|); the third
line sets this up, replacing $k$ by $k-m$ and tidying up the
range of summation.
This step, like the first, merely plays around with $\sum$-notation.
Now $k$~appears by itself in the upper index
and the limits of summation are in the proper form,
so the fourth line applies~\eq(|bc-sum-upper|). One more use of symmetry
finishes the job.

Certain sums that we did in Chapters 1 and~2 were actually special cases
of \eq(|bc-sum-upper|), or disguised versions of this identity.
For example, the case~$m=1$
gives the sum of the nonnegative integers up through~$n$:
\begindisplay
 {0 \choose 1} + {1 \choose 1} + \cdots + {n \choose 1}
 	= 0 + 1 + \cdots + n
&	= {(n+1)n\over 2}
&	= {n+1 \choose 2}\,.
\enddisplay
And the general case is equivalent to Chapter 2's rule
\begindisplay
\sum_{0\le k\le n} k\_m={(n+1)\_{m+1}\over m+1},
	\qquad\hbox{integers $m,n\ge0$},
\enddisplay
if we divide both sides of this formula by $m!$. In fact, the addition
formula \eq(|bc-addition|) tells us that
\begindisplay
\Delta\biggl({x\choose m}\biggr)
={x+1\choose m}-{x\choose m}
={x\choose m-1}\,,
\enddisplay
if we replace $r$ and $k$ respectively by $x+1$ and $m$.
Hence the methods of Chapter 2 give us the handy
"indefinite summation" formula
\begindisplay
\sum{x\choose m}\,\delta x={x\choose m+1}+C\,.
\eqno
\enddisplay

Binomial coefficients get their name from the {\it "binomial theorem"},
which deals with powers of the binomial expression $x+y$.
\g\noindent\llap{``}At the age of twenty-one he~[\hbox{Moriarty}] wrote a treatise upon the
Binomial Theorem, which has had a European vogue. On the strength of it,
he won the Mathematical Chair at one of our smaller Universities.''\par
\hfill\dash---S. "Holmes"~[|holmes-final|]\g
Let's look at the smallest cases of this theorem:
\begindisplay \openup2pt
(x+y)^0	&=1x^0y^0\cr
(x+y)^1	&=1x^1y^0&+1x^0y^1\cr
(x+y)^2	&=1x^2y^0&+2x^1y^1&+1x^0y^2\cr
(x+y)^3	&=1x^3y^0&+3x^2y^1&+3x^1y^2&+1x^0y^3\cr
(x+y)^4	&=1x^4y^0&+4x^3y^1&+6x^2y^2&+4x^1y^3&+1x^0y^4\,.\cr
\enddisplay
It's not hard to see why these coefficients
are the same as the numbers in Pascal's triangle:
When we expand the product
\begindisplay
 (x+y)^n
	= \overbrace{(x+y)(x+y)\ldots(x+y)}^{n \rm\ factors} \,,
\enddisplay
every term is itself the product of $n$~factors, each either an $x$~or~$y$.
The number of such terms with $k$~factors of~$x$ and $n-k$~factors of~$y$
is the coefficient of~$x^k y^{n-k}$ after we combine like terms. And
this is exactly the number of ways to choose $k$ of the~$n$~binomials
from which an~$x$ will be contributed;
that is, it's~$n \choose k$.

Some textbooks leave the quantity "$0^0$" undefined, because the
functions $x^0$ and $0^x$ have different limiting values when $x$
decreases to~$0$.
But this is a mistake. We must define
\begindisplay
x^0=1\,,\qquad\hbox{for all~$x$},
\enddisplay
if the binomial theorem is to be valid when $x=0$, $y=0$,
and/or $x=-y$.
The theorem is too important to be arbitrarily restricted! By contrast,
the function $0^x$ is quite unimportant.
(See [|knuth-tnn|] for further discussion.)

But what exactly is the binomial theorem? In its full glory it is
the following identity:
\begindisplay
(x+y)^r
	= \sum_k {r \choose k} x^k y^{r-k} \,,
	\qquad\tworestrictions{integer $r \geq 0$}{or $\vert x/y\vert < 1$.}
\eqno\eqref|bin-thm-xy|
\enddisplay
The sum is over all integers $k$; but it is really a finite sum
when $r$~is a nonnegative integer, because all terms are zero
except those with $0 \leq k \leq r$.
On the other hand, the theorem is also valid when $r$ is negative,
or even when $r$ is an arbitrary real or complex number.
In such cases the sum really is infinite,
and we must have $\vert x/y\vert < 1$
to guarantee the sum's absolute convergence.

Two special cases of the binomial theorem are worth special attention,
even though they are extremely simple. If $x=y=1$ and $r=n$ is nonnegative,
we get
\begindisplay
2^n={n\choose0}+{n\choose1}+\cdots+{n\choose n}\,,\qquad\hbox{integer $n\ge0$.}
\enddisplay
This equation tells us that row $n$ of Pascal's triangle sums to $2^n$.
"!Pascal's triangle, row sums"
 And
when $x$ is $-1$ instead of~$+1$, we get
\begindisplay
0^n={n\choose0}-{n\choose1}+\cdots+(-1)^n{n\choose n}\,,
\qquad\hbox{integer $n\ge0$.}
\enddisplay
For example, $1-4+6-4+1=0$;
the elements of row $n$ sum to zero if we give them
alternating signs, except in the top row (when $n=0$ and $0^0=1$).

When $r$ is not a nonnegative integer, we most often use the binomial theorem
in the special case $y=1$. Let's state this special case explicitly,
writing $z$ instead of $x$ to emphasize the fact that an arbitrary
complex number can be involved here:
\begindisplay
(1+z)^r
	= \sum_k {r \choose k} z^k \,,
			\qquad\hbox{$\vert z\vert < 1$.}
\eqno\eqref|bin-thm-z|
\enddisplay
The general formula in \eq(|bin-thm-xy|) follows from this one if we set $z=x/y$