Mathematical induction

In mathematics and Inductive Proof is a proof by cases, applicable whenever the problem can be divided into discrete, enumerable propositions. Inductive proofs consist first prove a base proposition $P_{0}$, and then prove an inductive hypothesis $\forall i>0,P_{i}\implies P_{i+1}$. modus ponens is then used to extend the proof over the entire domain of the problem.

Example

Proposition: A tree in graph theory has Euler Characteristic of -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$.

Inductive Hypothesis: 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.