Induction

Induction is a reasoning method to demonstrate true properties for the natural numbers:

$\mathbb{N}={0, 1, 2,...}$
In Computer Science, this is widely used since a lot of entities can be mapped to them.
To illustrate the process through an example, say we are given the following proposition -something that is either true or false:

Proposition. $Let\; p(n) ::= n^2 + n + 41$

$\forall n\!\in\!\mathbb{N},\; p(n)\; is\; prime.$
That is our proposition $P(n)$ . To that end, we may calculate the successive values of $p(n)$ :
$\begin{array}{lcl}p(0)=41\;is\;prime \\p(1)=43\;is\;prime \\p(2)=47\;is\;prime \\p(3)=53\;is\;prime \\p(4)=61\;is\;prime \\\vdots\end{array}$
If we continue to calculate the values for $p(n)$ for bunch of values we may believe that the proposition is true. Alas, you can’t conclude that:

$\forall n\!\in\!\mathbb{N}\ P(n)$

holds true because verifying an assertion for a finite set of values doesn’t prove anything for the whole infinite set of $\mathbb{N}$ , no matter the amount of values checked. As a point in case:

$p(40)=40^2+40+41=40(40+1)+41=41(40 + 1) = 41^2$
which is clearly not prime.

Example: A true proposition

We have to demonstrate by induction that:

$P(n)::=\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{1}{n(n+1)}=\frac{n}{n+1}$

First, let’s remove the ellipses and use a summation to represent the formulation:

$P(n)::=\sum_{k=1}^n \frac{1}{k(k+1)}=\frac{n}{n+1}$

Induction hypothesis: P(n)
Basis step: $P(1)::=\frac{1}{2}=\frac{1}{2}$
Inductive step:
$\begin{array}{lcl}\forall n\!\in\mathbb{N} \ P(n)\to P(n+1) \\ \\P(n+1)::=\overbrace {\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{1}{n(n+1)}}^{P(n)}+\frac{1}{(n+1)(n+1+1)}=\frac{n+1}{n+2} \\ \\P(n+1)::= \frac{n}{n+1}+\frac{1}{(n+1)(n+2)}=\frac{n+1}{n+2}\\ \\P(n+1)::= \frac{n(n+2)+1}{(n+1)(n+2)}=\frac{n+1}{n+2}\\ \\P(n+1)::= n(n+2)+1 = (n+1)^2\\ \\P(n+1)::= n^2+2n+1 = n^2+2n+1\end{array}$

We just used a basic inference rule named modus ponens: if $p$ is true and $p \to q$ is true, then $q$ is true, also written:

$\frac{p, \;p \to q}{q}$

Therefore, the Induction Axiom can be expressed as:

$\frac{P(0),\;\forall m\in\mathbb{N}\;P(m) \to P(m+1)}{\forall n\in\mathbb{N} \ P(n)}$

Demonstrating the Induction Axiom

But, how can we demonstrate the Induction Axiom itself? To that end, we can use reduction to the absurd:

Hypothesis: $P(N)$ is not true for every $n\in\mathbb{N}$ , i.e. there are natural numbers for which the proposition is false.
Using the Well-Ordering Principle of the natural numbers, we can state:
$\exists\;n^{*}\in\mathbb{N} \/\ is\ the\ smallest\ among\ the\ ones\ not\\ satisfying\ the\ proposition$
$P(1)$ is true by induction $\Leftrightarrow n^{*} \neq 1 \Rightarrow P(n^{*}-1)$ is true.
(If $n^{*}$ is not 1, then $P(n^{*}-1)$ must be true because $n^{*}$ is the smallest of all the natural numbers for which the proposition is false.)
$P(n^{*}-1)$ is true $\Rightarrow P(n^{*})$ is true by induction.
$P(n^{*})$ is true by induction, but at the same time $P(n^{*})$ is false by 2. Hence, the initial hypothesis must be false.

References

Mathematics for Computer Science at MIT OpenCourseWare

This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution 2.0 UK: England & Wales License.

Tags: maths

This entry was posted on Saturday, December 26th, 2009 at 3:06 PM and is filed under Computer Science. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Induction”

Storage Lower Openshaw Says:
September 19th, 2010 at 5:27 AM
Really like this post, thanks for writing.

TICS

Induction

One Response to “Induction”

Leave a Reply

Categories

Archives

Pages