Induction front page

a repository of mathematical know-how

Induction front page

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[note article incomplete]See comments.[/note]

[tableofcontents]

===Weak induction===

[EXAMPLE basic_weak_induction|A simple arithmetic identity]

Consider the identity [maths|1]1^2+2^2+...+n^2 = \frac{n(n+1)(2n+1)}{6}.[/maths] Since the left-hand side of (1) is neither an arithmetic nor a geometric progression, we are unable to use the standard formulas for calculating such sums; and, indeed, it is not obvious how to transform the expression into one that can be manipulated into a formula for the sum. However, this can be proved using induction.

[EXAMPLE counterexample|The base case is important]

Sometimes one can have the temptation of looking at the base case of induction as a mere formal step that is always trivially true, thinking that the "big deal" is just on the induction hypothesis. But actually it IS important: here we have an example of a general statement which induction hypothesis is true but that is ''always'' false... because we can never find a base case!

Suppose true that, for a fixed $n$, $n-1>n$. Then, $n=(n-1)+1 > n+1$. But we obviously know that this statement is never true, so there can't be a base case.

===Strong induction===

[EXAMPLE strong_induction_example|An example of strong induction]

===Induction on a general ordered set===

===See also===

[[Strengthen your inductive hypothesis]]

[[Transfinite induction]] is discussed in a separate article.

Induction front page

Recent articles

Active forum topics

Recent comments