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 ...
Get Discrete Mathematics and Combinatorics now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
