256 16. Answers to Exercises
3 Binomial Coefficients and Pascal’s Triangle
3.1 The Binomial Theorem
3.1.1.
(x+y)n+1
=(x+y)n(x+y)=(
xn+(
n
1)
xn−^1 y+···+(
n
n− 1)
xyn+(
n
n)
yn)
(x+y)=xn(x+y)+(
n
1)
xn−^1 y(x+y)+···+
(
n
n− 1)
xyn−^1 (x+y)+(
n
n)
yn(x+y)=
(
xn+1+xny)
+
(
n
1)
(
xny+xn−^1 y^2)
+···
+
(
n
n− 1)
(
x^2 yn−^1 +xyn)
+
(
n
n)
(
xyn+yn+1)
=xn+1+(
1+
(
n
1))
xny+((
n
1)
+
(
n
2))
xn−^1 y^2 +···+
((
n
n− 1)
+
(
n
n))
xyn+yn+1=xn+1+(
n+1
1)
xny+(
n+1
2)
xn−^1 y^2 +···+(
n+1
n)
xyn+yn+1.3.1.2. (a) (1−1)n= 0. (b) By
(n
k)
=
(n
n−k)
.
3.1.3. The identity says thatthe number of subsets of ann-element set
with an even number of elements is the same as the number of subsets with
an odd number of elements.We can establish a bijection between even and
odd subsets as follows: If a subset contains 1, delete it from the subset;
otherwise, add it to the subset.
3.2 Distributing Presents
3.2.1.
(
n
n 1
)
·
(
n−n 1
n 2)
···
(
n−n 1 −···−nk− 1
nk)
=
n!
n 1 !(n−n 1 )!(n−n 1 )!
n 2 !(n−n 1 −n 2 )!···
(n−n 1 −···−nk− 1 )!
nk− 1 !(n−n 1 −···−nk)!=n!
n 1 !n 2 !···nk!