# Mathematical induction

Talk0*667*pages on

this wiki

## Redirected from Induction

**Mathematical induction** is a method of proof by which a statement about a variable can be demonstrated to be true for all integer values of that variable greater than or equal to a specified integer (usually 0 or 1).

An example of such a statement is:

- The number of possible pairings of
*n*distinct objects is (for any positive integer*n*).

A **proof by induction** proceeds as follows:

- The statement is proved for the first possible value of
*n*(usually 0 or 1, but other "starting values" are possible). - The statement is
*assumed*to be true for some fixed, but unspecified, value*n*and this assumption is used to prove that the statement is true for (the latter statement is simply the original statement with*n*replaced by ). - The statement is then concluded to be true for all relevant values of
*n*(all nonnegative values or all positive values, depending).

That the conclusion in step 3 above follows from steps 1 and 2 is the **principle of mathematical induction**.

More formally, given a proposition about the integer-valued variable *n* that is to be proved for , the following must be proved.

The conclusion is then

- for .