Induction

Axiom: Principle of induction

Let be a statement for every . If and if for every , then for every .

Terminology

In an inductive proof, we call the induction basis, the induction hypothesis and the induction step.

Note that for an inductive proof to work, there only needs to exist a bijective map between the sequence of statements and the natural numbers. For example, if we want to prove that is true for every , then we can of course use induction here too. To use the principle of induction, we would for example let , but this is not a step one would actually take in a proof.

Theorem

Every number can be written as for some number of ones, that we call .

Proof:
We use induction. The statement is obviously true for . Now, if can be written as , then can be written as the sum of one more , so the statement is also true for . Hence, it is true for every .