Plz I need help
Let n be a positive integer. Let k be a positive integer.
(a) Using a counting argument, show that C(n - 1, k - 1) + C(n - 1, k) = C(n,k).
(b) Using a counting argument, show that C(n,0) + C(n,1) + C(n,2) + ... + C(n,n) = 2^n.
(c) Using a counting argument, show that C(n,0) + C(n + 1,1) + C(n + 2,2) + C(n + 3,3) + ... + C(n + k,k) = C(n + k + 1,k)
(d) Using a counting argument, show that C(m,0) C(n,r) + C(m,1) C(n,r - 1) + ... + C(m,r) C(n,0) = C(m + n,r).
(e) There are n^2 ordered pairs (a,b) of positive integers, where 1 \le a, b \le n. Using a counting argument, show that this number is also equal to
(n + 1)^2 - 2n - 1
(f) There are n^3 ordered triples (a,b,c) of positive integers, where 1 \le a, b, c \le n. Using a counting argument, show that this number is also equal to
(n + 1)^3 - 3n^2 - 3n - 1
Post one question at a time ! I will do (a) only and you do the rest so that you can learn:
We can use a combinatorial argument to prove this identity.
Suppose we want to choose a committee of k people from a group of n individuals. We can count the number of ways to do this in two different ways.
First, we can choose one person to be the leader of the committee, and then choose the remaining k - 1 members from the n - 1 remaining individuals. There are C(n - 1, k - 1) ways to do this.
Second, we can simply choose k members from the n individuals without designating one as the leader. There are C(n, k) ways to do this.
Since both methods count the same thing (the number of ways to choose a committee of k people from a group of n individuals), we have:
C(n - 1, k - 1) + C(n - 1, k) = C(n, k)
Therefore, we have proven the identity C(n - 1, k - 1) + C(n - 1, k) = C(n, k) using a combinatorial argument.
