Tricki

## Induction front page

### Example 1: A simple arithmetic identity

Consider the identity

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 , . Then, . But we obviously know that this statement is never true, so there can't be a base case.

### Induction on a general ordered set

Transfinite induction is discussed in a separate article.

Using generators and closure properties