This web page presents the idea of mathematical induction. It will explain the basic ideas, show how you can use induction in your proofs, and presents a framework or template for exemplary proofs by induction in first year mathematics.

The word induction

refers to a type of
reasoning in which one *induces* general principles and facts
from specific examples. So it might properly be applied
to the scientific method of *inducing* facts about the world from
observations and experiments, and as such is distinguished from
deduction

in which facts are *deduced* from axioms or other
facts by strict logical laws. In fact, all mathematical
proofs are deductions, since there is no place in mathematics
for a proof

that goes by guessing a rule from a few examples.
However, for obscure historical reasons the
kind of deduction we will look at here is called mathematical
induction

, and it is usually just called induction

by
mathematicians—who, as just pointed out, don't use any sort of
induction in the correct sense of the word.

The main idea of mathematical induction is that if a statement
can be proved true for the number $1$, and if we can also show
that by *assuming it true for $1,2,3,4,\dots ,n$ we can
prove it true for $n+1$
*, then our statement will
therefore true for all natural numbers $n\ge 1$. The power of
this method is that a statement can be proved true for all natural
numbers in finitely many steps, rather than having to prove it
true for each $n\in \left\{1,2,3,4,\dots \right\}$ individually.
Induction is the main method of proof for any statement involving
natural numbers, and is also used extensively for proofs concerning
other finite objects, such as finite graphs, groups, etc.

Actually there is nothing special about starting with the number 1. Inductions often start with some other integer as some of the following examples demonstrate.

We start with some examples of results to be proved by induction.

**Proposition 2.1**** (Bernoulli's inequality)**

Let $x>-1$ in $\mathbb{R}$ and $n\in \mathbb{N}\cup \left\{0\right\}$. Then $(1+x{)}^{n}\ge 1+nx$.

**Proof**

The statement to be proved is,
For all real numbers $x>-1$ and all $n\in \mathbb{N}$
the inequality $(1+x{)}^{n}\ge 1+nx$ is true.

We start by letting $x>-1$ be an arbitrary real number. That is, we are not allowed to assume anything at all about this number other than it is a real number greater than $-1$. The rest of the proof is by induction on $n\in \mathbb{N}$.

We must define a particular statement to look at. In this
case (as is *usually* the case for proofs by induction) we obtain this
statement from the result we are trying to prove.

Let $P\left(n\right)$ be the statement
$(1+x{)}^{n}\ge 1+nx$

.

Notice that $P\left(n\right)$ is a mathematical statement: it
doesn't have a numerical value, but is instead *true* or *false*.
In fact this statement depends on the value of $n$ in the
sense that it might be true for some values of $n$ and false for
others. (It also depends on $x$, so perhaps we should
write it as $P(x,n)$, but since $x$ has been chosen
and will not change again throughout this proof, it is acceptable
to leave $x$ out of the notation and write $P\left(n\right)$.)

We must first prove that $P\left(0\right)$ is true.

**Subproof**

The statement $P\left(0\right)$ is
$(1+x{)}^{0}\ge 1+0\cdot x$

.
Since $1+x>0$ we have $(1+x{)}^{0}=1$ and
we also have $1+0\cdot x=1$. So this statement
says that an expression with value $1$ is greater or
equal to another expression with value $1$. Therefore
$P\left(0\right)$ is *true*.

We now consider an arbitrary $n\in \mathbb{N}\cup \left\{0\right\}$
and make an important assumption, that the following statement
(called the *induction hypothesis*) is true.

- $P\left(0\right)$, $P\left(1\right)$, $P\left(2\right)$, $\dots $, $P\left(n\right)$ are all true.

We claim that using this assumption that we can show that $P(n+1)$ is also true.

**Subproof**

Indeed, since $n\ge 0$ our induction hypothesis says that $(1+x{)}^{n}\ge 1+nx$ holds, since this is what $P\left(n\right)$ says and our induction hypothesis says that $P\left(n\right)$ is true. Since $x>-1$ we have $1+x>0$ so we can multiply both sides of the inequality $(1+x{)}^{n}\ge 1+nx$ by $1+x$ giving

We can expand the right hand side of this as

Putting these together we have

which is precisely the statement $P(n+1)$. Therefore, for arbitrary $n\in \mathbb{N}\cup \left\{0\right\}$ the induction hypothesis implies that $P(n+1)$ is also true.

Summing up, we showed that $P\left(0\right)$
is true, and we also showed that if $P\left(0\right)$ holds
then $P\left(1\right)$ is true. So we can deduce that
$P\left(0\right)$ and $P\left(1\right)$ are both true. But
by the argument just given it follows from this that
$P\left(0\right)$ and $P\left(1\right)$ and $P\left(2\right)$ are all true.
This process continues for as many times as required
to show that
$P\left(0\right)$ and $P\left(1\right)$ and $\dots $ and $P\left(n\right)$ are
all true for any $n\ge 0$. We deduce that
$P\left(n\right)$ holds for all $n\in \mathbb{N}\cup \left\{0\right\}$
*by
the principle of mathematical induction*.

It may be worth commenting further: on the key argument in
the last paragraph of this proof: it perhaps seems rather vague
or imprecise that this step of the proof rests on some intuition
that if $P\left(0\right)$ holds and $P\left(0\right)$, $P\left(1\right)$, $\dots $,
$P\left(n\right)$ imply $P(n+1)$ then $P\left(n\right)$ holds for all
$n\in \mathbb{N}$. Indeed this is a principle about the natural
numbers that we believe intuitively, and one that we take as an *axiom*
for the natural numbers. There are other approaches: for example
this principle of induction can be justified from alternative principles
or axioms about the natural numbers, such as the one that says that
for any property $P\left(n\right)$ true for some natural number there is
a *least* natural number with this property. This alternative axiom
for the natural numbers (together with the assertion that every
natural number except the very first one has a natural number one
less than it) can be used to justify the principle of induction.
A third approach, which takes us beyond the scope of these notes,
is that in some circumstances the set of natural numbers can be
*defined* to be the *smallest* set containing $0$ and closed under
$x\mapsto x+1$. Then if the conditions for induction are
correct for some statement $P\left(n\right)$, the set of objects satisfying
$P\left(n\right)$ is such a set of natural numbers containing $0$ and
closed under $x\mapsto x+1$ hence must be the whole of
$\mathbb{N}$, since $\mathbb{N}$ is the smallest such.

Here is another example of induction.

**Proposition 2.2**** (Triangle numbers)**

Let $k\ge 1$ be a natural number. Then the $k$th triangle number $1+2+\dots +k$ is equal to $k(k+1)/2$.

**Proof**

Let $P\left(k\right)$ be the statement
$\sum _{n=1}^{k}n=k(k+1)/2$

.

We first prove that $P\left(1\right)$ is true.

**Subproof**

The statement $P\left(1\right)$ is
$\sum _{n=1}^{1}n=1(1+1)/2$

.
The summation on the left hand side has a single term where
$n=1$, so is $1$. The formula on the right hand side
evaluates to $1(1+1)/2=2/2=1$. So the statement just
says $1=1$, which is true.

We now let $k\ge 1$ in the natural numbers be arbitrary and assume the following induction hypothesis.

- $P\left(1\right)$, $P\left(2\right)$, $\dots $, $P\left(k\right)$ are all true.

We show that using this assumption that $P(k+1)$ is also true.

**Subproof**

The expression $\sum _{n=1}^{k+1}n$ equals $(\sum _{n=1}^{k}n)+(k+1)$. By our assumption $P\left(k\right)$ is true so $\sum _{n=1}^{k}n=k(k+1)/2$ so $\sum _{n=1}^{k+1}n=k(k+1)/2+(k+1)=(k+1)(\frac{k}{2}+1)=(k+1)(k+2)/2$. Therefore $\sum _{n=1}^{k+1}n=(k+1)(k+2)/2$ is true. But this is exactly the statement $P(k+1)$, so we have succeeded in showing what we claimed.

So we have showed that $P\left(1\right)$ is true, and we also showed that if $k\ge 1$ is arbitrary and $P\left(1\right)$ and $P\left(2\right)$ and $\dots $ and $P\left(k\right)$ are all true then $P(k+1)$ is also true. We deduce that $P\left(k\right)$ holds for all $k\ge 1$ in $\mathbb{N}$ by the principle of mathematical induction.

The previous section gave example proofs by induction. These proofs have similar structure, and it is worth highlighting the similarities (as well as the differences).

- Both proofs use an integer variable to do the main work.
In the first case this variable was called $n$ and in the
second it was called $k$. We often explain what we are
doing as
*proving a statement by induction on $n$*(or $k$ in the second case). - In both proofs we defined a particular statement
that is considered in the induction. We called it
$P\left(n\right)$ or $P\left(k\right)$ but you can call it whatever you like.
This statement is the
*induction statement*. - In both proofs the variable we are doing induction on starts
at some particular number. In the first it was convenient to
start at $0$, and in the second we started at $1$.
This is the
*starting value*. - In both proofs we first proved that the statement $P$
is true at the starting value of the induction variable. This
step is called the
*base case*of the induction. - In the first proof we assumed that $n$ was arbitrary
and that a statement of the form $P\left(0\right)$ and $P\left(1\right)$
and $\dots $ and $P\left(n\right)$ is true. In the second this
was only modified to change the name of the induction variable
and the starting value of that variable. This assumption
that we made is the
*induction hypothesis*. - In both cases we showed that the induction hypothesis
implies that the next instance of $P$ is true (i.e.
$P(n+1)$ in the first case and $P(k+1)$ in the second).
This step in the argument is called the
*induction step*. - In both cases there is a concluding short narrative that explains
the use of the
*principle of induction*.

There are some general comments about induction that we should make.

- You should be prepared to do induction on any variable, whether it be called $n$, $k$ or something else.
- You should be prepared to start your induction at any integer. The most common places to start are $0$ and $1$, but any integer, even negative values, are valid places to start an induction.
- You must always write down an induction statement. Often this is derived from the theorem being proved, but there are also many cases when it is not obvious what to take at all. The conclusion of the induction is that this statement is true for all values of the variable greater than or equal to the starting value. In some complicated proofs it may be necessary to explain why this conclusion implies the required result.
- There are two steps to an induction proof: the base case and the induction step. Both must be included and nothing can be deduced until they are both done. It is not always the case that the base case is easier than the induction step. Sometimes it is the other way round.
- The safest kind of induction hypothesis to use is the one here
that says that $P\left(x\right)$ holds for all previous values $x$.
This is
safest

because it is the strongest hypothesis that is valid, and it makes sense to assume as much as possible to make the remaining argument as easy as possible. The two proofs above only used the immediately preceding case, $P\left(n\right)$ or $P\left(k\right)$, and many other induction proofs work in the same way. But there are also plenty of induction proofs that require more than one previous case.

For students who first see induction, the usual form it takes is the following:

- Define a statement $P\left(n\right)$;
- Show that $P\left(1\right)$ is true;
- Show that, assuming $P\left(n\right)$ is true one can derive $P(n+1)$;
- State that by the principle of induction, the above steps show that $P\left(n\right)$ holds for all natural numbers $n$.

This is the
$P\left(n\right)$ implies $P(n+1)$

form of induction
and the examples given above are of this type. There is nothing wrong
with this form of induction, except that it is not quite as powerful as
the one given earlier. The point is that in the
$P\left(n\right)$
implies $P(n+1)$

form you assume $P\left(n\right)$ is true whereas
you *could* have assumed the much stronger statement that $P\left(1\right)$,
$P\left(2\right)$,..., $P\left(n\right)$ all hold instead. You would have had a
little more to help you, which might have been useful (and often is), and
there are no disadvantages. The example of the Least Number Principle
discussed and proved below is one where the stronger form of induction is
particularly useful.

As a useful rule of thumb, any proof that you see which contains $\dots $ in the form something like $1,2,\dots ,n$ should properly speaking be proved by an application of induction. Hopefully, if the work is not yours, the piece you are reading is sufficiently clear to understand what is happening and to be able to rephrase the proof in terms of induction. This section discusses other common types of argument, some of which are really induction in disguise.

**Proposition 4.1**** (Least number principle)**

Suppose $P\left(x\right)$ is a statement and $s\in \mathbb{Z}$ such that $P\left(k\right)$ holds for some integer $k\ge s$. Then there is a least integer $k\ge s$ such that $P\left(k\right)$ holds.

**Proof**

This is by induction on the variable $k$ starting at $s$. But the twist is that we also combine this proof with a use of proof by contradiction.

So we start by assuming that the statement we are trying to prove is false, and we then use induction to derive a contradiction. Assume therefore that

- There is no least integer $k\ge s$ such that $P\left(k\right)$ holds.

**Subproof**

We now derive a contradiction by induction. Our
contradiction will be that there is in fact no integer
$k\ge s$ such that $P\left(k\right)$ holds, and this is
contrary to the assumptions in the proposition. Our
induction statement $Q\left(k\right)$ is the statement
$P\left(k\right)$ is false

. We must prove a base case
and an induction step.

The base case, $Q\left(s\right)$.

**Subproof**

If $Q\left(s\right)$ were false, that would mean that
$P\left(s\right)$ is false

is false, i.e. that
$P\left(s\right)$ is true. But then $s$ is the least
integer greater than or equal to $s$ for which
$P\left(s\right)$ is true, since there is no smaller integer
to consider, contrary to our assumption that there
is no such least integer.

Now assume that $k\ge s$ is arbitrary and assume the induction hypothesis that

- $Q\left(s\right)$, $Q(s+1)$, $\dots $, $Q\left(k\right)$ are all true.

We claim that it follows that $Q(k+1)$ is true.

**Subproof**

Indeed, if $Q(k+1)$ were false, that would mean that $P(k+1)$ is true. But by the induction hypothesis $Q\left(s\right)$, $Q(s+1)$, $\dots $, $Q\left(k\right)$ are all true and hence $P\left(s\right)$, $P(s+1)$, $\dots $, $P\left(k\right)$ are all false. So $k+1$ would be the least integer greater than or equal to $s$ such that $P(k+1)$ is true. This is contrary to our assumption that there is no such integer. So therefore $P(k+1)$ cannot be true and hence $Q(k+1)$ is true.

It follows from the base case and the induction step that $Q\left(k\right)$ is true for all integers $k\ge s$ by the principle of mathematical induction. Therefore $P\left(k\right)$ is false for all integers $k\ge s$, and this is contrary to one of the assumptions in the proposition, giving us the required contradiction.

**Proposition 4.2**** (Minimal counter-example)**

Suppose $P\left(k\right)$ is a statement that is false for some integer $k\ge s$, where $s\in \mathbb{Z}$. Then there is some least integer value of $k\ge s$ such that $P\left(k\right)$ is false.

**Proof**

Let $Q\left(k\right)$ be the statement that
$P\left(k\right)$ is false

.
So $Q\left(k\right)$ is true for some $k\ge s$ since
$P\left(k\right)$ is false for some such $k$. But then by
the previous proposition there is a least $k\in \mathbb{Z}$
with $k\ge s$ and $Q\left(k\right)$ is true. And this $k$
is the least integer $k\ge s$ such that $P\left(k\right)$ is false.

We conclude with an application: the
Archimedean Property
of the reals says that for any $x\in \mathbb{R}$ there is
some $n\in \mathbb{N}$ such that $x\le n$. It follows
from this that every $x\in \mathbb{R}$ has an
integer part,
$\left[x\right]$. To see this, let $x\in \mathbb{R}$
and choose $n,m\in \mathbb{N}$ such that $x\le n$
and $-x\le m$. So $-m\le x\le n$. and let
$P\left(k\right)$ be the statement
$x\le k$

. Then the integer
$n$ is an integer greater than or equal to $-m$ such that
$P\left(n\right)$ is true. So there is a least
integer $k\ge -m$ such that $P\left(k\right)$. For this
$k$ we have $k-1<x\le k$ since either
$k-1<-m\le x$ or else $-m\le k-1$ and therefore
$P(k-1)$ is false (since $k$ is least such that
$P\left(k\right)$ holds). Therefore $k=\lceil x\rceil $,
the upper integer part of $x$. To get the lower integer-part
$\lfloor x\rfloor =\left[x\right]$ just argue that if
$x=k$ then $k=\lfloor x\rfloor $ and if not then
$k-1<x<k$ so $k-1=\lfloor x\rfloor $.

This web page is available in xhtml, html and pdf. It is copyright and is one of Richard Kaye's Sequences and Series Web Pages. It may be copied under the terms of the Gnu Free Documentation Licence (http://www.gnu.org/copyleft/fdl.html). There is no warranty. Web page design and creation are by GLOSS.