258 16. Answers to Exercises
3.5.2.
(n
0)
=
(n
n)
= 1 (e.g., by the general formula for the binomial coeffi-
cients).
3.6 Identities in Pascal’s Triangle
3.6.1.
1+(
n
1)
+
(
n
2)
+···+
(
n
n− 1)
+
(
n
n)
=1+
[(
n− 1
0)
+
(
n− 1
1)]
+
[(
n− 1
1)
+
(
n− 1
2)]
+
···+
[(
n− 1
n− 2)
+
(
n− 1
n− 1)]
+1
=2
[(
n− 1
0)
+
(
n− 1
1)
+···+
(
n− 1
n− 2)
+
(
n− 1
n− 1)]
=2· 2 n−^1 =2n.3.6.2. The coefficient ofxnynin
((
n
0)
xn+(
n
1)
xn−^1 y+···+(
n
n− 1)
xyn−^1 +(
n
n)
yn) 2
is (
n
0
)(
n
n)
+
(
n
1)(
n
n− 1)
+···+
(
n
n− 1)(
n
1)
+
(
n
n)(
n
0)
.
3.6.3. The left-hand side counts allk-element subsets of an (n+m)-
element set by distinguishing them according to how many elements they
pick up from the firstn.
3.6.4. If the largest element isj(which is at leastn+ 1), then the rest
can be chosen
(j− 1
n)
ways. If we sum over allj≥n+ 1, we get the identity
(
n
n)
+
(
n+1
n)
+···+
(
n+k
n)
=
(
n+k+1
n+1)
.
Using that
(n+i
n)
=
(n+i
i)
, we get (3.5).3.7 A Bird’s Eye View of Pascal’s Triangle
3.7.1. n=3k+2.
3.7.2. This is not easy. We want to determine the first value ofkwhere
the difference of differences turns nonpositive:
((
n
k+1
)
−
(
n
k))
−
((
n
k)
−
(
n
k− 1