I need a combinatorial proof for Pascal\'s identity. Prove C(n,k) = C(n-1,k) + C

Question

I need a combinatorial proof for Pascal's identity.

Prove C(n,k) = C(n-1,k) + C (n-1,k-1).

So here is what I have: We have a group of n students and we can choose k committees from the n students. For the RHS: if we take one student out (call him r), then we can make k subcommittees out of n-1 students, that is, C(n-1, k).

That is all I have. C (n-1,k-1) is supposed to represent how many committees you can that has student r. However, I do not see why that is the case.

In short, it is the left hand side of the RHS of the equation that has me stumped.

Explanation / Answer

combinatorial proof: Prove C(n,k) = C(n-1,k-1) + C(n-1,k) Consider a set T of n elements nWe want to choose a subset of k elements nWe will count the number of subsets of k elements via 2 methods Method 1: There are C(n,k) ways to choose such a subset Method 2: Let a be an element of set T Two cases na is in such a subset There are C(n-1,k-1) ways to choose such a subset na is not in such a subset There are C(n-1,k) ways to choose such a subset Thus, there are C(n-1,k-1) + C(n-1,k) ways to choose a subset of k elements
Therefore, C(n,k) = C(n-1,k) + C(n-1,k-1) combinatorial proof: Prove C(n,k) = C(n-1,k-1) + C(n-1,k) Consider a set T of n elements nWe want to choose a subset of k elements nWe will count the number of subsets of k elements via 2 methods Method 1: There are C(n,k) ways to choose such a subset Method 2: Let a be an element of set T Two cases na is in such a subset There are C(n-1,k-1) ways to choose such a subset na is not in such a subset There are C(n-1,k) ways to choose such a subset Thus, there are C(n-1,k-1) + C(n-1,k) ways to choose a subset of k elements
Therefore, C(n,k) = C(n-1,k) + C(n-1,k-1)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.