a repository of mathematical know-how

Revision of Induction front page from Fri, 24/04/2009 - 20:37

Stub iconThis article is a stub.This means that it cannot be considered to contain or lead to any mathematically interesting information.
Note iconIncomplete This article is incomplete. See comments.

Weak induction

Example 1: A simple arithmetic identity

Consider the identity

1^2+2^2+...+n^2 = \frac{n(n+1)(2n+1)}{6}.(1)
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.

Strong induction

Example 2: 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.

See also Using generators and closure properties.


Moved the discussion to the comments

When this article is written, it should have examples of several different styles of inductive proof: the usual kind where you deduce P(k) from P(k-1), the slightly more sophisticated kind where you deduce it from the fact that P(j) is true for every j<k, induction over more sophisticated well-ordered sets, use of the well-ordering principle, etc.

Induction without an indexing set

"The generalized induction is harder because we don't have a nice indexing set like the natural numbers. Is there a way of doing induction without the crutch of an indexing set? Yes there is: you look for a minimal counterexample."

The above is from this article by Prof Gowers:

I feel that this could be put somewhere, but I am not sure where. The connection between the well-ordering principle and induction could also be mentioned (albeit briefly, since it doesn't seem like a trick).