Fundamental Proof Techniques
- Induction Principle
- Diagonalization Principle
- Pigeonhole Principle
Induction Principle
The principle of mathematical induction states that any set of natural numbers containing zero, and with the property that it contains n + 1 whenever it contains all the numbers up to and including n, must in fact be the set of all natural numbers. Let we want to show that property P holds for all natural numbers. To prove this property, P using mathematical induction following are the steps:
- Basic Step: Firstly, show that property P is true for 0 or 1 i.e. the statement holds for the first natural number n where n = 0 or n = 1.
- Induction Hypothesis: Assume that property P holds for n
- Induction Step: Using induction hypothesis, show that P is true for n+1. Then by the principle of mathematical induction, P is true for all natural numbers
