Mathematical induction

Mathematical induction is a technique for proving a proposition that can be considered a conjunction of an infinite sequence of special cases. Despite the name, it is a deductive, rather than inductive, method, in the sense in which those terms are usually used in logic.

In any proof by mathematical induction, one proves that each member of an infinite sequence of propositions holds by reasoning as follows:

• The first case is true; and
• If any case is true then so is the next.

Suppose one calls the propositions P₁, P₂, P₃, ... . Then the proof consists of two steps:

• The proof that P₁ is true; and
• The proof that if P_k is true, the so is P_k+1, regardless of the value of k.

The first step is called the "basis". The second is the "inductive step". In the inductive step one assumes the truth of P_k and proves P_k+1. The proposition P_k is called the "induction hypothesis".

Example

Proposition: A tree in graph theory has Euler characteristic −1.

Proof: By induction,

Base proposition: the trivial tree $\Gamma _{0}$—a single vertex without edges—has Euler characteristic $\mathrm {X} (\Gamma _{0})=0E-1V=-1$.

Induction step: For a tree $\Gamma$, and any extension single vertex extension of that tree $\Gamma '$, show that

$[\mathrm {X} (\Gamma )=-1]\implies [\mathrm {X} (\Gamma ')=-1].$

If $\mathrm {X} (\Gamma )=-1$, then adding one vertex and one edge to this graph would yield:

$\mathrm {X} (\Gamma ')=\mathrm {X} (\Gamma )+1E-1V=\mathrm {X} (\Gamma )=-1.$

Since all trees can be constructed in this manner from the trivial tree, it must be the case that all trees have Euler characteristic −1. QED.