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”.