Mathematics - Proof by induction

Mathematical induction is a method of mathematical proof.

It is done in two steps:

• The first step, known as the base case, is to prove the given statement for the first element.
• The second step, known as the inductive step, is to prove that, if the statement holds for some element n, then the statement holds for n + 1.

Mathematical induction is closely related to recursion.

Mathematical induction is an inference rule used in proofs.

The hypothesis in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis).

To test a collection, you only need to show that the “zero and one element work”. If this is the case, it implies by induction that “any numbers of elements work”.

• Mathematical induction