chap5.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

{r\choose k}&={r\over k}{r-1\choose k-1}\,,
 \quad}\hfill{\hbox{integer $k\ne0$.}\\{absorption/extraction}
{r\choose k}&={r-1\choose k}+{r-1\choose k-1}\,,
 \quad}\hfill{\hbox{integer $k$.}\\{addition/induction}
{r\choose k}&=(-1)^k{k-r-1\choose k}\,,
 \quad}\hfill{\hbox{integer $k$.}\\{upper negation}
{r\choose m}{m\choose k}&={r\choose k}{r-k\choose m-k}\,,
 \quad}\hfill{\hbox{integers $m,k$.}\\{trinomial revision}
\sum_k{r\choose k}x^ky^{r-k}&=(x+y)^r\,,
 \quad}\hfill{\tworestrictions
 {integer $r\ge0$,}{or $\vert x/y\vert<1$.}\\{binomial theorem}
\noalign{\vskip-2pt}
\sum_{k\le n}{r+k\choose k}&={r+n+1\choose n}\,,
 \quad}\hfill{\hbox{integer $n$.}\\{parallel summation}
\noalign{\vskip-4pt}
\sum_{0\le k\le n}{k\choose m}&={n+1\choose m+1}\,,
 \quad}\hfill{\tworestrictions
 {integers}{$m,n\ge0$.}\\{upper summation}
\noalign{\vskip-2pt}
\sum_{k}{r\choose k}{s\choose n-k}&={r+s\choose n}\,,
 \quad}\hfill{\hbox{integer $n$.}\\{Vandermonde convolution}
\enddisplay
\hrule width\hsize height.5pt
\kern4pt
\global\let\thiseq=\savethiseq
\endinsert

We can also simplify the boundary conditions by summing over all $k\ge0$;
the terms for $k>m$ are zero.
The sum that's left isn't so intimidating:
\begindisplay
 \sum_{k\ge0}{n-k \choose m-k} \,.
\enddisplay
It's similar to the one in identity~\eq(|bc-sum-both|),
because the index~$k$ appears twice with the same sign.
But here it's $-k$ and in~\eq(|bc-sum-both|) it's not.
The next step should therefore be obvious; there's only one reasonable
thing to do:
\begindisplay
 \sum_{k\ge0}{n-k \choose m-k}
&= \sum_{m-k\ge0}{n-(m-k) \choose m-(m-k)}\cr
&=\sum_{k \leq m} {n-m+k \choose k} \,.
\enddisplay
And now we can apply the parallel summation identity, \eq(|bc-sum-both|):
\begindisplay
 \sum_{k \leq m} {n-m+k \choose k}
	= {(n-m)+m+1 \choose m}
	= {n+1 \choose m} \,.
\enddisplay

Finally we reinstate the $n \choose m$ in the denominator
that we removed from the sum earlier,
and then apply~\eq(|bc-absorb-r-k|)
to get the desired closed form:
\begindisplay
 {n+1 \choose m} \bigg/ {n \choose m}
	= {n+1\over n+1-m} \,.
\enddisplay
This derivation actually works for any real value of~$n$,
as long as no division by zero occurs;
that is, as long as $n$~isn't one of the integers $0$,~$1$, \dots,~$m-1$.

The more complicated the derivation,
the more important it is to check the answer.
This one wasn't too complicated but we'll check anyway.
In the small case $m=2$ and $n=4$ we have
\begindisplay
 {2 \choose 0} \bigg/ {4 \choose 0}
		\;+\; {2 \choose 1} \bigg/ {4 \choose 1}
		\;+\; {2 \choose 2} \bigg/ {4 \choose 2}
	= 1 + {1\over 2} + {1\over 6}
	= {5\over 3} \,;
\enddisplay
yes, this agrees perfectly with our closed form $(4+1)/(4+1-2)$.

\subhead Problem 2: From the literature of "sorting".

Our next sum appeared way back in ancient times (the early 1970s)
before people were fluent with binomial coefficients. A paper that
introduced an improved "merging" technique [|jones|] concludes with
the following remarks: ``It can be shown that the expected number
of saved transfers \dots\ is given by the expression
\begindisplay
 T = \sum_{r=0}^n \,r\,\, {_{m-r-1} C_{m-n-1}\over _m C_n}
\enddisplay
Here $m$ and $n$ are as defined above, and $_mC_n$ is the symbol for
the number of combinations of $m$ objects taken $n$ at a time. \dots\thinspace
The author is grateful to the "referee" for reducing a more complex equation
for expected transfers saved to the form given here.''

We'll see that this is definitely not a final answer to the author's
problem. It's not even a midterm answer.
\g Please, don't remind me of the midterm.\g

First we should translate the sum into something we can work with;
the ghastly notation $_{m-r-1} C_{m-n-1}$ is enough to stop anybody,
"!notation, ghastly"
save the enthusiastic referee~(please). "!Youngman, Henny" % "take my wife"
In our language we'd write
\begindisplay
 T = \sum_{k=0}^n\, k {m-k-1 \choose m-n-1} \bigg/
 {m \choose n} \,,\qquad\hbox{integers $m > n \geq 0$.}
\enddisplay
The binomial coefficient in the denominator
doesn't involve the index of summation,
so we can remove it and work with the new sum
\begindisplay
 S = \sum_{k=0}^n \,k {m-k-1 \choose m-n-1} \,.
\enddisplay

\looseness=-1
What next?
The index of summation appears
in the upper index of the binomial coefficient but not in the lower index.
So if the other~$k$ weren't there,
we could massage the sum and apply
summation on the upper index~\eq(|bc-sum-upper|).
With the extra~$k$, though, we can't.
If we could somehow absorb that~$k$ into the binomial coefficient,
using one of our absorption identities,
we could then sum on the upper index.
Unfortunately those identities don't work here.
But if the $k$ were instead $m-k$,
we could use absorption identity~\eq(|bc-absorb-k|):
\begindisplay
 (m-k) {m-k-1 \choose m-n-1}
	= (m-n) {m-k \choose m-n} \,.
\enddisplay

So here's the key: We'll
rewrite~$k$ as~$m - (m-k)$
and split the sum~$S$ into two sums:
\begindisplay \openup4pt
\sum_{k=0}^n \,k {m-k-1 \choose m-n-1}
	&=\sum_{k=0}^n \,\bigl(m-(m-k)\bigr) {m-k-1 \choose m-n-1}\cr
	&=\sum_{k=0}^n \,m{m-k-1 \choose m-n-1}
	        -\sum_{k=0}^n\, (m-k){m-k-1 \choose m-n-1}\cr
	&=m\sum_{k=0}^n {m-k-1 \choose m-n-1}
	        -\sum_{k=0}^n (m-n){m-k \choose m-n}\cr
\noalign{\smallskip}
	&=mA-(m-n)B\,,
\enddisplay
where
\begindisplay
A&=\sum_{k=0}^n{m-k-1\choose m-n-1}\,,\qquad
B&=\sum_{k=0}^n{m-k\choose m-n}\,.
\enddisplay

The sums $A$ and $B$ that remain are none other than our old friends
in which the upper index varies while the lower index stays fixed.
Let's do $B$ first, because it looks simpler. A little bit of massaging
is enough to make the summand match the left side of \eq(|bc-sum-upper|):
\begindisplay
\sum_{0 \leq k \leq n} {m-k \choose m-n}
 &= \sum_{0\le m-k\le n}{m-(m-k)\choose m-n}\cr
 &= \sum_{m-n\le k\le m}{k\choose m-n}\cr
 &= \sum_{0\le k\le m}{k\choose m-n}\,.\cr
\enddisplay
In the last step we've included the terms
with $0 \leq k < m-n$ in the sum;
they're all zero,
because the upper index is less than the lower.
Now we sum on the upper index, using \eq(|bc-sum-upper|), and get
\begindisplay
B=\sum_{0 \leq k \leq m} {k \choose m-n} = {m+1 \choose m-n+1} \,.
\enddisplay

The other sum $A$ is the same, but with $m$ replaced by $m-1$. Hence
we have a closed form for the given sum~$S$, which can be further simplified:
\begindisplay \openup7pt
S=mA-(m-n)B&=m{m\choose m-n}-(m-n){m+1\choose m-n+1}\cr
&=\left(m-(m-n){m+1\over m-n+1}\right){m\choose m-n}\cr
&=\left(n\over m-n+1\right){m\choose m-n}\,.\cr
\enddisplay
And this gives us a closed form for the original sum:
\begindisplay \openup5pt
 T &= S\,\bigg/ {m \choose n}\cr
	&= {n\over m-n+1} {m \choose m-n} \bigg/ {m \choose n}\cr
	&= {n\over m-n+1} \,.
\enddisplay
Even the referee can't simplify this.

Again we use a small case to check the answer.
When $m=4$ and $n=2$, we have
\begindisplay
\textstyle T = 0 \cdt {3 \choose 1} \big/ {4 \choose 2}
		\,+\, 1 \cdt {\2 \choose 1} \big/ {4 \choose 2}
		\,+\, 2 \cdt {1 \choose 1} \big/ {4 \choose 2}
	= 0 + {2\over 6} + {2\over 6}
	= {2\over 3} \,,
\enddisplay
which agrees with our formula $2/(4-2+1)$.

\subhead Problem 3: From an old exam.

Let's do one more sum that involves a single binomial coefficient. This
one, unlike the last, originated in the halls of academia; it was a problem
\g Do old exams ever~die?\g
on a take-home test. We want the value of $Q_{1000000}$, when
\begindisplay
 Q_n = \sum_{k \leq 2^n} {2^n - k \choose k} (-1)^k \,,
					\qquad\hbox{integer $n \geq 0$.}
\enddisplay
This one's harder than the others; we can't apply {\it any\/} of the
identities we've seen so far. And we're faced with
 a sum of $2^{1000000}$ terms, so we can't just add them up.
The index of summation~$k$ appears in both indices, upper and lower,
but with opposite signs.
Negating the upper index doesn't help, either;
it removes the factor of~$(-1)^k \bex$, but
it introduces a~$2k$ in the upper index.

When nothing obvious works,
we know that it's best to look at small cases.
If we can't spot a pattern and prove it by induction,
at least we'll have some data for checking our results.
Here are the nonzero terms and their sums
for the first four values of~$n$.
\begindisplay\def\preamble{\bigstrut\hfil$##$\hfil\ &\vrule##\ &&${}##$\hfil}%
 \setbox\bigstrutbox=\hbox{\vrule height13pt depth6pt width0pt}\offinterlineskip
n&&	&	& \quad Q_n \cr
\omit&height 2pt\cr
\noalign{\hrule}
\omit&height 2pt\cr
0&&\,{1\choose0}&=1&=\,1\cr
1&&\,{2\choose0}-{1\choose1}&=1-1&=\,0\cr
2&&\,{4\choose0}-{3\choose1}+{2\choose2}&=1-3+1&=-1\cr
3&&\,{8\choose0}-{7\choose1}+{6\choose2}-{5\choose3}+{4\choose4}
 &=1-7+15-10+1&=\,0\cr
\enddisplay
We'd better not try the next case, $n=4$;
the chances of making an arithmetic error are too high.
(Computing terms like $12@\choose 4$ and $11@\choose 5$ by hand,
let alone combining them with the others,
is worthwhile only if we're desperate.)

So the pattern starts out $1$,~$0$, $-1$,~$0$.
Even if we knew the next term or two,
the closed form wouldn't be obvious.
But if we could find and prove a recurrence for~$Q_n$
we'd probably be able to guess and prove its closed form.
To find a recurrence,
we need to relate~$Q_n$ to~$Q_{n-1}$ (or to~$Q_{\rm smaller\ values}$);
but to do this
we need to relate a term like $128 - 13 \choose 13$, which arises when
$n=7$ and $k=13$,
to terms like $64 - 13 \choose 13$.
This doesn't look promising;
we don't know any neat relations between entries in Pascal's triangle
that are 64~rows apart.
The addition formula,
our main tool for induction proofs,
only relates entries that are one row apart.

But this leads us to a key observation:
There's no need to deal with entries that are $2^{n-1}$ rows apart.
The variable~$n$ never appears by itself,
it's always in the context~$2^n \bex$.
So the~$2^n$ is a red herring!
\g Oh, the sneakiness of the instructor who set that exam.\g
If we replace~$2^n$ by~$m$, all we need to do is
find a closed form for the more general (but easier) sum
\begindisplay
 R_m = \sum_{k \leq m} {m-k \choose k} (-1)^k \,,
					\qquad\hbox{integer $m \geq 0$;}
\enddisplay
then we'll also have a closed form for $Q_n = R_{2^n}$.
And there's a good chance that the addition formula
will give us a recurrence for the sequence~$R_m$.

Values of $R_m$ for small $m$ can be read from Table |pascal-triangle|,
if we alternately
add and subtract values that appear in a southwest-to-northeast
diagonal. The results are:
\begindisplay \let\preamble=\tablepreamble
m&&0&1&2&3&4&5&6&7&8&9&10\cr
\noalign{\hrule}
R_m&& 1 & 1 & 0 &-1 & -1 & 0 & 1 & 1 & 0 & -1 & -1\cr
\enddisplay
There seems to be a lot of cancellation going on.

Let's look now at the formula for $R_m$ and see if it defines a recurrence.
Our strategy is to apply the addition formula~\eq(|bc-addition|) and to find
sums that
 have the form $R_k$ in the resulting expression, somewhat as
we did in the "perturbation" method of Chapter~2:
\begindisplay \openup2pt
R_m	&= \sum_{k \leq m} {m-k \choose k} (-1)^k \cr
	&= \sum_{k \leq m} {m-1-k \choose k} (-1)^k
		\;+\; \sum_{k \leq m} {m-1-k \choose k-1} (-1)^k \cr
	&= \sum_{k \leq m} {m-1-k \choose k} (-1)^k
		\;+\; \sum_{k+1 \leq m} {m-2-k \choose k}
								(-1)^{k+1} \cr
\noalign{\smallskip}
	&= \sum_{k \leq m-1}{m-1-k \choose k} (-1)^k
					\;+\; {-1 \choose m} (-1)^m \cr
\noalign{\vskip-2pt}
	&\hskip60pt
		-\; \sum_{k \leq m-2} {m-2-k \choose k} (-1)^k
					\;-\; {-1 \choose m-1} (-1)^{m-1} \cr
\noalign{\vskip2pt}
	&= R_{m-1} \,+\, (-1)^{2m} \,-\, R_{m-2} \,-\, (-1)^{2(m-1)}
	 = R_{m-1} \,-\, R_{m-2}\,.
\enddisplay
(In the next-to-last step we've used the formula
${-1 \choose m} = (-1)^m$, which we know is true when $m\ge0$.)
\g Anyway those of us who've done warmup exercise~|-1-choose-k| know it.\g
This derivation is valid for~$m \geq 2$.

From this recurrence we can generate values of~$R_m$ quickly,
and we soon perceive that the sequence is periodic. Indeed,
\begindisplay
 R_m=\left\{\,\vcenter{\baselineskip12.5pt
		\halign{$\hfil#\hfil$\cr 1\cr 1\cr 0\cr -1\cr -1\cr 0\cr}}
	\right.\qquad\hbox{if $m \bmod 6$}
    =\left\{\,\vcenter{\baselineskip12.5pt
		\halign{$\hfil#\hfil$\cr 0\cr 1\cr 2\cr 3\cr 4\cr 5\cr}}
	\right.\,.
\enddisplay
The proof by induction is by inspection. Or, if we must give a more
academic proof, we can unfold the r