- Two Combinatorics Proofs We Have Seen In Question 2 A That Substituting X 1 And X 1 Into The Binomial Expansion P 1 (107.99 KiB) Viewed 33 times
[Two combinatorics proofs] We have seen in Question 2 a that substituting x = -1 and x = 1 into the binomial expansion proves "Co + "C₁ + "C₂ + "C3 + ··· = 2". (1) (2) "Co "C₁ + "C₂ - "C3 + = 0, for n ≥ 1. Here are combinatorics proofs of these results. a Let S be an n-member set, and interpret each "C, as the number of r-member subsets of S. Hence prove the first identity (1). b To prove the second identity (2), choose a fixed element A in the set S. Pair up each subset U not containing A with the unique subset UU{A} containing A. i Explain why the procedure arranges all the subsets of S uniquely into pairs. ii Explain why one member of each pair has an even number of members, and the other has an odd number of members. iii Hence prove that "Co + "C₂ + ... = "C₁ + "C3 + ....