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).^[1][2] 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.^[3]

In the careful language of mathematics, a proof by induction often proceeds as follows:

• State that the proof will be by induction over ${\displaystyle n}$. (${\displaystyle n}$ is the induction variable.)
• Show that the statement is true when ${\displaystyle n}$ is 1.
• Assume that the statement is true for any natural number ${\displaystyle n}$. (This is called the induction step.)
  • Show then that the statement is true for the next number, ${\displaystyle 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:

${\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}$

Proof:

First, the statement can be written as:

${\displaystyle 2\sum _{k=1}^{n}k=n(n+1)}$ (for all natural numbers n)

By induction on n,

First, for n=1:

${\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)}$,

so this is true.

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

${\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}$

Then for n=n₀+1:

${\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}$

can be rewritten as

${\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}$

Since ${\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),}$

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

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

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

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

• ${\displaystyle m+|=m|}$
• ${\displaystyle m+n|=(m+n)|}$

Related pages

• Mathematical proof
• Proof by contradiction

References

1. "The Definitive Glossary of Higher Mathematical Jargon". Math Vault. 2019-08-01. Retrieved 2020-09-23.
2. "3.4: Mathematical Induction - An Introduction". Mathematics LibreTexts. 2018-04-25. Retrieved 2020-09-23.
3. "Induction". discrete.openmathbooks.org. Retrieved 2020-09-23.