Mathematical induction

**Mathematical induction** is a special way of proving a mathematical truth. It can be used to prove that something is true for all the natural numbers (or all positive numbers from a point onwards). The idea is that if:

# Something is true for the first case (base case); 
# Whenever that same thing is true for a case, it will be true for the next case (inductive case),

then
* That same thing is true for every case by induction.

In the careful language of mathematics, a proof by induction often proceeds as follows:
* State that the proof will be *by induction over n*. (n is the *induction variable*.)
* Show that the statement is true when n is 1.
* Assume that the statement is true for any natural number n. (This is called the *induction step*.)
** Show then that the statement is true for the next number, n+1.

Because it is true for 1, then it is true for 1+1 (=2, by the induction step), then it is true for 2+1 (=3), then it is true for 3+1 (=4), and so on.

## Examples of proof by induction
### Sum of the first n natural numbers
Prove that for all natural numbers *n*:

:1+2+3+....+(n-1)+n=\tfrac12 n(n+1)

Proof:

First, the statement can be written as:

:2\sum_{k=1}^n k=n(n+1)    (for all natural numbers *n)*

By induction on *n*,

First, for *n*=1:
:2\sum_{k=1}^1 k=2(1)=1(1+1),

so this is true.

Next, assume that for some *n*=*n0* the statement is true. That is,:

:2\sum_{k=1}^{n_0} k = n_0(n_0+1)

Then for *n*=*n0*+1:

:2\sum_{k=1}^{{n_0}+1} k

can be rewritten as

:2\left( \sum_{k=1}^{n_0} k+(n_0+1) \right) 

Since 2\sum_{k=1}^{n_0} k = n_0(n_0+1),

:2\sum_{k=1}^{n_0+1} k = n_0(n_0+1)+2(n_0+1) =(n_0+1)(n_0+2)

Hence the proof is complete by induction.

### The sum of the interior angles of a polygon
Mathematical induction is often stated with the starting value 0 (rather than 1). In fact, it will work just as well with a variety of starting values. Here is an example when the starting value is 3: "The sum of the interior angles of a n-sided polygon is (n-2)180 degrees."

The initial starting value is 3, and the interior angles of a triangle is (3-2)180 degrees. Assume that the interior angles of a n-sided polygon is (n-2)180 degrees. Add on a triangle which makes the figure a n+1-sided polygon, and that increases the count of the angles by 180 degrees (n-2)180+180=(n+1-2)180 degrees. Since both the base case and the inductive case are handled, the proof is now complete.

There are a great many mathematical objects for which proofs by mathematical induction works. The technical term is a *well-ordered set*.

## Inductive definition
The same idea can work to *define* a set of objects, as well as to prove statements about that set of objects.

For example, we can define nth degree cousin as follows:
*A 1st degree cousin is the child of a parent's sibling.
*A n+1st degree cousin is the child of a parent's nth degree cousin.

There is a set of axioms for the arithmetic of the natural numbers which is based on mathematical induction. This is called "Peano's Axioms". The undefined symbols are | and =.The axioms are
*| is a natural number.
* If n is a natural number, then n| is a natural number.
*If n| = m| then n = m.

One can then define the operations of addition and multiplication and so on by mathematical induction. For example:

*m + | = m|
*m + n| = (m + n)|

## Related pages 
* Mathematical proof
* Proof by contradiction

## References