# Mathematical induction

https://arbital.com/p/mathematical_induction

by Douglas Weathers Jul 17 2016 updated Aug 9 2016

Proving a statement about all positive integers by knocking them down like dominoes.

The principle of mathematical induction is a proof technique in which a statement, $P(n)$, is proven about a set of natural numbers $n$. It may be best understood as treating the statements like dominoes: a statement $P(n)$ is true if the $n$-th domino is knocked down. We must knock down a first domino, or prove that a base case $P(m)$ is true. Next we must make sure the dominoes are close enough together to fall, or that the inductive step holds; in other words, we prove that if $k \geq m$ and $P(k)$ is true, $P(k+1)$ is true. Then since $P(m)$ is true, $P(m+1)$ is true; and since $P(m+1)$ is true, $P(m+2)$ is true, and so on.

# An example

We'll do an example to build our intuition before giving the proper definition of the principle. We'll provide yet another proof that $$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$ for all integers $n \ge 1$. First, let's check the base case, where $n=1$: $$1 = \frac{1(1+1)}{2} = \frac{2}{2} = 1.$$ This is (fairly obviously) true, so we can move forward with the inductive step. The inductive step includes an assumption, namely that the statement is true for some integer $k$ that is larger than the base integer. For our example, if $k\ge1$, we assume that $$1 + 2 + \cdots + k = \frac{k(k+1)}{2}$$ and try to prove that $$1 + 2 + \cdots + k + (k+1) = \frac{(k+1)([k+1]+1)}{2}.$$ Take our assumption and add $k+1$ to both sides: $$1+2+\cdots + k + (k+1) = \frac{k(k+1)}{2} + k + 1.$$ Now the left-hand sides of what we know and what we want are the same. Hopefully the right-hand side will shake out to be the same. Get common denominators so that the right-hand side of the above equation is $$\frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+2)(k+1)}{2} = \frac{(k+1)([k+1]+1)}{2}.$$ Therefore, $$1 + 2 + \cdots + k + (k+1) = \frac{(k+1)([k+1]+1)}{2}$$ as desired.

Let $P(n)$ be the statement for $n \ge 1$ that the sum of all integers between 1 and $n$ is $n(n+1)/2$. At the beginning we showed that the base case, $P(1)$, is true. Next we showed the inductive step, that if $k \ge 1$ and $P(k)$ is true, then $P(k+1)$ is true. This means that since $P(1)$ is true, $P(2)$ is true; and since $P(2)$ is true, $P(3)$ is true; etc., so that $P(n)$ is true for all integers $n \ge 1$.

# Definition for the natural numbers

We are ready to properly define mathematical induction.

## Weak mathematical induction

Let $P(n)$ be a statement about the natural numbers. Then $P$ is true for all $n \ge m$ if

1. $P(m)$ is true, and
2. For all $k \ge m$, $P(k+1)$ is true if $P(k)$ is.

## Strong mathematical induction

Let $P(n)$ be a statement about the natural numbers. Then $P$ is true for all $n \ge m$ if

1. $P(m)$ is true, and
2. For all $k \ge m$, $P(k)$ is true so long as $P(\ell)$ is true for all $m \le \ell < k$.

A note: strong mathematical induction is a variant on mathematical induction by requiring a stronger inductive step, namely that the statement is true for all smaller indices, not just the immediate predecessor.

# Induction on a well-ordered set

Well done if your immediate response to the above material was, "Well, am I only restricted to this technique on the natural numbers?" No. As long as your index set is well-ordered, then strong mathematical induction will work.

However, if your ordered set is not well-ordered, you can prove properties 1 and 2 above, and still not have it hold for all elements beyond the base case. For instance, consider the set of nonnegative real numbers, and let $P(x)$ be the claim $x\leq 1$. Then $P(0)$ is true, and for all real numbers $x\ge 0$, $P(x)$ is true whenever $P(y)$ is true for all $0 \le y < x$. But of course $P(2)$ is false.

The principle of mathematical induction is a proof technique in which a statement, $P(n)$, is proven about a set of natural numbers $n$\. It may be best understood as treating the statements like dominoes: a statement $P(n)$ is true if the $n$\-th domino is knocked down\. We must knock down a first domino, or prove that a base case $P(m)$ is true\. Next we must make sure the dominoes are close enough together to fall, or that the inductive step holds; in other words, we prove that if $k \\geq m$ and $P(k)$ is true, $P(k+1)$ is true\. Then since $P(m)$ is true, $P(m+1)$ is true; and since $P(m+1)$ is true, $P(m+2)$ is true, and so on\.
We'll do an example to build our intuition before giving the proper definition of the principle\. We'll provide yet another proof that $$1 + 2 + \\cdots + n \= \\frac{n(n+1)}{2}$$ for all integers $n \\ge 1$\. First, let's check the base case, where $n\=1$: $$1 \= \\frac{1(1+1)}{2} \= \\frac{2}{2} \= 1.$$ This is $$fairly obviously$$ true, so we can move forward with the inductive step\. The inductive step includes an assumption, namely that the statement is true for some integer $k$ that is larger than the base integer\. For our example, if $k\\ge1$, we assume that $$1 + 2 + \\cdots + k \= \\frac{k(k+1)}{2}$$ and try to prove that $$1 + 2 + \\cdots + k + (k+1) \= \\frac{(k+1)($k+1$+1)}{2}.$$ Take our assumption and add $k+1$ to both sides: $$1+2+\\cdots + k + (k+1) \= \\frac{k(k+1)}{2} + k + 1.$$ Now the left\-hand sides of what we know and what we want are the same\. Hopefully the right\-hand side will shake out to be the same\. Get common denominators so that the right\-hand side of the above equation is $$\\frac{k(k+1)}{2} + \\frac{2(k+1)}{2} \= \\frac{(k+2)(k+1)}{2} \= \\frac{(k+1)($k+1$+1)}{2}.$$ Therefore, $$1 + 2 + \\cdots + k + (k+1) \= \\frac{(k+1)($k+1$+1)}{2}$$ as desired\.
I think it would be worthwhile to explicitly call out that what's happening here is that we're replacing $n$ in the original equation with $k+1$.