gen-define-a-bijective-proof-and-give-one-short-worked-example-88c1

Define a bijective proof and give one short worked example.

# Bijective Proof A **bijective proof** is a technique for proving that two sets have the same size by constructing an explicit bijection (one-to-one correspondence) between them. This is often used to prove that two different counting formulas equal each other. ## Short Example **Claim:** The number of subsets of {1, 2, ..., n} equals 2ⁿ. **Bijective Proof:** We construct a bijection between: - **Set A:** All subsets of {1, 2, ..., n} - **Set B:** All binary strings of length n **The bijection f:** For each subset S ⊆ {1, 2, ..., n}, create a binary string where the i-th position is: - 1 if i ∈ S - 0 if i ∉ S **Example with n = 3:** - Subset {1, 3} ↔ binary string 101 - Subset {2} ↔ binary string 010 - Subset ∅ ↔ binary string 000 - Subset {1, 2, 3} ↔ binary string 111 This mapping is clearly one-to-one and onto (bijective). Since there are 2ⁿ binary strings of length n, there must be 2ⁿ subsets. ∎