Mathematical induction: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Nick Johnson
No edit summary
 
imported>Randy Nonenmacher
m (changed "and" to "an")
Line 1: Line 1:
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 <math>P_0</math>, and then prove an inductive hypothesis <math>\forall i > 0, P_i\implies P_{i+1}</math>.  [[modus ponens]] is then used to extend the proof over the entire domain of the problem.
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 <math>P_0</math>, and then prove an inductive hypothesis <math>\forall i > 0, P_i\implies P_{i+1}</math>.  [[modus ponens]] is then used to extend the proof over the entire domain of the problem.


[[Category: Mathematics Workgroup]] [[Category: CZ_Live]]
[[Category: Mathematics Workgroup]] [[Category: CZ_Live]]

Revision as of 13:35, 14 May 2007

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.