Mathematical logic and foundations Concept
Mathematical induction
Summary
Mathematical induction is a method to prove that a property holds for every natural number . A proof by induction has two steps. The base case proves . The induction step proves, for an arbitrary natural number , that implies . Then holds for every natural number .
Remarks
The method is valid because of the induction axiom of the Peano axioms. In the induction step, the assumption is the induction hypothesis. Common variants are induction from an arbitrary base case and strong induction.
Where this leads
14 pages build on this one.
- Well-ordering principle
- Sum of the first n natural numbers
- Sum of the roots of unity
- Sum of a finite geometric progression
- Repeating decimals are rational
- Associativity of addition
- Commutativity of addition
- Induction from an arbitrary base case
- Induction on the integers
- Distributive law
- Strong induction
- Bernoulli's inequality
- Arithmetic progression
- Skolem–Mahler–Lech theorem
Further reading
About this page
| Tag | 0ASJVEFA9J |
|---|---|
| URI | m2://0ASJVEFA9J |
| Aliases | principle-of-mathematical-induction, proof-by-induction |
| Kind | concept |
| Writing | W1 stated |
| MSC | 03F30 |
| Specializes | Mathematical proof |
| Part of | Proof methods |
| Same as |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge defines in: at least one definition (0 of 1)
- edge instance_of in: at least two examples (0 of 2)
- edge not_instance_of in: at least one non-example (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.