Go backward to More Readable Version Go up to Top Go forward to Structural Induction

Mathematical Induction

Strategy for proving P on natural numbers.

• Induction basis: Show that P(0) holds.
• Induction hypothesis: assume P(i).
• Induction step: prove P(i+1)

Proposition

There exist exactly n! permutations of n objects.

Proof

We use mathematical induction.

• Basis: There exists exactly 1=0! permutation of 0 objects (the "empty" permutation).
• Hypothesis: n! permutations of n objects exist.
• Step: Add a new object j to n objects. For each permutation <k_i1, k_i2, ..., k_in > of the n objects, n+1 permutations result: <j, k_i1, k_i2, ..., k_in >, <k_i1, j, k_i2, ..., k_in >, ..., <k_i1, k_i2, ..., k_in, j >. Since there are n! permutations of n objects, there are (n+1)*n!=(n+1)! permutations of n+1 objects.