Summary
First principle of mathematical induction(1PI)
- for well-ordered sets, such as
Second principle of mathematical induction(2PI)
- strong induction
- when the statement relies on several previous cases
The main idea of induction: a previous iteration of your proof satisfies a smaller version of your problem
Application
1PI, generalisation of De Morgan’s law
2PI, fundemental theorem of arithmetic
- every integer can be expresses as a product of prime numbers
2PI, CNF