2.30 The following theorem is called the Pigeonhole Principle. Theorem 2.10 When n+1 pigeons roost in...

Transcribed Image Text:

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. 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.