BijectiveProof.md (868B)
1 # Bijective Proof 2 3 Ch 6.3 4 5 **Definition:** A bijective proof is a proof where we prove the compared sets can be represented as a bijective function and thus have the same cardinality. 6 7 Example: 8 9 Prove $\binom{n}{k} = \binom{n}{n-k}$ 10 11 Proof: 12 13 $\binom{n}{k}$ describes all combinations of length k from a set of length n. Let's now defined a function upon these combinations. This function is f : X -> Y where X is the set of all combinations of length k made from the set with cardinality n. Let's also define Y as the complement of the input x with respect to the original set of length n. We know this function is a bijection because all combinations have a unique complement and all complements are mapped to, because of how we defined our function. $\blacksquare$ 14 15 I could improve upon this proof by stating Y is the set of all combinations of n with length n - k.