6.2 Binomial Coefficients and Counting Methods 295
(
n
k)
=
(
n− 1
k)
+
(
n− 1
k− 1)
allows the binomial coefficients to be arranged inPascal’s triangle:
1
11
121
1331
14641
1 5 10 10 5 1
... ... ... ... ... ... ... ... ... ... ... ...Here every entry is obtained by summing the two entries just above it.
This section presents applications of the basic properties of binomial coefficients.
Here is a problem from the 2001 Hungarian Mathematical Olympiad.
Example.Letmandnbe integers such that 1≤m≤n. Prove thatmdivides the number
nm∑− 1k= 0(− 1 )k(
n
k)
.
Solution.We would like to express the sum in closed form. To this end, we apply the
recurrence formula for binomial coefficients and obtain
nm∑− 1k= 0(− 1 )k(
n
k)
=nm∑− 1k= 0(− 1 )k((
n− 1
k)
+
(
n− 1
k− 1))
=nm∑− 1k= 0(− 1 )k(
n− 1
k)
−nm∑− 2k= 0(− 1 )k(
n− 1
k)
=n(− 1 )m−^1(
n− 1
m− 1)
=m(− 1 )m−^1(
n
m)
.
The answer is clearly divisible bym.
The methods used in proving combinatorial identities can be applied to problems
outside the field of combinatorics. As an example, let us take a fresh look at a property
that we encountered elsewhere in the solution to a problem about polynomials.
Example.Ifkandmare positive integers, prove that the polynomial
(xk+m− 1 )(xk+m−^1 − 1 )···(xk+^1 − 1 )is divisible by
(xm− 1 )(xm−^1 − 1 )···(x− 1 )in the ring of polynomials with integer coefficients.