The following theorem is called the Pigeonhole Principle. 

Theorem 2.10 When n + 1 pigeons roost in n holes, there must be some hole containing at least two pigeons. 

(a) Prove the Pigeonhole Principle using proof by contradiction. 

(b) Prove the Pigeonhole Principle using mathematical induction.