## The Principle of Mathematical Induction

If you have ever made a domino line (like the one made out of books in the video below), you are familiar with the general idea behind mathematical induction.

In order to get all of the dominoes to fall, two things need to happen:

1. The first domino must fall.

2. The dominos must be setup so that if any single domino falls, say the $k^{th}$ one in line, then we know that the next one in the line -- the $(k+1)^{th}$ one in line -- will also fall.

Suppose we are trying to prove some statement $S(n)$ is true for every positive integer $n$. For example, maybe $S(n)$ is the statement "The sum of the first $n$ positive odd numbers is $n^2$. For any given value of $n$, $S(n)$ might be trivial to verify. Certainly it is easy to check (via simple arithmetic) the aforementioned statement is true for any individual value of $n$:

$$\begin{array}{rlcl} S(1):& 1 &=& 1^2 \quad \quad \textrm{...clearly this is true;}\\ S(3):& 1 + 3 + 5 &=& 3^2 \quad \quad \textrm{...this works too;}\\ S(7):& 1 + 3 + 5 + 7 + 9 + 11 + 13 &=& 7^2 \quad \quad \textrm{...more arithmetic, but it checks out!} \end{array}$$

However, we desire to show that this works for all positive integers $n$. We can't check every possibility via arithmetic -- there are infinitely many possibilities!

Instead, we think of each $S(n)$ as a domino that either falls or doesn't fall, according to whether $S(n)$ is true or not true, respectively.

We may then reasonably conclude that $S(n)$ is true for every positive integer $n$ (i.e., all of the dominoes fall), if we know:

1. $S(1)$ is true (i.e., the first domino falls); and

2. If $S(k)$ is true for any particular value of $k$, then $S(k+1)$ must also be true
(i.e., if the $k^{th}$ domino falls, then the $(k+1)^{th}$ domino must also fall).

Formalizing the above method of argument, by removing the references to dominoes, we have:

The Principle of Mathematical Induction.

If, for any statement involving a positive integer, $n$, the following are true:
1. The statement holds for $n=1$, and
2. Whenever the statement holds for $n=k$, it must also hold for $n=k+1$
then the statement holds for for all positive integers, $n$.

In an inductive argument, demonstrating the first condition above holds is called the basis step, while demonstrating the second is called the inductive step. Further, the assumption that the statement holds for $n=k$ for some particular value of $k$ that is necessary to demonstrate the inductive step is called the inductive hypothesis.

Consider the following simple example of an argument by induction involving summations:

Suppose we believe the following is true for all positive integers $n$ and wish to prove this: $$\displaystyle{\sum_{i=1}^{n} i = \frac{n(n+1)}{2}}$$

Proof:

Starting with the basis step, we must show that the statement holds for $n=1$.

Note however, when $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n i = 1$$

While on the right side, if $n=1$, $$\frac{n(n+1)}{2} = \frac{1(1+1)}{2} = 1$$

Since the left and right sides agree in value, the statement is true when $n=1$

Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

Equivalently for this problem, we need to show if the following "inductive hypothesis" is true $$\sum_{i=1}^k i = \frac{k(k+1)}{2}$$ then it must also be true that $$\sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)}{2}$$

To this end, we will attempt to manipulate the left side of the above equation until it looks like the right side. We can use the inductive hypothesis to provide the transition from an expression involving $\sum$ to a simpler algebraic expression.

$$\begin{array}{rcl} \displaystyle{\sum_{i=1}^{k+1} i} &=& \displaystyle{\left( \sum_{i=1}^{k} i \right) + (k+1)}\\\\ &=& \displaystyle{\left( \frac{k(k+1)}{2} \right) + (k+1)}\\\\ &=& \displaystyle{\frac{k}{2}(k+1) + (k+1)}\\\\ &=& \displaystyle{(k+1) \left( \frac{k}{2} + 1\right)}\\\\ &=& \displaystyle{(k+1) \left( \frac{k+2}{2} \right)}\\\\ &=& \displaystyle{\frac{(k+1)(k+2)}{2}}\\\\ &=& \displaystyle{\frac{(k+1)((k+1)+1)}{2}} \end{array}$$

Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$: $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$