Consider the following situation n people are gathered for a

Consider the following situation: n people are gathered for a game requiring teams (such as soccer), each with k players. One team will wear blue shirts, and the other team will wear red shirts. Assume that 2k lessthanorequalto n. The n-2k people not on either team will just watch the game. We can choose the teams in either of two ways. One approach is to choose the k players to wear the red shirts, from among n people, and then choose the k players to wear the blue shirts, from among the remaining n-k people. The other approach is to choose the 2k players from among n people, and then choose k of them to wear the red shirts (giving blue shirts to the other k players). Write down the combinatorial identify suggested by this analysis. Prove algebraically the identity suggested by this analysis. Consider the identity kC(n, k) = nC(n-1, k-1), where 1 lessthanorequalto k lessthanorequalto n. Verify the identity for n = 10, k = 5. Give an algebraic proof of the identity. Give a combinatorial proof of the identity. Give a combinatorial proof of the identity. Consider the identity k(k - 1)C(n, k) = n(n - 1)C(n - 2, k - 2). Verify the identity for n = 10, k = 5. Give an algebraic proof of the identity. Give a combinatorial proof of the identity. Give a combinatorial proof of the identity. Give a combinatorial proof of the identity found in Exercise 9a. Consider the identity Sigma^n_ k=1 kC(n, k) = n2^n-1. Verify the identity for n = 6. Prove the identity by induction, using Pascal\'s identity. Prove the identity by a combinatorial argument based on choosing a committee with a chairperson from a group of n people. Prove the identity by a combinatorial argument based on the sum of the cardinalities of all the subsets of an n-set. Give a combinatorial proof of the identity Sigma^n_k=0 C(n, k)^2 = C(2n, n). Consider the identity

Solution

For n=6

RHS

= 6 * (2)⁵

= 192

and LHS = C(6,1) + 2C(6,2) + 3C(6,3) + 4C(6,4) + 5C(6,5) + 6C(6,6)

= 6 + 30 + 60 + 60 + 30 + 6

= 192

hence proved

Let given identity be true for n-1

i.e. summation of kC(n-1,k) = (n-1) (2)^n-2

adding nC(n,k) on RHS,

(n-1) 2^n-2 + nC(n,k)

i.e.

(n-1)/2 * 2n/(n-1) * 2ⁿ

i.e. n.2^n-1 = RHS

hence proved