Tricki
a repository of mathematical know-how

Induction front page

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.

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

A non-trivial circular argument can often be usefully perturbed to a non-circular one.

Comments

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: http://www.dpmms.cam.ac.uk/~wtg10/bounded.html.

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).