# College Math Teaching

## March 6, 2010

### The Principle of Mathematical Induction: why it works

Filed under: induction, logic, transfinite induction, Uncategorized — collegemathteaching @ 11:03 pm

I am writing this post because I’ve seen that there is some misunderstanding of what mathematical induction is and why it works.

• What is mathematical induction? It is a common proof technique. Basically, if one wants to show that a statement is true in generality and that one can index the set of statements via the integers (or by some other appropriate index set), then one can use induction.

Here is a common example: suppose one wants to show that

$1 + 2 + 3 + ....+ k = (1/2)*(k)*(k+1)$ for all positive integers $k$
(for example, $1 + 2 + 3 + 4 + 5 = (1/2)*(5)*(5+1) = 15$).

Initial step: $1 = (1/2)*(1)*(1+1)= 1$ so the statement is true for $k = 1$.

Inductive step: assume that the formula holds for some integer $k$.
Finish the proof: show that if the formula holds for some integer $k$, then it holds for $k+1$ as well.

So $1 + 2 + 3 +....+ k + (k+1) = (1 + 2 + ...+ k) + (k+1) =(1/2)*(k)*(k+1) + (k + 1)$
(why? because we assumed that $k$ was an integer for which
$1 + 2 + 3 + ....+ k = (1/2)*(k)*(k+1)$. )

so $1 + 2 + 3 +....+ k + (k+1) = (1/2)*(k)*(k+1) + (k + 1) = ((1/2)*k + 1)*(k+1)$ (factor out a k+1 term)
$= (1/2)*2*((1/2)*k + 1)*(k+1) = (1/2)*(k+2)*(k+1)=(1/2)*(k+1)*(k+2)=(1/2)*(k+1)*(k+1 + 1)$
which is what we needed to show. So the proof would be done.

• Why does induction “prove” anything? Mathematical induction is equivalent to the so called “least positive integer” principle in mathematics.
• What is the least positive integer principle? It says this: “any non-empty set of positive integers has a smallest element”. That statement is taken as an axiom; that is, it isn’t something that can be proved.
Notice that this statement is false if we change some conditions. For example, is is NOT true that, say, any set of positive numbers (or even rational numbers) has a smallest element. For example, the set of all numbers between 0 and 1 (exclusive; 0 is not included) does NOT have a least element (not according to the “usual” ordering induced by the real number line; it is an easy exercise to see that the rationals can be ordered so as to have a least element). Why? Let $b$ be a candidate to be the least element. Then $b$ is between 0 and 1. But then $(1/2)b$ is greater than zero but is less than $b$; hence $b$ could not have been the least element. Neither could any other number.

Note that the set of negative integers has no least element; hence we need the condition that the integers are positive.

Notice also that there could be groups of positive integers with no greatest element. For example, Let $x$ be the largest element in the set of all even integers. But then $2x$ is also even and is bigger than $x$. Hence it is impossible to have a largest one.

• What does this principle have to do with induction? This is what: an induction proof is nothing more than a least integer argument in disguise. Lets return to our previous example for a demonstation; that is, our proof that $1 + 2 + ....+ n = (1/2)n(n+1)$

We start by labeling our statements: $1 = (1/2)(1)(1+1)$ is statement P(1),
$1 + 2 = (1/2)(2)(2+1)$ is statement P(2), …$1+2+...+ 5 = (1/2)(5)(5+1)$ is statement P(5) and so on.

We assume that the statement is false for some integer. The set of integers for which the statement is false has a least element by the least element principle for positive integers.

We assume that the first integer for which the statement is false is $k+1$. We can always do this, because we proved that the statement is true for $k = 1$, so the first possible false statement is $k = 2$ or some larger integer, and these integers can always be written in the form $k + 1$.

That is why the anchor statement (the beginning) is so important.

We now can assume that the statement is true for $n = 1,....n = k$ since $k+1$ is the first time the statement fails.

Now when we show “if statement P($k$) is true then P($k+1$) is also true (this is where we did the algebra to add up $1 + 2 + .....+ k + (k+1) = ((1/2)k(k+1)) + (k+1) )$. This contradicts that statement P($k+1$) is false.

Hence the statement cannot be false for ANY positive integer $k$.

• Weak versus strong induction. As you can see, the least positive integer principle supposes that the statement is true for all statements P(1) through P($k$), so in fact there is no difference (when inducting on the set of positive integers) between weak induction (which assumes the induction hypothesis for some integer $k$) and strong induction (which assumes the induction hypothesis for $n = 1$ through $n = k$).
• Other index sets: any index set that one has to induct on has to have the “least element principle” to its subsets. Also, if there is a cardinal w that has no immediate predecessor, then one must “reanchor” the induction hypothesis as $k = w$ prior to proceeding.