Given that the Pigeonhole Principle states that "When n + 1 pigeons roost in n holes, there must be some hole containing at least two pigeons", prove this by contradiction.
how would one go about doing this without using a specific example
Proving the Pigeonhole Principle using proof by contradiction
pigeonhole-principleproof-explanation
Best Answer
Suppose you could fit $n + 1$ pigeons into $n$ holes without any hole containing at least two pigeons. Number the $n$ holes for which this is possible from $1$ to $n$, and let $a_i$ denote the number of pigeons in hole $i$. By assumption, each $a_i$ is either $0$ or $1$. Since every pigeon is in a hole, it must be the case that $a_1 + \cdots + a_n$ is the total number of pigeons. That is $$ a_1 + \cdots + a_n = n + 1 $$ On the other hand, we have $a_i \leq 1$ for all $i$ (there is at most $1$ pigeon in each hole). Thus $$ a_1 + \cdots + a_n \leq 1 + \cdots + 1 = n $$ (if we add up $n$ things, each of which is at most $1$, the largest number we can get is $n$). So, we have shown $$ n + 1 \leq n $$ This implies $1 \leq 0$, which is absurd.