Mathematical induction

From Citizendium
Revision as of 11:28, 13 July 2007 by imported>Michael Hardy (Inductive proof moved to Mathematical induction)
Jump to navigation Jump to search

In mathematics, an 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 , and then prove an inductive hypothesis . 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 ---a single vertex without edges---has Euler characteristic .

Inductive Hypothesis: For a tree , and any extension single vertex extension of that tree , show that .

If , then adding one vertex and one edge to this graph would yield:

.

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.