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:

1. Something is true for the first case (base case);
2. 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 [math]\displaystyle{ n }[/math]. ([math]\displaystyle{ n }[/math] is the induction variable.)
• Show that the statement is true when [math]\displaystyle{ n }[/math] is 1.
• Assume that the statement is true for any natural number [math]\displaystyle{ n }[/math]. (This is called the induction step.)
  • Show then that the statement is true for the next number, [math]\displaystyle{ n+1 }[/math].

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.

Sum of the first n natural numbers

Prove that for all natural numbers n:

[math]\displaystyle{ 1+2+3+....+(n-1)+n=\tfrac12 n(n+1) }[/math]

Proof:

First, the statement can be written as:

[math]\displaystyle{ 2\sum_{k=1}^n k=n(n+1) }[/math] (for all natural numbers n)

By induction on n,

First, for n=1:

[math]\displaystyle{ 2\sum_{k=1}^1 k=2(1)=1(1+1) }[/math],

so this is true.

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

[math]\displaystyle{ 2\sum_{k=1}^{n_0} k = n_0(n_0+1) }[/math]

Then for n=n₀+1:

[math]\displaystyle{ 2\sum_{k=1}^ == Mathematical Induction Media == \lt gallery widths='160px' heights='100%' mode='traditional' caption=''\gt File:Dominoeffect.png|Mathematical induction can be informally illustrated by reference to the sequential effect of [[Domino toppling|falling dominoes]]. File:OmegaPlusOmega_svg.svg|"[[Number line]]" for the set {{math|1={{color|#800000|{(0, ''n''): ''n'' ∈ '''N'''}}} ∪ {{color|#000080|{(1, ''n''): ''n'' ∈ '''N'''}}}}}. Numbers refer to the second component of pairs; the first can be obtained from color or location. \lt /gallery\gt {{n_0}+1} k }[/math]

can be rewritten as

[math]\displaystyle{ 2\left( \sum_{k=1}^{n_0} k+(n_0+1) \right) }[/math]

Since [math]\displaystyle{ 2\sum_{k=1}^{n_0} k = n_0(n_0+1), }[/math]

[math]\displaystyle{ 2\sum_{k=1}^{n_0+1} k = n_0(n_0+1)+2(n_0+1) =(n_0+1)(n_0+2) }[/math]

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 [math]\displaystyle{ n }[/math]-sided polygon is [math]\displaystyle{ (n-2)180 }[/math] degrees."

The initial starting value is 3, and the interior angles of a triangle is [math]\displaystyle{ (3-2)180 }[/math] degrees. Assume that the interior angles of a [math]\displaystyle{ n }[/math]-sided polygon is [math]\displaystyle{ (n-2)180 }[/math] degrees. Add on a triangle which makes the figure a [math]\displaystyle{ n+1 }[/math]-sided polygon, and that increases the count of the angles by 180 degrees [math]\displaystyle{ (n-2)180+180=(n+1-2)180 }[/math] 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 [math]\displaystyle{ n }[/math]th degree cousin as follows:

• A [math]\displaystyle{ 1 }[/math]st degree cousin is the child of a parent's sibling.
• A [math]\displaystyle{ n+1 }[/math]st degree cousin is the child of a parent's [math]\displaystyle{ n }[/math]th 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 [math]\displaystyle{ n }[/math] is a natural number, then [math]\displaystyle{ n| }[/math] is a natural number.
• If [math]\displaystyle{ n| = m| }[/math] then [math]\displaystyle{ n = m }[/math].

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

• [math]\displaystyle{ m + | = m| }[/math]
• [math]\displaystyle{ m + n| = (m + n)| }[/math]

Related pages

• Mathematical proof
• Proof by contradiction