Properties of binomial coefficients

1.6 PROPERTIES OF BINOMIAL COEFFICIENTS
We start by assuming that (1.49) is true for some positive integer n = N. We now
proceed to show that this implies that it must also be true for n = N+1, as follows:
(x + y)N+1 = (x + y)
N
N
Ck xN−k y k
k=0
=
=
N
N
Ck xN+1−k y k +
N
k=0
k=0
N
N+1
N
Ck xN+1−k y k +
N
Ck xN−k y k+1
N
Cj−1 x(N+1)−j y j ,
j=1
k=0
where in the first line we have used the assumption and in the third line have
moved the second summation index by unity, by writing k + 1 = j. We now
separate off the first term of the first sum, N C0 xN+1 , and write it as N+1 C0 xN+1 ;
we can do this since, as noted in (i) following (1.50), n C0 = 1 for every n. Similarly,
the last term of the second summation can be replaced by N+1 CN+1 y N+1 .
The remaining terms of each of the two summations are now written together,
with the summation index denoted by k in both terms. Thus
(x + y)N+1 = N+1 C0 xN+1 +
N
N
Ck +
N
Ck−1 x(N+1)−k y k + N+1 CN+1 y N+1
k=1
= N+1 C0 xN+1 +
N
N+1
Ck x(N+1)−k y k + N+1 CN+1 y N+1
k=1
=
N+1
N+1
Ck x(N+1)−k y k .
k=0
In going from the first to the second line we have used result (1.51). Now we
observe that the final overall equation is just the original assumed result (1.49)
but with n = N + 1. Thus it has been shown that if the binomial expansion is
assumed to be true for n = N, then it can be proved to be true for n = N + 1. But
it holds trivially for n = 1, and therefore for n = 2 also. By the same token it is
valid for n = 3, 4, . . . , and hence is established for all positive integers n.
1.6 Properties of binomial coefficients
1.6.1 Identities involving binomial coefficients
There are many identities involving the binomial coefficients that can be derived
directly from their definition, and yet more that follow from their appearance in
the binomial expansion. Only the most elementary ones, given earlier, are worth
committing to memory but, as illustrations, we now derive two results involving
sums of binomial coefficients.
27
PRELIMINARY ALGEBRA
The first is a further application of the method of induction. Consider the
proposal that, for any n ≥ 1 and k ≥ 0,
n−1
k+s
Ck = n+k Ck+1 .
(1.53)
s=0
Notice that here n, the number of terms in the sum, is the parameter that varies,
k is a fixed parameter, whilst s is a summation index and does not appear on the
RHS of the equation.
Now we suppose that the statement (1.53) about the value of the sum of the
binomial coefficients k Ck , k+1 Ck , . . . , k+n−1 Ck is true for n = N. We next write down
a series with an extra term and determine the implications of the supposition for
the new series:
N+1−1
k+s
Ck =
s=0
N−1
k+s
Ck + k+N Ck
s=0
= N+k Ck+1 + N+k Ck
= N+k+1 Ck+1 .
But this is just proposal (1.53) with n now set equal to N + 1. To obtain the last
line, we have used (1.52), with n set equal to N + k.
It only remains to consider the case n = 1, when the summation only contains
one term and (1.53) reduces to
k
Ck = 1+k Ck+1 .
This is trivially valid for any k since both sides are equal to unity, thus completing
the proof of (1.53) for all positive integers n.
The second result, which gives a formula for combining terms from two sets
of binomial coefficients in a particular way (a kind of ‘convolution’, for readers
who are already familiar with this term), is derived by applying the binomial
expansion directly to the identity
(x + y)p (x + y)q ≡ (x + y)p+q .
Written in terms of binomial expansions, this reads
p
p
Cs xp−s y s
s=0
q
q
Ct xq−t y t =
t=0
p+q
p+q
Cr xp+q−r y r .
r=0
We now equate coefficients of xp+q−r y r on the two sides of the equation, noting
that on the LHS all combinations of s and t such that s + t = r contribute. This
gives as an identity that
r
p
Cr−t q Ct = p+q Cr =
t=0
r
t=0
28
p
Ct q Cr−t .
(1.54)
1.6 PROPERTIES OF BINOMIAL COEFFICIENTS
We have specifically included the second equality to emphasise the symmetrical
nature of the relationship with respect to p and q.
Further identities involving the coefficients can be obtained by giving x and y
special values in the defining equation (1.49) for the expansion. If both are set
equal to unity then we obtain (using the alternative notation so as to produce
familiarity with it)
n
n
n
n
(1.55)
+
+
+ ···+
= 2n ,
0
1
2
n
whilst setting x = 1 and y = −1 yields
n
n
n
n
= 0.
−
+
− · · · + (−1)n
n
2
0
1
(1.56)
1.6.2 Negative and non-integral values of n
Up till now we have restricted n in the binomial expansion to be a positive
integer. Negative values can be accommodated, but only at the cost of an infinite
series of terms rather than the finite one represented by (1.49). For reasons that
are intuitively sensible and will be discussed in more detail in chapter 4, very
often we require an expansion in which, at least ultimately, successive terms in
the infinite series decrease in magnitude. For this reason, if x > y we consider
(x + y)−m , where m itself is a positive integer, in the form
y −m
(x + y)n = (x + y)−m = x−m 1 +
.
x
Since the ratio y/x is less than unity, terms containing higher powers of it will be
small in magnitude, whilst raising the unit term to any power will not affect its
magnitude. If y > x the roles of the two must be interchanged.
We can now state, but will not explicitly prove, the form of the binomial
expansion appropriate to negative values of n (n equal to −m):
(x + y)n = (x + y)−m = x−m
∞
k=0
where the hitherto undefined quantity
of negative numbers, is given by
−m
Ck = (−1)k
−m
−m
Ck
y k
x
,
(1.57)
Ck , which appears to involve factorials
m(m + 1) · · · (m + k − 1)
(m + k − 1)!
= (−1)k
= (−1)k
k!
(m − 1)!k!
m+k−1
Ck .
(1.58)
The binomial coefficient on the extreme right of this equation has its normal
meaning and is well defined since m + k − 1 ≥ k.
Thus we have a definition of binomial coefficients for negative integer values
of n in terms of those for positive n. The connection between the two may not
29