I'm not sure how to go about this proof at all and I would greatly appreciate it if the overall process was shown please! Use the principle of mathematical induction to prove the pigeonhole principle:

"If $n$ items are distributed amongst $m$ pigeonholes with $n, m \in \Bbb{Z^+}$ and $n>m$, then at least one pigeonhole will contain at least $\frac{n}{m}$ items."

Thanks again!!!


Base case: let there be just one pigeonhole, i.e. $m=1$. If we seek to distribute $n > 1$ items among this one pigeonhole, then it follows that this pigeonhole contains $n/m = n$ items.

Induction step: now let there be $m+1$ pigeonholes, and suppose we want to distribute $n > m + 1$ items among these pigeonholes. This case reduces to needing to distribute one item in one pigeonhole, and $n-1$ items among $m+1-1 =m$ pigeonholes, for which we know the proposition to hold true (see the base case, above.) Note that since $n > m +1$ , it follows that $n - 1 > m$, so the case is the exact same.

  • $\begingroup$ Beat me to it. Nice job. $\endgroup$ – Laars Helenius Apr 12 '17 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.