Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 3.1.2 The principle of mathematical induction

In its most basic form, mathematical induction has two parts:
  1. Prove \(P(1)\) is true.
    🔗
    🔗
  2. Prove for all positive integers \(k\text{,}\) if \(P(k)\) is true, then
    🔗
    🔗
🔗
Then symbolically, mathematical induction says
\begin{equation*} (P(1)\land \forall k(P(k) \implies P(k + 1))) \implies \forall n P(n). \end{equation*}
A useful analogy to keep in mind is stacking dominos to topple. How can we prove that the \(n\) th domino topples for all \(n\text{?}\) First, we need to know that the first domino falls. A bit of thought shows that this is not enough. We need to additionally know that the dominos are stacked expertly. Namely, they are stacked in such a way that if the \(k\) th domino falls, then the \((k + 1)\) st domino falls.
🔗
Follow these steps to write a proof by induction.
Introduction
🔗
State that we are using induction. To be extra clear, tell the reader on what we are doing induction. A common way of saying this is “We proof the theorem by induction on \(n\)”.
🔗
Define \(P(n)\text{.}\)
🔗
Basis step
🔗
Prove \(P(n_0)\) is true.
🔗
Inductive step
🔗
For fixed (generic) \(k\ge n_0\text{,}\) assume \(P(k)\) is true. This is known as assuming the inductive hypothesis.
🔗
Prove \(P(k + 1)\) is true. In this step you apply that \(P(k)\) is true.
🔗
Conclusion
🔗
State that by the principle of mathematical induction you have proven that \(P(n)\) is true for all \(n\in\{n_0,n_0+1,n_0+2,\dots\}\text{.}\)
🔗
🔗
We proof Theorem the following theorem by induction.
🔗

Proof.

Introduction
🔗
We proof the theorem by induction on \(n\text{.}\)
🔗
Let \(P(n)\) be “\(\sum_{i=1}^n i=\frac{n\cdot(n+1)}{2}\)”.
🔗
Basis step
🔗
We prove that \(P(1)\) is true by evaluating both sides of the equation at \(n=1\) and concluding that they are equal.
🔗
For the left hand side of \(P(1)\) we have
\begin{equation*} \sum_{i=1}^1 i=1 \end{equation*}
and for the right hand side of \(P(1)\) we have
\begin{equation*} \frac{1\cdot(1+1)}{2}=\frac{2}{2}=1. \end{equation*}
Thus \(P(1)\) is true.
🔗
Inductive step
🔗
Suppose that for a fixed \(k\ge 1\) we have \(P(k)\) is true, that is “\(\sum_{i=1}^k i=\frac{k\cdot(k+1)}{2}\)” is true.
🔗
We now want to prove that \(P(k+1)\) is true, that is that “\(\sum_{i=1}^{k+1} i=\frac{(k+1)\cdot(k+2)}{2}\)” is true. With the induction hypothesis that \(P(k)\) is true we get
\begin{align*} \sum_{i=1}^{k+1} i \amp = \left(\sum_{i=1}^{k} i\right)+(k+1)\\ \amp=\frac{k\cdot (k+1)}{2}+(k+1) \\ \amp =\frac{k\cdot (k+1)}{2}+\frac{2k+2}{2}\\ \amp =\frac{k\cdot (k+1)+(2k+2)}{2} \\ \amp =\frac{k^2+3k+2}{2}\\ \amp=\frac{(k+1)\cdot(k+2)}{2} \end{align*}
Thus \(P(k+1)\) is true.
🔗
Conclusion
🔗
By the principle of mathematical induction we have proven that \(P(n)\) is true for all \(n\in\NN\text{.}\)
🔗
🔗
🔗
For the next example of a proof by induction we need the notion of divisibility by \(5\text{.}\)
🔗

Definition 3.1.2.3.

Let \(m\in\NN\cup\{0\}\) and \(d\in\NN\text{.}\) We say \(m\) is divisible by \(d\) when there exists \(s\in\NN\cup\{0\}\) such that \(m=d\cdot s\text{.}\)
🔗
🔗

Proof.

Introduction. We proof the theorem by induction on \(n\text{.}\)
🔗
Let \(P(n)\) be “\(n^5-n\) is divisible by \(5\)” with domain \(\NN\cup\{0\}\text{.}\)
🔗
Basis step. We prove that \(P(0)\) is true.
🔗
For \(n=0\) we have \(0^5-0=0\text{.}\) Because \(0=5\cdot 0\) and because \(0\in\NN\cup\{0\}\) we have that \(5\) divides \(0\text{,}\) which proves that \(P(0)\) is true.
🔗
Inductive step For fixed \(k\ge 0\text{,}\) assume \(P(k)\) is true, that is “\(k^5-k\) is divisible by \(5\)” is true.
🔗
We now want to show that \(P(k+1)\) is true, that is “\((k+1)^5-(k+1)\) is divisible by \(5\)” is true. We get
\begin{align*} (k\!+\!1)^5\!-(k\!+\!1) \amp = k^5\!+5\!\cdot\! k^4\!+10\!\cdot\! k^3\!+ 10\!\cdot\! k^2\! +5\!\cdot\!k+ 1 - k -1 \\ \amp =k^5+5\cdot(k^4+2\cdot k^3+2\cdot k^2+k)-k \\ \amp =k^5-k+5\cdot(k^4+2\cdot k^3+2\cdot k^2+k) \end{align*}
Because of the assumption that \(P(k)\) is true, there exists \(s\in\NN\cup\{0\}\) such that \(k^5-k=5\cdot s\text{.}\) With this we get
\begin{align*} (k+1)^5-(k+1) \amp =k^5-k+5\cdot(k^4+2\cdot k^3+2\cdot k^2+k) \\ \amp =5\cdot s+5\cdot(k^4+2\cdot k^3+2\cdot k^2+k) \\ \amp =5\cdot(s+k^4+2\cdot k^3+2\cdot k^2+k). \end{align*}
Thus \((k+1)^5-(k+1)\) is divisible by \(5\) which means that \(P(k+1)\) is true.
🔗
Conclusion. By the principle of mathematical induction we have proven that \(P(n)\) is true for all \(n\in\NN\cup\{0\}\text{.}\)
🔗
🔗

Definition 3.1.2.5.

Let the sequence \(\set{f_n}\) be given by the recurrence relation \(f_{n}=n\cdot f_{n-1}\) and the initial value \(f_0=1\text{.}\) We call \(f_n\) the factorial of \(n\) and denote it by \(n!\text{.}\)
🔗
🔗

Remark 3.1.2.6.

For \(n\in\NN\) we have \(\displaystyle n!=\prod_{i=1}^n i=1\cdot 2\cdot 3\cdot\dots\cdot (n-1)\cdot n\text{.}\)
🔗
🔗

Proof.

Introduction
🔗
We proof the theorem by induction on \(n\text{.}\)
🔗
Let \(P(n)\) be “\(\displaystyle\sum_{i=1}^n \left(i\cdot(i!)\right)=(n+1)!-1\text{.}\)”
🔗
Basis step
🔗
We prove that \(P(1)\) is true.
🔗
For the left hand side of \(P(n)\) with \(n=1\) we have
\begin{equation*} \displaystyle\sum_{i=1}^1 \left(i\cdot(i!)\right)=\left(1\cdot(1!)\right)=1\cdot 1=1 \end{equation*}
For the right hand side we have
\begin{equation*} (1+1)!-1=2!-1=2-1=1 \end{equation*}
As the left hand side and the right hand side are equal \(P(1)\) is true.
🔗
Inductive step
🔗
For fixed \(k\ge 0\text{,}\) assume \(P(k)\) is true, that is “\(\sum_{i=1}^k \left(i\cdot(i!)\right)=(k+1)!-1\)” is true.
🔗
We now want to show that \(P(k+1)\) is true, that is
\begin{equation*} \displaystyle\sum_{i=1}^{k+1} \left(i\cdot(i!)\right)=(k+2)!-1. \end{equation*}
We have
\begin{equation*} \sum_{i=1}^{k+1} \left(i\cdot(i!)\right) = \sum_{i=1}^{k} \left(i\cdot(i!)\right)+(k+1)\cdot(k+1)! \end{equation*}
With the assumption that \(P(k)\) is true we obtain
\begin{align*} \sum_{i=1}^{k+1} \left(i\cdot(i!)\right) \amp = \sum_{i=1}^{k} \left(i\cdot(i!)\right)+(k+1)\cdot(k+1)! \\ \amp =(k+1)!-1 +(k+1)\cdot(k+1)! \\ \amp = (1+k+1)\cdot(k+1)!-1 \\ \amp = (k+2)\cdot(k+1)!-1 \\ \amp = (k+2)!-1 \end{align*}
Thus if \(P(k)\) is true then \(P(k+1)\) is true.
🔗
Conclusion
🔗
By the principle of mathematical induction we have proven that \(P(n)\) is true for all \(n\in\NN\text{.}\)
🔗
🔗
🔗
Now that you have seen a couple of example, we only label the basis and the inductive steps.
🔗

Proof.

We proof the theorem by induction on \(n\text{.}\) Let \(P(n)\) be “\(\displaystyle\sum_{i=0}^n 2^i=2^{n+1}-1\)”.
🔗
Basis step. We prove that \(P(0)\) is true. For the left hand side of \(P(0)\) we have
\begin{equation*} \sum_{i=0}^0 2^i=2^0=1 \end{equation*}
and fro the right hand side of \(P(1)\) we have
\begin{equation*} 2^{0+1}-1=2^1-1=2-1=1. \end{equation*}
Thus \(P(0)\) is true.
🔗
Inductive step. We assume \(P(k)\) is true for a fixed \(k\ge 0\text{,}\) that is “\(\sum_{i=0}^k 2^i=2^{k+1}-1\)” is true. We now want to show that \(P(k+1)\) is true, that is we want to show that “\(\sum_{i=0}^{k+1} 2^i=2^{k+2}-1\)” is true. We have
\begin{align*} \sum_{i=0}^{k+1} 2^i \amp = \left(\sum_{i=0}^{k} 2^i\right)+2^{k+1} \\ \amp =\left(2^{k+1}-1\right)+2^{k+1} \text{ because we assume }P(k)\text{ is true} \\ \amp = 2\cdot 2^{k+1}-1 \\ \amp =2^{k+2}-1 \end{align*}
Thus \(P(k+1)\) is true.
🔗
By the principle of mathematical induction we have proven that \(P(n)\) is true for all \(n\in\NN\cup\{0\}\text{.}\)
🔗
🔗
Mathematical induction can be used to prove statements other than formulas.
🔗

Example 3.1.2.9. Tower of Hanoi.

The Tower of Hanoi is a puzzle game consisting of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
🔗
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
  1. Only one disk can be moved at a time.
    🔗
    🔗
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack that is , a disk can only be moved if it is the uppermost disk on a stack.
    🔗
    🔗
  3. No disk may be placed on top of a smaller disk.
    🔗
    🔗
See the Wikipedia article for more details (https://en.wikipedia.org/wiki/Tower_of_Hanoi)
🔗
Answer.
Let \(P(n)\) be the proposition “\(m_n = 2^n - 1\text{.}\)”
🔗
We proceed by induction on \(n\text{.}\)
🔗
Basis step. It is clear that \(m_1 = 1\text{.}\) Thus \(P(1)\) is true.
🔗
Inductive step. Fix \(k \geq 1\text{.}\) Assume \(P(k)\) is true so that \(m_k =2^k + 1\text{.}\) Then
\begin{align*} m_{k + 1} \amp = 2 m_k + 1 \\ \amp = 2(2^k -1) + 1 \text{ (by inductive hypothesis)} \\ \amp = 2^{k + 1} - 1. \end{align*}
Thus \(P(k + 1)\) is true.
🔗
Therefore, by mathematical induction, \(m_n = 2^n - 1\) for all \(n \geq 1\text{.}\)
🔗
🔗
Solution.
Let \(\hanoi(n)\) denote the Tower of Hanoi game with \(n\) disks. Once we have a winning strategy for \(\hanoi(k)\) for some positive integer \(k\text{,}\) we can get a winning strategy for \(\hanoi(k + 1)\) as follows.
  1. Use strategy to move the smallest \(k\) disks to an empty rod.
    🔗
    🔗
  2. Move largest disk to the remaining empty rod.
    🔗
    🔗
  3. Use strategy to move the smallest \(k\) disks on top of the
    🔗
    🔗
If there are \(m_k\) moves in the \(\hanoi(k)\) winning strategy, then there are \(m_k + 1 + m_k = 2m_k + 1\) moves in the \(\hanoi(k + 1)\) strategy described above. It is clear that \(m_1 = 1\text{.}\) Then its easy to see that \(m_2 = 3\text{,}\) \(m_3 = 7\text{,}\) \(m_4 = 15\text{,}\) and so on. It looks like \(m_k = 2^k - 1\text{.}\) Let’s prove it by induction.
🔗
🔗
🔗

Remark 3.1.2.10.

A proof almost identical to the one above can be used to prove that the winning strategy for \(\hanoi(n)\) with the minimum number of moves has \(2^n - 1\) moves.
🔗
🔗

Example 3.1.2.11. All people are the same age.

Find the flaw in the following proof that any set with \(n\) people are all the same age.
🔗
We proceed by induction. Let \(P(n)\) be the proposition “In any set of \(n\) people are all the same age.”
🔗
We proceed by induction on \(n\text{.}\)
🔗
Basis step. It is clear that in any set with 1 person, they are the same age. Thus \(P(1)\) is true.
🔗
Inductive step Fix \(k \geq 1\text{.}\) Assume \(P(k)\) is true so that any set of \(k\) people are the same age. Let \(S\) be a set of \(k + 1\) people. We have to show that everyone in \(S\) is the same age. Pick one person \(X\) in \(S\text{.}\) Let \(T = S - \set{X}\text{.}\) Then \(\size{T} = k\text{,}\) so by the inductive hypothesis everyone in \(T\) is the same age, call it \(a\text{.}\) Pick another person \(X'\) in \(S\text{,}\) \(X \neq X'\text{.}\) Let \(T' = S -\set{X'}\text{.}\) Then \(\size{T'} = k\text{,}\) so by the inductive hypothesis everyone in \(T'\) is the same age, call it \(a'\text{.}\)
🔗
Notice that we have \(a = a'\) since \(T\) and \(T'\) have some members in common. Furthermore, \(T \cup T' = S\text{.}\) Thus everyone in \(S\) is the same age.
🔗
Therefore by mathematical induction, any set of \(n\) people are all the same age.
🔗
Solution.
What is the error in the “proof”? When we choose \(X' \neq X\text{,}\) we are assuming \(k \geq 2\text{.}\) Furthermore, when we assert \(T\) and \(T'\) have members in common, we assume \(k \geq 3\text{.}\) This shows that we need to be really careful that the basis step is correctly chosen so that the inductive step can work.
🔗
🔗
🔗
Figure 3.1.2.12. Win By Induction? by Randall Munroe (https://xkcd.com/1516/). This would be bad enough, but every 30th or 40th pokéball has TWO of them inside.
🔗
🔗
PrevTopNext