Variations on Induction

There are variations on induction arguments that may work better in certain circumstances.

As a simple example, if one wished to show a statement holds for all integers $n \ge n_0$, one could do so by showing:

  1. the statement holds when $n = n_0$; and
  2. when the statement holds for some $n=k$, it must also hold for $n=k+1$.
This is a slight modification of the original principle of mathematical induction, but is easily shown to be equivalent.

As an example, suppose one wished to prove $2^n \lt n!$ for $n = 4, 5, 6, \ldots$ (Interestingly, for $n \lt 4$, this statement does not hold!)

Arguing by induction, we establish the basis step by considering $n = 4$. For this value of $n$, the left side is $2^4 = 16$ and the right side is $4! = 24$. As $2^4 \lt 4!$, the basis step is established.

Moving on to the inductive step, we assume that the statement holds for some $n=k$, and try to prove it must also hold for $n=k+1$. That is to say, we hope to show that if $2^k \lt k!$, then $2^{k+1} \lt (k+1)!$

Noting that one could turn the left side of the first inequality ($2^k$) into the left side of the second inequality ($2^{k+1}$) by multiplying it by 2, we try multiplying both sides of the inequality by $2$ to deduce

$$2^k \lt k! \implies 2^{k+1} \lt 2 \cdot k!$$ We would have been more happy if the right side of our inequality had become $(k+1)!$, but instead we have $2 \cdot k!$. This is not a large setback, however, as replacing the $2$ with a $(k+1)$ will only make the expression on the right side bigger (as $k+1 \gt 2$ for every $k \ge 4$), and thus preserve the inequality, while at the same time turn the right side into the desired $(k+1)!$, as shown below: $$2^{k+1} \lt 2 \cdot k! \lt (k+1) \cdot k! = (k+1)!$$ or more succinctly, $$2^{k+1} \lt (k+1)!$$ This, of course, was what we needed to show to establish the inductive step.

With both the basis and inductive steps accomplished, our modified principle of mathematical induction tells us that $2^n \lt n!$ holds for all integers $n \ge 4$, proving our claim.

As another variation on induction, suppose one wished to show some statement held for all positive even integers. In this case, we show:

  1. the statement holds when $n=2$; and
  2. when the statement holds for some $n=k$, it must also hold for $n=k+2$
Note how the inductive step changes from talking about $n=k+1$ to $n=k+2$ as the difference between any two successive even numbers is $2$.

We could do essentially the same thing to prove a statement holds for all positive odd integers $n$, except that we would establish our basis step again at $n=1$.

Interestingly, we can combine these two tactics to show a statement holds for all integers $n \gt 0$, since the set of such $n$ is the union of all positive odd integers with all positive even integers. The combined strategy would be to show that

  1. the statement holds both when $n=1$ and $n=2$; and
  2. when the statement holds for some $n=k$, it must also hold for $n=k+2$

To see why this works, instead of thinking of the various values of $n$ as a line of dominoes, where any domino that falls causes the next one in line to fall -- think of the various values of $n$ as a line of people who upon getting hit in the head by a rock throw another rock at the person two ahead of them in line. Before -- with the dominoes -- one had to make the first domino fall to get all the rest to fall. Here, we must drop rocks on the the first two people's heads to start the chain reaction whereby everyone in line gets hit in the head with a rock, as seen in the graphic below:

As a related example, consider the proof that for for every integer $n \gt 7$, there exist non-negative integers $x$ and $y$ such that $n = 3x+5y$, as shown below:

We have 3 cases: $n$ could have remainder $0$, $1$, or $2$ upon division by $3$.

We establish the base step for each of these in the following order: remainders of $2$, $0$, and $1$ (as starting with $n=8$ that is the order in which they appear).

$$\begin{align*} 8 &= 3 \cdot 1 + 5 \cdot 1\\ 9 &= 3 \cdot 3 + 5 \cdot 0\\ 10 &= 3 \cdot 0 + 5 \cdot 2\\ \end{align*}$$

To argue the inductive step for each case, notice that if the statement is true for some $n=k$, then we can find integers $x$ and $y$ so that $k=3x+5y$, which in turn implies $k+3 = 3(x+1)+5y$. As $n=k+3$ is the next value of $n$ after $k$ with the same remainder as $k$, the inductive step is established.

Hence, the claim holds.

Strong Induction

Another important variant on induction shown below, which is called complete induction or strong induction, requires in its inductive step that we assume not just that the statement holds for $n = k$ but rather that it holds for all $n \le k$.

The (Second) 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 all $n \le k$, it must also hold for $n=k+1$
then the statement holds for all positive integers, $n$.

At first blush, it seems like this might be fundamentally different from the versions of induction examined so far. However, this second principle of mathematical induction is actually completely equivalent to the first principle of mathematical induction. (If you don't believe this, check out the proof). Despite the equivalence, this form of induction can often significantly shorten the work needed to prove some claims.

As an example, consider the following proof that if a sequence $a_n$ is defined by $a_1 = 5$, $a_2 = 7$, and $a_n = 3a_{n-1} - 2a_{n-2}$, then $a_n = 3 + 2^n$ for all positive integers $n$.

We establish two base steps by observing $a_n = 3 + 2^n$ yields the correct values for $n = 1$ and $n=2$:

$$\begin{align*} a_1 &= 3 + 2^1 = 5\\ a_2 &= 3 + 2^2 = 7 \end{align*}$$

To establish the inductive step (for strong induction), we suppose that $a_n = 3 + 2^n$ for all $n \le k$ for some integer $k$.

We then need to show that $a_{k+1} = 3 + 2^{k+1}$.

To this end, note that

$$\begin{split} a_{k+1} &= 3a_k - 2a_{k-1}\\ &= 3(3+2^k) - 2(3+2^{k-1}) \quad {\small \textrm{after applying the strong inductive hypothesis twice}}\\ &= 9 + 3 \cdot 2^k - 6 - 2^k\\ &= 3 + 2 \cdot 2^k\\ &= 3 + 2^{k+1} \end{split}$$

We have shown what we needed to show. Thus, by the principle of strong induction $a_n = 3 + 2^n$ for all positive integers $n$.

The Well Ordering Principle

As our final variation on induction, we present a principle that is completely equivalent to all of the forms of induction seen above, but doesn't even remotely resemble induction in its statement:

The Well-Ordering Principle.

Every non-empty set of positive integers contains a smallest element.

Note, one could replace the words "positive integers" with "non-negative integers", or even "integers greater than some given $M \in \mathbb{Z}$", and still have an equivalent principle. Depending on what text you might read, these variations are sometimes seen.

To see the connection between the Well-Ordering Principle and the Principle of Mathematical Induction, consider the following standard way to use Well Ordering to prove that some property $P(n)$ holds for every positive integer $n$:

To prove that "$P(n)$ is true for all $n \in \mathbb{N}$" using the Well Ordering Principle:

  1. Define the set $S$ of counterexamples to $P$ being true. Namely, define $$S = \{ n \in \mathbb{N} \, : \, P(n) \textrm{ is false}\}$$
  2. Argue indirectly, and assume that $S$ is nonempty
  3. By the Well Ordering Principle, there must be a smallest element $k$ in $S$
  4. Reach a contradiction (somehow) -- often by showing how to use $k$ to find another member of $S$ that is smaller than $k$
  5. Conclude the assumption must be false, and that it is instead the case that $S$ must be empty
  6. Consequently no counterexamples exist, which means that $P(n)$ is true for all $n \in \mathbb{N}$. QED

This is best understood through an example. Suppose we again attempt to prove (only this time with the Well Ordering Principle) that the following holds for all positive integers $n$: $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$

Proof

We argue indirectly. Assume this statement is false for at least one positive integer $n$.

Now, let $S$ be the set defined by $$S = \left\{n \in \mathbb{Z}^+ \textrm{ such that } \sum_{i=1}^n i \neq \frac{n(n+1)}{2} \right\}$$ $S$ is non-empty by our assumption, and contains only non-negative values of $n$, so the well-ordering principle applies, and guarantees that $S$ has a least element.

Suppose we call this least element $k$.

Remember, $0 \notin S$ since $0 \notin \mathbb{Z}^+$.

Also, $1 \notin S$, as simply plugging in $n=1$ into the left and right hand sides of the statement reveals it is true for this value of $n$.

Thus $k$, which is in $S$, must be greater than $1$.

However, if $k > 1$, then $k-1$ is a positive integer less than $k$, the minimum value for which our statement is false. Consequently, the statement must be true when $n=k-1$.

Hence, $$\sum_{i=1}^{k-1} i = \frac{(k-1)((k-1)+1)}{2} = \frac{k(k-1)}{2}$$

Importantly, knowing this allows us to investigate the validity of the statement when $n=k$ from another direction.

Consider the following sum, $$\begin{array}{rcl} \displaystyle{\sum_{i=1}^k i} &=& \displaystyle{\left[ \sum_{i=1}^{k-1} i \right] + k}\\\\ &=& \displaystyle{\frac{k(k-1)}{2} + k}\\\\ &=& \displaystyle{\frac{k^2 - k}{2} + \frac{2k}{2}}\\\\ &=& \displaystyle{\frac{k^2 + k}{2}}\\\\ &=& \displaystyle{\frac{k(k+1)}{2}} \end{array}$$

But this means that the statement is true when $n=k$, which contradicts $k$ being the least integer for which the statement is false.

Having reached a contradiction, it must be the case that the opposite of our assumption is true. Hence, the statement $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$ is true for every positive integer $n$.