5.1. Induction#

Recall from Section 1.3, that existence proofs were quite easy. We just find one example which satisfies the statement. Proving that a statement holds for every possible choice is much more challenging.

Mathematical Induction is a mathematical technique to reason about, and prove, that a statement holds for every choice of natural number.

Consider the classic and hilarious problem of hot dogs and hot dog buns.

If a store sells hot dog buns in packs of either \(6\) or \(13\) a baker’s dozen, can you always purchase a combination of packages so there are exactly enough buns for 60 or more hot dogs?

  • For \(60\) hot dogs, \(10\) packs of \(6\) and \(0\) packs of \(13\) works; \(60 = 10\cdot 6\)

  • For \(61\) hot dogs, \(8\) packs of \(6\) and \(1\) pack of \(13\) works; \(61 = 8\cdot 6 + 1\cdot 13\)

  • For \(62\) hot dogs, \(6\) packs of \(6\) and \(2\) packs of \(13\) works; \(62 = 6\cdot 6 + 2 \cdot 13\)

  • For \(63\) hot dogs, \(4\) packs of \(6\) and \(3\) packs of \(13\) works; \(63 = 4\cdot 6 + 3 \cdot 13\)

  • For \(64\) hot dogs, \(2\) packs of \(6\) and \(4\) packs of \(13\) works; \(64 = 2\cdot 6 + 4 \cdot 13\)

  • \(\cdots\)

We could keep going in this way to show that it works for any choice of number of hot dogs. However, we would run out of paper, or ink, or time in the universe, to prove this for all numbers of hot dogs. This is where induction comes in!

5.1.1. Mathematical Induction#

Consider the predicate statement \(P(n)\) for some natural number \(n\). If we know that \(P(0)\) is true, \(P(1)\) is true, and \(P(2)\) is true, then is \(P(3)\) true? Is \(P(1000)\) true? This is the job of mathematical induction.

Let us first consider some metaphors.

Falling Dominoes

Consider a sequence of falling dominoes.

../_images/dominoes.jpg

Fig. 5.1 A sequence of falling dominoes.#

We know that if the first domino is knocked over, then the second domino will be knocked over. If the second domino is knocked over, then the third domino will be knocked over, and so on. If the \(k\)th domino is knocked over then the \(k+1\)th domino will be knocked over.

Therefore, for any number of dominoes, if the first is knocked over than they all will be knocked over.

An Infinite Staircase

Consider a very, very, very long staircase.

../_images/staircase.jpg

Fig. 5.2 Diminish and Ascend by David McCracken#

Can you reach the top of the staircase? If you can reach the first step, then you can reach the second step. If you can reach the second step, then you can reach the third step. If you can reach the third step, then you can reach the fourth step, and so on. If you can reach the \(k\)th step, then you can reach the \(k+1\)th step.

Therefore, assuming you can reach the first step, you can eventually reach any higher up step.

Principle of Mathematical Induction

We look to prove that \(P(n)\) is true for all natural numbers \(n\) that are greater than some natural number \(n_0\).

  1. Basis Step. Show directly that \(P(n_0)\) is true.

  2. Inductive Step. Show that the implication \(P(k) \rightarrow P(k+1)\) is true for all \(k \in \mathbb{N}\), \(k \geq n_0\).

If both 1. and 2. can be shown to be true, then by induction \(P(n)\) is true for all natural numbers greater than or equal to \(n_0\).

We prove the inductive step of mathematical induction by following the inductive hypothesis. Just as with proving any implication, we assume the left hand side is true, and then prove that the right hand side must also be true. In mathematical induction, assuming \(P(k)\) is the inductive hypothesis and we “assume that the inductive hypothesis is true” in order to show \(P(k+1)\) must also be true.

Staircase by Induction

Consider the case of the infinite staircase. If we can reach the first step then we can reach any step.

Proof:

Let \(P(n)\) be “I can reach the \(n\)th step of the staircase”. By hypothesis, we can reach the first step, so \(P(1)\) is true. Therefore, we look to prove that \(P(n)\) is true for all \(n \geq 1\).

Assume the inductive hypothesis \(P(k)\) is true. That is, assume we can reach the \(k\)th step. Since we can reach the \(k\)th step we can surely reach the next step, the \(k+1\)th step. Therefore, by induction \(P(n)\) is true for all \(n \geq 1\). Thus, we can reach any step of the staircase. \(\blacksquare\)

Formally, mathematical induction gives us the following implication:

\[ \left( P(n_0) \ \land\ \forall k \geq n_0\ (P(k) \rightarrow P(k+1))\ \right) \quad \rightarrow \quad \forall n \geq n_0\ P(n) \]

Notice that both parts of the left hand side must be true in order to imply the right-hand side. If either the base case does not hold or the inductive step does not hold, then induction does not apply.

In the inductive step, we do not assume that \(P(k)\) is true for all choices of \(k\). Rather, we show that if \(P(k)\) is true, then \(P(k+1)\) must also be true.

First Proof by Induction

Recall the summation formula \(\sum_{i=1}^n i = \frac{n(n+1)}{2}\). Prove this formula is correct for all \(n \geq 1\).

Proof:

  1. Basis Step. \(\sum_{i=1}^1 i = 1 = \frac{1(2)}{2}\). Therefore, the formula is correct for \(n=1\).

  2. Inductive step. Assume the inductive hypothesis, that \(\sum_{i=1}^k i = \frac{k(k+1)}{2}\).

We must show that \(\sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}\).

\[\begin{align*} \sum_{i=1}^{k+1} i &= 1 + 2 + 3 + \cdots + k + (k+1) \\[1em] &= \sum_{i=1}^k i + (k+1) \\[1em] &= \frac{k(k+1)}{2} + (k+1) \quad\quad \text{by inductive hypothesis} \\[1em] &= \frac{k(k+1) + 2(k+1)}{2} \\[1em] &= \frac{k^2 + 3k + 2}{2} \\[1em] &= \frac{(k+1)(k+2)}{2} \end{align*}\]

Therefore, by induction, \(\sum_{i=1}^n i = \frac{n(n+1)}{2}\) for all \(n \geq 1\).

Tip

Mathematical induction reasons about statements involving the natural numbers. However, recall that we can form a bijection between the natural numbers and any countably infinite set. Therefore, mathematical induction can be applied to any countably infinite set.

Why does induction work?#

But, why does mathematical induction work? It is based on the well-ordering principle.

Definition (well-ordering principle)

The well-ordering principle states that every non-empty subset of the positive integers has a least element.

Let us use this principle to prove that mathematical induction works.

Recall the formal statement of mathematical induction, taking \(n_0 = 1\) for simplicity:

\[ \left( P(1) \ \land\ \forall k \geq 1 \ (P(k) \rightarrow P(k+1))\ \right) \quad \rightarrow \quad \forall n \geq 1\ P(n) \]

Suppose the left hand side is true. That is, \(P(1)\) is true and the implication \(P(k) \rightarrow P(k+1)\) is true for all \(k \geq 1\).

Proceed by contradiction and assume that there is some positive integer \(x\) such that \(P(x)\) is false. Define \(S\) as \(\{ \ s \,\mid\, P(s) \text{ is false }\}\). By assumption, \(P(x)\) is false and thus \(S\) is non-empty.

By the well-ordering property, \(S\) has a minimum element. Call it \(m\). We know \(m \neq 1\) since our hypothesis is that \(P(1)\) is true. So, \(m \geq 2\) and thus \(m-1\) is a positive integer. Since \(m -1 < m\), \(m-1\) cannot be in \(S\). Thus, \(P(m-1)\) is true.

But, out hypothesis says that \(P(k) \rightarrow P(k+1)\) for all \(k > 1\). Therefore, since \(P(m-1)\) is true, it must be that \(P(m)\) is true. This is a contradiction! Therefore, our assumption false; there does not exist an \(x\) such that \(P(x)\) is false.

Hence, \(P(n)\) is true for all \(n \geq 1\). \(\blacksquare\)

Now, try induction by yourself.

Proving Summations

Show that the sum of the first \(n\) positive integers is equal to \(n^2\). That is, \(1 + 3 + 5 + \cdots + (2n - 1) = n^2\)

For example, \(1,3,5,7,9,11\) is the first \(6\) odd integers and we have \(1 + 3 + 5 + 7 + 9 + 11 = 36 = 6^2\).

Proving Summations

We proceed by induction.

Clearly, the sum of the first \(1\) positive integers is \(1^2\).

Assume the inductive hypothesis, that \(1 + 3 + 5 + 7 + \ldots + (2k - 1) = k^2\) Then, we have:

\[\begin{split} 1 + 3 + 5 + \ldots + (2k -1) + (2k + 1) &= k^2 + (2k + 1) \quad \text{by the inductive hypothesis} \\[1em] &= k^2 + 2k + 1 \\[1em] &= (k+1)^2 \end{split}\]

Therefore, by induction the sum of the first \(n\) positive integers is equal to \(n^2\) for all positive integers \(n \geq 1\). \(\blacksquare\).

More Induction Examples#

Here’s another example. This time, with inequalities.

Proof by Induction with Inequalities

Use mathematical induction to prove that \(n < 2^n\) for all positive integers \(n\).

Proof:

We can let \(P(n)\) be “\(n < 2^n\)”.

For the basis step, \(P(1)\) is true since \(1 < 2^1 = 2\).

For the inductive step, assume \(P(k)\) is true. That is, \(k < 2^k\), for some positive integer \(k\). We will now show that \(k + 1 < 2^{k+1}\) must also be true.

\[\begin{align*} k &< 2^k &\quad\quad \text{by inductive hypothesis} \\[1em] k+1 &< 2^k + 1 \\[1em] k+1 &< 2^k + 1 \leq 2^k + 2^k &\quad\quad \text{$1 \leq 2^k$ since $k$ is positive} \\[1em] k+1 &< 2^k + 1 \leq 2\cdot 2^k \\[1em] k+1 &< 2^k + 1 \leq 2^{k+1} \\[1em] k+1 &< 2^{k+1} \end{align*}\]

Hence, by induction, \(n < 2^n\) for all \(n \geq 1\). \(\blacksquare\)

Here’s another example. This time, using sets.

Proof by Induction with Sets

Use mathematical induction to prove that \(|\mathcal{P}(A)| = 2^{|A|}\) for a finite set \(A\).

Proof:

Recall that the size of the power set of \(A\) is the number of subsets of \(A\). We can let \(P(n)\) be “a finite set of size \(n\) has \(2^n\) subsets.

For the basis step, \(P(0)\) is clearly true since \(2^0 = 1\) and the empty set has exactly one subset, the empty set itself.

For the inductive step, assume that \(P(k)\) is true. That is, a finite with \(k\) elements has \(2^k\) subsets. Now, let \(S\) be a set with \(k+1\) elements. Let \(a\) be an element of \(S\) and define \(T = S \setminus \{a\}\).

Clearly, \(|T| = k\). Therefore, \(T\) has \(2^k\) subsets by the inductive hypothesis.

Now, notice that \(S\) also has the element \(a\) which is not in \(T\) nor any of the subsets of \(T\). Clearly, since \(T \subset S\), any subset of \(T\) is also a subset of \(S\). Additionally, for any subset of \(T\) we can construct a new subset of \(S\) by adding the element \(a\) to that subset.

Therefore, for each subset of \(T\) there are two possible subsets of \(S\). Counting them, we have that \(S\) has \(2 \cdot 2^k = 2^{k+1}\) subsets. Since \(|S| = k+1\), we have that \(P(k+1)\) is true.

Hence, by mathematical induction, \(P(n)\) is true for all \(n \geq 0\). \(\blacksquare\)

An Induction Cheatsheet#

Every proof by induction follows the same general template.

Induction Cheatsheet

  1. Express the statement to be proved in the form “\(\forall n \geq n_0, P(n)\)”, for some integer \(n_0\).

  2. Write “Basis Step.” and then prove that \(P(n_0)\) is true.

  3. Write “Inductive Step.” and state the inductive hypothesis in the form “assume that \(P(k)\) is true for some integer \(k \geq n_0\)”

  4. State what you look to prove. That is, state what \(P(k+_1)\) means.

  5. Prove \(P(k+1)\) must be true, assuming \(P(k)\) is true. Ensure this proof is correct for any choice of \(k\).

  6. Identify the conclusion of the inductive step by stating something of the form “therefore, \(P(k+1)\) holds, assuming \(P(k)\) does.”

  7. State the final conclusion: “By mathematical induction, \(P(n)\) is true for all \(n \geq n_0\).”

5.1.2. Strong Induction#

“Strong” induction is a variant of mathematical induction which is sometimes easier to use than the “normal” induction.

Strong induction is also called the second principle of mathematical induction or complete induction.

It is called strong induction, because it makes a stronger hypothesis than mathematical induction. Informally, strong induction assumes that the condition \(P(k)\) holds for all values less than or equal to \(k\). Therefore, our inductive hypothesis is now:

\[ P(n_0) \land P(n_0 + 1) \land \cdots \land P(k-1) \land P(k) \rightarrow P(k+1) \]

Consider again the infinite staircase.

Staircase by Strong Induction

Suppose that you can reach the first and second step of the staircase. Further suppose that you can only jump between steps; if you are on step \(n\), then you can jump to step \(n+2\).

Show that you can then reach any step.

Proof:

We proceed by strong induction. Let \(P(n)\) be “I can reach the \(n\)th step of the staircase”. By hypothesis, we can reach the first step and second step. So, \(P(1)\) and \(P(2)\) are true. This is our basis step.

For the inductive step, we assume the inductive hypothesis and thus we can reach all the steps from the 1st to the \(k\)th, for \(k \geq 2\). Since \(k \geq 2\), \(k-1 \geq 1\). Thus, we can certainly reach the \(k-1\)th step by the inductive hypothesis. We can then jump to the \(k+1\) step. Thus, \(P(k+1)\) is true.

Therefore, by strong induction, \(P(n)\) is true for all \(n \geq 1\). That is, we can reach all steps of the staircase.

So why use strong induction over regular induction? Both are actually equivalent in “power”. They can both be used to solve the same things, and none can prove something the other cannot.

We simply make use of strong induction or normal mathematical induction depending on which is easier for the given problem. Let’s see some example that are easier to prove using strong induction.

Existence Proof for the Fundamental Theorem of Arithmetic

Theorem

If \(n>1\) is an integer, then \(n\) can be written as a product of primes.

Proof:

Let \(P(n)\) be “\(n\) can be written as a product of primes”.

Basis step: \(P(2)\) is true since \(2\) it itself a prime.

Inductive step: Let the inductive hypothesis be that \(P(i)\) is true for all \(i\), \(2 \leq i \leq k\). We will show that \(P(k+1)\) must be true.

If \(k+1\) is prime, then it is already written as a product of primes (itself) and thus \(P(k+1)\) is true. Otherwise, \(k+1\) is a composite number and can be written as the product of two integers greater than 1, say \(a\) and \(b\). That is, \(k+1 = ab\) with \(2 \leq a < k+1\) and \(2 \leq b < k+1\). This is obvious since \(k\) is greater than 2 and thus both \(a\) and \(b\) must be greater than \(2\).

By the inductive hypothesis, \(P(a)\) is true and \(P(b)\) is true. Since \(k+1 = a\cdot b\), then \(P(k+1)\) is also a product of primes by replacing \(a\) and \(b\) by their respective product of primes.

Therefore, by strong induction, \(P(n)\) is true for all \(n \geq 2\). \(\blacksquare\)

Let’s return to the problem of hot dogs and hot dog buns. Can you use structure induction to prove it?

Strong induction of hot dogs

If a store sells hot dog buns in packs of either \(6\) or \(13\), show using strong induction that you can always purchase a combination of packages so there are exactly enough buns for 60 or more hot dogs.

Strong induction of hot dogs

Proof: we proceed by strong induction.

Let \(P(n)\) be “exactly \(n\) hot dog buns can be formed from packs of \(6\) and packs of \(13\) buns”.

For the basis step, we show \(P(60), P(61), P(62), P(63), P(64), P(65)\) all hold.

  • For \(60\), we use \(10\) packs of \(6\).

  • For \(61\), we use \(8\) packs of \(6\) and \(1\) pack of \(13\).

  • For \(62\), we use \(6\) packs of \(6\) and \(2\) packs of \(13\).

  • For \(63\), we use \(4\) packs of \(6\) and \(3\) packs of \(13\).

  • For \(64\), we use \(2\) packs of \(6\) and \(4\) packs of \(13\).

  • For \(65\), we use \(0\) packs of \(6\) and \(5\) packs of \(13\).

For the inductive step, assume that \(P(i)\) is true for all \(i\), \(60 \leq i \leq k\), where \(k \geq 65\). We will show \(P(k+1)\) is true.

By the inductive hypothesis, \(P(k-5)\) holds. Thus, add a pack of \(6\) to the packs of buns for \(k-5\) hot dogs and we have exactly enough buns for \(k-5+6 = k+1\) hot dogs.

Hence, by strong induction, \(P(n)\) holds for all \(n \geq 60\). \(\blacksquare\)

5.1.3. Well-Ordering Principle#

Recall that the well-ordering principle states that every non-empty subset of the positive integers has a least element. This can be proved by induction. In fact, this property is equivalent to mathematical induction and can be used to prove statements just like induction.

First, a generalization.

Definition (well-ordered)

A set is well-ordered is every one of its non-empty subsets has a least element.

Clearly, the natural numbers \(N\) is well-ordered under the ordering induced by “less than”. As another example, the list of words in the English language are well-ordered under lexicographical ordering (dictionary order).

Let us see an example which uses well-ordering to solve a statement similar to induction.

Proof by well-ordering

Euclidean division states that if \(a\) is an integer and \(b\) is a positive integer, then there are integers \(q\) and \(r\) such that \(a = bq + r\) and \(0 \leq r < d\).

Proof:

Let \(a, b\) be integers satisfying the hypothesis of Euclidean division. Let \(S\) be the set of non-negative integers of the form \(a - bq\), for some integer \(q\). The set is non-empty because we can choose \(q\) arbitrarily.

By the well-ordering principle, \(S\) has a least element. Call it \(r\). since \(r \in S\), \(r\) is non-negative. Moreover, \(r = a - bq_0\) for some integer \(q_0\).

It must also be that \(r < b\). Proceed by constriction. Assume that \(r \geq b\). Then, another element of \(S\) is \(a - b(q_0 + 1)\) where \(a - b(q_0 + 1) = a - bq_0 - b = r - b\). where \(r - b \geq 0\) since \(r \geq b\). But, \(r\) was the smallest element of \(S\), so it cannot be that \(r \geq b\). Hence, \(r < b\).

By the well-ordering principle integers \(q, r\) exist satisfying \(a = bq + r\) and \(0 \leq r < b\).

5.1.4. Exercises#

Exercise 5.1

Use mathematical induction to prove that \(2^n < n!\) for every integer \(n \geq 4\).

Exercise 5.2

Use mathematical induction to prove that \(n^3 - n\) is divisible by \(3\) for all positive integers \(n\).

Exercise 5.3

Use mathematical induction to prove that \(n^2 + n\) is divisible by \(2\) for all integers \(n \geq 1\).

Exercise 5.4

Use mathematical induction to prove that \(5^n - 1\) is divisible by \(4\) for all integers \(n \geq 1\).

Exercise 5.5

Use mathematical induction to prove that \(n^2 < 2^n\) for all integers \(n \geq 5\).

Exercise 5.6

Use mathematical induction to prove that \(n! > 2^n\) for all integers \(n \geq 5\).

Exercise 5.7

Why does the proof in previous exercise use \(n \geq 5\)?

Exercise 5.8

Consider the statement “In any group of \(n \geq 1\) people, everyone has the same birthday.”

Find the error in the following proof. Explain why this proof does not work.

Let \(n=1\). In a group consisting of only one person, surely that person has the same birthday as themselves. Now, for the inductive step, suppose that in any group of \(k\) people, everyone has the same birthday.

Let \(G = \{a_1, a_2, \ldots, a_{k+1}\}\) be a group of \(k+1\) people. Since both \(\{a_1, a_2, \ldots, a_{k}\}\) and \(\{a_2, a_3, \ldots, a_{k+1}\}\) are groups of \(k\) people, then by the inductive hypothesis every person in each group has the same birthday.

Since \(a_2\) is in both groups, then everyone in \(G\) must also have the same birthday as \(a_2\) and each other. Hence, by mathematical induction, in every group of \(n \geq 1\) people, everyone has the same birthday. \(\blacksquare\).

Exercise 5.9

From Lemma 4.3.3, we know that if \(m\) and \(n\) are co-prime where \(m \mid x\) and \(n \mid x\) for some integer \(x\), then \(mn \mid x\).

Now, let \(m_1, m_2, \ldots, m_n\) be pairwise co-prime integers for \(n \geq 2\). Let \(x\) be some integer. Show using mathematical induction that if \(m_i \mid x\) for all \(1 \leq i \leq n\), then \(m_1\cdot m_2 \cdots m_n \mid x\).