CombinatorialProof.md (784B)
1 # Combinatorial (Counting) Proofs 2 3 Ch 6.3 4 5 **Definition:** A combinatorial proof is a proof that shows we are counting the same set and thus they are equivalent. 6 7 Example: 8 9 Prove That $\binom{n}{k} = \binom{n}{n-k}$ 10 11 Proof: 12 13 Consider n choose k. This describes all combinations of length k of a set length n. This computation can be thought of inversely as well. Consider, each of these combinations has a complement where we have all elements not selected in the current combination. If we assume A is the current combination $\bar A$ is all elements of the set N (|N| = n), not in A. We know the set of all possible $\bar A$ is just all non-selected elements and thus has the same cardinality as the set A because we are describing the **same thing from two sides**. $\blacksquare$