Mathematical induction: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Nick Johnson
No edit summary
 
imported>Subpagination Bot
m (Add {{subpages}} and remove any categories (details))
(9 intermediate revisions by 3 users not shown)
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.
{{subpages}}


[[Category: Mathematics Workgroup]] [[Category: CZ_Live]]
'''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]].


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


Proposition: A [[tree (Graph Theory)|tree]] in [[graph theory]] has [[euler characterist|Euler Characteristic]] of -1.
* The first case is true; and
* If any case is true then so is the next.
 
Suppose one calls the propositions ''P''<sub>1</sub>, ''P''<sub>2</sub>, ''P''<sub>3</sub>, ... .  Then the proof consists of two steps:
 
* The proof that ''P''<sub>1</sub> is true; and
* The proof that if ''P''<sub>''k''</sub> is true, the so is ''P''<sub>''k''+1</sub>, 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''<sub>''k''</sub> and proves ''P''<sub>''k''+1</sub>.  The proposition ''P''<sub>''k''</sub> is called the "induction hypothesis".
 
== Examples ==
 
=== An identity ===
 
A proposition states that for all positive integers ''n'',
 
: <math>1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}.</math>
 
In case ''n'' = 1, this says
 
: <math> 1 = \frac{1(1 + 1)}{2}, </math>
 
which is trivial.  The induction hypothesis states that for a particular value of ''n'' we have
 
: <math>1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2},</math>
 
and in the induction step we need to prove that if the induction hypothesis is true, then so is the ''next'' proposition in the sequence, involving ''n''&nbsp;+&nbsp;1 instead of ''n'':
 
: <math> 1 + 2 + 3 + \cdots + n + (n + 1) = \frac{(n+1)(n+2)}{2}.</math>
 
We have
 
: <math> \bigg[ 1 + 2 + 3 + \cdots + n \bigg] + (n + 1) = \left[\frac{n(n + 1)}{2}\right] + (n + 1),  </math>
 
since the induction hypothesis tells us the two expressions in square brackets are equal.  Then by elementary algebra we have
 
: <math> \left[\frac{n(n + 1)}{2}\right] + (n + 1) = (n+1)\left[ \frac{n}{2} + 1 \right] </math>
 
(we have taken out the factor ''n''&nbsp;+&nbsp;1 that the two terms share in common)
 
: <math> {} = \frac{(n + 1)(n + 2)}{2}, </math>
 
which was to be proved.
 
=== An example from graph theory ===
 
Proposition: A [[tree (graph theory)|tree]] in [[graph theory]] has [[euler characterist|Euler characteristic]] &minus;1.


Proof: By induction,
Proof: By induction,


Base proposition: the trivial tree <math>\Gamma_0</math>---a single vertex without edges---has Euler characteristic <math>\Chi(\Gamma_0) = 0E - 1V = -1</math>.
Base proposition: the trivial tree <math>\Gamma_0</math>&mdash;a single vertex without edges&mdash;has Euler characteristic <math>\Chi(\Gamma_0) = 0E - 1V = -1</math>.
 
Induction step: For a tree <math>\Gamma</math>, and any extension single vertex extension of that tree <math>\Gamma'</math>, show that


Inductive Hypothesis: For a tree <math>\Gamma</math>, and any extension single vertex extension of that tree <math>\Gamma'</math>, show that <math>[ \Chi(\Gamma) = -1 ] \implies [ \Chi(\Gamma') = -1 ]</math>.
: <math>[ \Chi(\Gamma) = -1 ] \implies [ \Chi(\Gamma') = -1 ].</math>


If <math>\Chi(\Gamma) = -1</math>, then adding one vertex and one edge to this graph would yield:
If <math>\Chi(\Gamma) = -1</math>, then adding one vertex and one edge to this graph would yield:


<math>\Chi(\Gamma') = \Chi(\Gamma) + 1E - 1V = \Chi(\Gamma) = -1</math>.
: <math>\Chi(\Gamma') = \Chi(\Gamma) + 1E - 1V = \Chi(\Gamma) = -1.</math>


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.
Since all trees can be constructed in this manner from the trivial tree, it must be the case that all trees have Euler characteristic &minus;1. QED.

Revision as of 16:53, 10 November 2007

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

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 P1, P2, P3, ... . Then the proof consists of two steps:

  • The proof that P1 is true; and
  • The proof that if Pk is true, the so is Pk+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 Pk and proves Pk+1. The proposition Pk is called the "induction hypothesis".

Examples

An identity

A proposition states that for all positive integers n,

In case n = 1, this says

which is trivial. The induction hypothesis states that for a particular value of n we have

and in the induction step we need to prove that if the induction hypothesis is true, then so is the next proposition in the sequence, involving n + 1 instead of n:

We have

since the induction hypothesis tells us the two expressions in square brackets are equal. Then by elementary algebra we have

(we have taken out the factor n + 1 that the two terms share in common)

which was to be proved.

An example from graph theory

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

Proof: By induction,

Base proposition: the trivial tree —a single vertex without edges—has Euler characteristic .

Induction step: 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.