Page 443 - Discrete Mathematics and Its Applications

422 6 / Counting

21. Prove that if n and k are integers with 1 ≤ k ≤ n, then 33. In this exercise we will count the number of paths in the
n
n−1
k = n , xy plane between the origin (0, 0) and point (m, n), where
k k−1
a) using a combinatorial proof. [Hint: Show that the two m and n are nonnegative integers, such that each path is
sides of the identity count the number of ways to select made up of a series of steps, where each step is a move one
a subset with k elements from a set with n elements unit to the right or a move one unit upward. (No moves to
and then an element of this subset.] the left or downward are allowed.) Two such paths from
n
(0, 0) to (5, 3) are illustrated here.
b) using an algebraic proof based on the formula for
r
given in Theorem 2 in Section 6.3.
(5, 3)
n
n
r
n−k
22. Prove the identity = , whenever n, r, and
r k k r−k
k are nonnegative integers with r ≤ n and k ≤ r,
a) using a combinatorial argument.
b) using an argument based on the formula for the num-
ber of r-combinations of a set with n elements.
23. Show that if n and k are positive integers, then
(0, 0)
n + 1 n
(5, 3)

= (n + 1) k.
k k − 1
Use this identity to construct an inductive definition of
the binomial coefficients.
24. Show that if p is a prime and k is an integer such that
p

1 ≤ k ≤ p − 1, then p divides .
k
25. Let n be a positive integer. Show that (0, 0)
a) Show that each path of the type described can be rep-
2n 2n 2n + 2 resented by a bit string consisting of m 0s and n 1s,

+ = /2.
n + 1 n n + 1 where a 0 represents a move one unit to the right and
a 1 represents a move one unit upward.
∗ 26. Let n and k be integers with 1 ≤ k ≤ n. Show that m + n
b) Conclude from part (a) that there are paths of
n
the desired type.
n
n n 2n + 2 2n
= /2 − . 34. Use Exercise 33 to give an alternative proof of Corollary 2
k k − 1 n + 1 n n
n
k = 1 in Section 6.3, which states that = whenever k
k n−k
is an integer with 0 ≤ k ≤ n.[Hint: Consider the number
∗ 27. Prove the hockeystick identity
of paths of the type described in Exercise 33 from (0, 0)
r to (n − k, k) and from (0, 0) to (k, n − k).]
n + k n + r + 1
=
k r 35. Use Exercise 33 to prove Theorem 4. [Hint: Count the
k = 0
number of paths with n steps of the type described in Ex-
whenever n and r are positive integers, ercise 33. Every such path must end at one of the points
a) using a combinatorial argument. (n − k, k) for k = 0, 1, 2,...,n.]
b) using Pascal’s identity. 36. Use Exercise 33 to prove Pascal’s identity. [Hint: Show
2n
n
2 that a path of the type described in Exercise 33
28. Show that if n is a positive integer, then = 2 + n
2 2 from (0, 0) to (n + 1 − k, k) passes through either
a) using a combinatorial argument.
(n + 1 − k, k − 1) or (n − k, k), but not through both.]
b) by algebraic manipulation.
n
n n−1 37. Use Exercise 33 to prove the hockeystick identity from
∗ 29. Give a combinatorial proof that k = n2 .
k = 1 k Exercise 27. [Hint: First, note that the number of
[Hint: Count in two ways the number of ways to select a n + 1 + r
paths from (0, 0) to (n + 1,r) equals . Sec-
committee and to then select a leader of the committee.] r
ond, count the number of paths by summing the num-
n 2
n 2n−1
∗ 30. Give a combinatorial proof that k = 1 k k = n n−1 . ber of these paths that start by going k units upward for
[Hint: Count in two ways the number of ways to select a k = 0, 1, 2,...,r.]
committee, with n members from a group of n mathemat-
38. Give a combinatorial proof that if n is a positive inte-
ics professors and n computer science professors, such n 2 n n−2

ger then k = 0 k k = n(n + 1)2 .[Hint: Show that
that the chairperson of the committee is a mathematics bothsidescountthewaystoselectasubsetofasetofnele-
professor.] ments together with two not necessarily distinct elements
31. Show that a nonempty set has the same number of subsets from this subset. Furthermore, express the right-hand side
with an odd number of elements as it does subsets with as n(n − 1)2 n−2 + n2 n−1 .]
an even number of elements. ∗ 39. Determine a formula involving binomial coefficients for
∗ 32. Prove the binomial theorem using mathematical induc- the nth term of a sequence if its initial terms are those
tion. listed. [Hint: Looking at Pascal’s triangle will be helpful.