Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
