Discrete Math › Section D · Counting › Topic D.6
Combinatorial proofs
If two expressions both count the same collection of things, they must be equal. Combinatorial proofs turn that simple observation into short, convincing proofs of identities that would be tedious to prove with algebra.
In this topic
- Two ways to prove an identity
- The recipe
- Worked example: in or out
- Worked example: Pascal's rule
- Row sums revisited
- Worked example: a committee and its chair
- Worked example: the hockey stick
- Worked example: sum of squares
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…