5.1 BASIC IDENTITIES 167
and this recurrence is satisfied also by the right-hand side of (5.19). By induction, both sides must be equal; QED. But there’s a neater proof. When r is an integer in the range 0 3 r 3 -m, the binomial theorem tells us that both sides of (5.19) are (x+y)“‘+‘y~‘. 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 y(y)(-l,x
=
integer m 3 0,
k
an alternative form of identity (5.16). And if we set x = y = 1 and r = m + 1, we get
&. (‘“,’ ‘) = &. (“: “pk. 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 1pm+1 = 22” . This yields a formula that is quite unexpected, 2 (5.20) Let’s check it when m = 2: (‘,) + i(f) + i(i) = 1 + $ + $ = 4. Astounding. 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:
(L)(F) = (I)(z$
integers m, k.
(5.21)
We’ve already seen the special case k = 1; it’s the absorption identity (5.6). Although both sides of (5.21) 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 (i) (r) by (I;) (A<“,) when summing on m.
