2.30 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. 550 Chap. 2 Mathematical Preliminaries (a) Prove the Pigeonhole Principle using proof by contradiction. (b) Prove the Pigeonhole Principle using mathematical induction.