Math Wiki

Mathematical induction

667pages 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 \frac{n(n+1)}{2} (for any positive integer n).

A proof by induction proceeds as follows:

  1. The statement is proved for the first possible value of n (usually 0 or 1, but other "starting values" are possible).
  2. 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 n+1 (the latter statement is simply the original statement with n replaced by n+1).
  3. 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 P(n) about the integer-valued variable n that is to be proved for n\ge n_0, the following must be proved.

  1. P(n_0)
  2. P(n) \implies P(n+1)

The conclusion is then

  1. P(n) for n\ge n_0.

Around Wikia's network

Random Wiki