gen-briefly-explain-a-bijective-proof-and-one-common-misconcepti-ee0e

Briefly explain a bijective proof and one common misconception about it.

## Bijective Proof A **bijective proof** is a technique that proves two sets have the same size by constructing a bijection (one-to-one correspondence) between them. If counting one set answers a combinatorial question in two different ways, this establishes that both counting methods give the same answer. **Example:** To prove that the number of subsets of an n-element set equals 2^n, you can create a bijection between subsets and n-bit binary strings (each bit indicates whether an element is included). ## Common Misconception **Misconception:** "A bijective proof just means proving two formulas are equal algebraically." **Reality:** A bijective proof requires explicitly constructing a bijection between two *sets of objects*—not just manipulating formulas. The proof must show that each object in set A corresponds to exactly one object in set B and vice versa. Simply showing that two expressions evaluate to the same number (like algebraic manipulation or induction) is not a bijective proof, even though it may prove the same result.