## Chapter 5

## Mathematical Induction, Principle of Inclusion and Exclusion, and Pigeon-hole Principle

#### Learning Objectives

On completing this chapter, you should be able to:

state the principle of mathematical induction

prove formulas that are valid for all *n* ∈ ℕ by using the principle of mathematical induction

state the principle of inclusion and exclusion

solve counting problems using the principle of inclusion and exclusion

state and prove the result on the number of functions from a finite set onto another finite set

state the pigeon-hole principle

solve simple counting problems using the pigeon-hole principle

Mathematical induction is a technique, which is used in proving statements that are valid for all *n* ∈ *N*. We are familiar with the ...