Session 6D
Proofs by bijection
45-75 min - work through lesson notes, practice, and the MCQ check.
In progress
Account sync
Sign in to keep this session synced across devices.
Account sync disabled
Add Supabase environment variables to enable account sync. Progress is saved locally in this browser for now.
Session tips
- Finish the MCQ before marking complete.
- Check the answer outlines after trying on paper.
- Mark complete to update your certificate progress.
Lesson notes
- A bijection proof shows two sets have the same size by giving a function that pairs each object in one set with exactly one object in the other, with no leftovers. This is stronger than "they look the same size" because it explicitly constructs a perfect matching. Bijections are widely used to prove combinatorial identities, like C(n,k) = C(n,n-k): map each k-subset to its complement, which is an (n-k)-subset. The complement map is reversible, so it's a bijection.
- Bijection thinking also helps you avoid double counting and clarifies when order matters. If you can build a bijection, you have a proof that two counts are equal without computing either count directly. This style becomes more important later in algebra and discrete math, where structure-preserving maps (isomorphisms) are essentially advanced bijections. For beginners, the goal is learning to describe the map clearly and argue it is one-to-one and onto.
Practice
- 1Give a bijection proof of C(n,k) = C(n,n-k).
- 2Prove: number of odd-sized subsets equals number of even-sized subsets (n >= 1).
Show answers / outlines
Answers
- 1Pair each subset S with its symmetric difference with a fixed element.
Week quiz
- 1Use pigeonhole: show among any 5 integers, two differ by a multiple of 4.
Show quiz answers
Quiz answers
- 1Two integers have the same remainder mod 4.
MCQ
A bijection is used to prove: