Many mathematical theorems are of the form \(\forall n\in \mathbb{N}, P(n)\). Very often, such theorems can be proved using a technique called mathematical induction. It is based on the Axiom of Induction:
If \(P(0)\) holds and \(P(k) \Rightarrow P(k+1)\) for all \(k \in \mathbb{N}\), then \(\forall n \in \mathbb{N}, P(n)\).
Here, \(P(k) \Rightarrow P(k+1)\) means that if \(P(k)\) holds, then \(P(k+1)\) must also hold. (We will see a formal definition of the logical connective “\(\Rightarrow\)” later when we study propositional logic. For our purposes here, the stated interpretation is sufficient.)
Note that the Axiom of Induction is something that we simply accept without proof. To see why it is reasonable to accept it as true, suppose that \(P(n)\) satisfies the assumption of the axiom; namely, that \(P(0)\) holds and \(P(k) \Rightarrow P(k+1)\) for all \(k \in \mathbb{N}\). Since \(P(k) \Rightarrow P(k+1)\) for all \(k \in \mathbb{N}\), that means \(P(0) \Rightarrow P(1)\) holds in particular. But we know that \(P(0)\) holds. Hence, \(P(1)\) holds as well. Now, \(P(1) \Rightarrow P(2)\) also holds. Since \(P(1)\) holds, \(P(2)\) holds as well. As you can see, we can continue in a similar fashion to show that \(P(n)\) holds for any given \(n\in\mathbb{N}\).
Proving a mathematical statement by (the principle of) mathematical induction means doing two things:
Prove that \(P(0)\) holds. (This is called the base case or basis.)
Prove that for any \(k \in \mathbb{N}\), if \(P(k)\) holds, then \(P(k+1)\) also holds. (This is called the inductive step and \(P(k)\) is called the induction hypothesis.)
Prove that \(\displaystyle\sum_{i=0}^n (2i+1) = (n+1)^2\) for all \(n \in \mathbb{N}\).
Proof. Let \(P(n)\) denote the predicate “\(\displaystyle\sum_{i=0}^n (2i+1) = (n+1)^2\)” where \(n \in \mathbb{N}\).
Basis. When \(n = 0\), \(\displaystyle\sum_{i=0}^n (2i+1) = (2\cdot0+1) = 1\) which is the same as \((0+1)^2\). Thus, \(P(0)\) holds.
Inductive step. Assume that \(P(k)\) holds where \(k \in \mathbb{N}\). We show that \(P(k+1)\) also holds; that is, \(\displaystyle\sum_{i=0}^{k+1} (2i+1) = ((k+1)+1)^2\).
Now, \(\displaystyle\sum_{i=0}^{k+1} (2i+1) = \sum_{i=0}^k (2i+1) + (2(k+1)+1)\). By the induction hypothesis, \(\displaystyle\sum_{i=0}^k (2i+1) = (k+1)^2\). Hence, \[\begin{align} \sum_{i=0}^{k+1} (2i+1) &= (k+1)^2+(2(k+1)+1) \\ &= k^2+2k +1+ 2k + 3 \\ &= k^2 + 4k + 4 \\ &= (k+2)^2 = ((k+1)+1)^2. \end{align}\] This establishes \(P(k+1)\).
By the principle of mathematical induction, we have \(\forall n \in \mathbb{N}, P(n)\); that is, \(\displaystyle\sum_{i=0}^n (2i+1) = (n+1)^2\) for all \(n \in \mathbb{N}\).
Prove that \(133 \mid (11^{n+2} + 12^{2n+1})\) for all \(n \in \mathbb{N}\).
Proof. Let \(P(n)\) denote the predicate “\(133 \mid (11^{n+2} + 12^{2n+1})\)” where \(n \in \mathbb{N}\).
Basis. When \(n = 0\), \(11^{n+2} + 12^{2n+1} = 11^2 + 12 = 121 + 12 = 133\) which is an integer multiple of \(133\). Thus, \(P(0)\) holds.
Inductive step. Assume that \(P(k)\) holds where \(k \in \mathbb{N}\). We show that \(P(k+1)\) also holds; that is, \(133 \mid (11^{(k+1)+2} + 12^{2(k+1)+1})\).
Now, \[\begin{align} 11^{(k+1)+2} + 12^{2(k+1)+1} &= 11\cdot 11^{k+2} + 144\cdot 12^{2k+1} \\ & = 11\cdot 11^{k+2}+ (11+133) \cdot 12^{2k+1} \\ & = 11(11^{k+2}+ 12^{2k+1}) + 133\cdot 12^{2k+1}.\end{align}\] By the induction hypothesis, \(133 \mid (11^{k+2}+ 12^{2k+1})\). Hence, \(11\cdot 11^{k+2} + 144\cdot 12^{2k+1} = 133 m\) for some integer \(m\). Thus, \[11^{(k+1)+2} + 12^{2(k+1)+1} = 11\cdot 133 m + 133\cdot 12^{2k+1} = 133 (11m + 12^{2k+1}).\] As \(11m + 12^{2k+1}\) is an integer, we have \(133 \mid (11^{(k+1)+2} + 12^{2(k+1)+1})\). Hence, \(P(k+1)\) holds.
By the principle of mathematical induction, we have \(\forall n \in \mathbb{N},P(n)\); that is, \(133 \mid (11^{n+2} + 12^{2n+1})\) for all \(n \in \mathbb{N}\).
The proofs in the examples all follow the same structure. You are advised to use the following template when you write proofs by mathematical induction.
Let \(P(n)\) denote the predicate \(\ldots\).
Basis. When \(n = 0\), \(\ldots\).
Inductive step. Assume that \(P(k)\) holds where \(k\in \mathbb{N}\). We show that \(P(k+1)\) also holds; that is, \(\ldots\).
By the principle of mathematical induction, we have \(\forall n\in\mathbb{N}, P(n)\); that is, \(\ldots\).
As you gain experiencing writing mathematical proofs, you might choose to deviate from the wording given in the above template though the necessary ingredients must still be present. For now, please adopt this template so that you do not miss any important detail by mistake.
Sometimes, we might be asked to prove that \(P(n)\) is true for all \(n \geq n_0\) for some integer \(n_0\) other than 0. What we can do is to prove instead \(Q(n) = P(n+n_0)\) for all \(n \in \mathbb{N}\).
For example, say we need to prove that \(2^{m-1} \leq m!\) for all integers \(m \geq 2\).
The statement is equivalent to \(2^{n+1} \leq (n+2)!\) for all \(n \in \mathbb{N}\). We can now prove this equivalent statement using the above template.
Let \(P(n)\) denote the predicate “\(2^{n+1} \leq (n+2)!\)” where \(n \in \mathbb{N}\).
Basis. When \(n = 0\), \(2^{n+1} = 2\) which is equal to \((0+2)!\) since \((0+2)! = 2! = 2\). This establishes \(P(0)\).
Inductive step. Assume that \(P(k)\) holds where \(k \in \mathbb{N}\). We show that \(P(k+1)\) also holds; that is, \(2^{(k+1)+1} \leq ((k+1)+2)!\).
Note that \(2^{(k+1)+1} = 2\cdot 2^{k+1}\). By the induction hypothesis, \(2^{k+1} \leq (k+2)!\). Thus, \(2\cdot 2^{k+1} \leq 2\cdot (k+2)! \leq (k+3)(k+2)!\) since \(k + 3 > 2\) for all \(k \in \mathbb{N}\). Hence, \(2^{(k+1)+1} \leq ((k+1)+2)!\), establishing \(P(k+1)\).
By the principle of mathematical induction, we have \(\forall n \in \mathbb{N},P(n)\); that is, \(2^{n+1} \leq (n+2)!\) for all \(n \in \mathbb{N}\).
It is a bit inconvenient to prove an equivalent statement just to fit the template when the base case is not at 0. Thus, we use a more general template that allows the base case to be any integer other than 0.
Let \(n_0\) be an integer. Say we want to prove that \(P(n)\) holds for all \(n \geq n_0\). The following template can be used:
Let \(P(n)\) denote the predicate…
We prove that \(P(n)\) holds for all \(n \geq n_0\) by mathematical induction.
Basis. When \(n = n_0\), \(\ldots\).
Inductive step. Assume that \(P(k)\) holds for some \(k \geq n_0\). We show that \(P(k+1)\) also holds; that is, \(\ldots\).
By the principle of mathematical induction, we have \(P(n)\) for all \(n \geq n_0\).
Prove that \((x+y)^n = \displaystyle\sum_{i=0}^n \binom{n}{i} x^{n-i} y^i\) for all \(n \in \mathbb{N}\) and arbitrary real numbers \(x\) and \(y\).
Proof.
Basis. When \(n = 0\), \((x+y)^n = (x+y)^0 = 1\) and \(\displaystyle\sum_{i=0}^n \binom{n}{i} x^{n-i} y^i = \binom{0}{0} x^0 y^0 = 1\). Since both values are equal, the basis holds.
Inductive step. Assume that \((x+y)^k = \displaystyle\sum_{i=0}^k \binom{k}{i} x^{k-i} y^i\) where \(k\) is a natural number. We prove that \((x+y)^{k+1} = \displaystyle\sum_{i=0}^{k+1} \binom{k+1}{i} x^{k+1-i} y^i\).
Now, \((x+y)^{k+1} = (x+y) (x+y)^k = (x+y)\displaystyle\sum_{i=0}^k \binom{k}{i} x^{k-i} y^i\) by the induction hypothesis.
Expanding \((x+y)\displaystyle\sum_{i=0}^k \binom{k}{i} x^{k-i} y^i\) gives
\[\begin{align} \sum_{i=0}^k \binom{k}{i} x^{k+1-i} y^i + \sum_{i=0}^k \binom{k}{i} x^{k-i} y^{i+1} & = x^{k+1} + \sum_{i=1}^k \binom{k}{i} x^{k+1-i} y^i + \sum_{i=0}^{k-1} \binom{k}{i} x^{k-i} y^{i+1} + y^{k+1} \\ & = x^{k+1} + \sum_{i=1}^k \binom{k}{i} x^{k+1-i} y^{i} + \sum_{i=1}^k \binom{k}{i-1} x^{k-i+1} y^{i} + y^{k+1} \\ & = x^{k+1} + \sum_{i=1}^k \left(\binom{k}{i}+\binom{k}{i-1}\right) x^{k+1-i} y^{i} + y^{k+1} \\ & = \binom{k+1}{0} x^{k+1} y^0 + \sum_{i=1}^k \binom{k+1}{i} x^{k+1-i} y^{i} + \binom{k+1}{k+1} x^{(k+1)-(k+1)} y^{k+1} \\ & = \sum_{i=0}^{k+1} \binom{k+1}{i} x^{k+1-i} y^{i} \end{align}\]as desired. Thus, by the principle of mathematical induction, \((x+y)^n = \displaystyle\sum_{i=0}^n \binom{n}{i} x^{n-i} y^i\) for all \(n \in \mathbb{N}\) where \(x\) and \(y\) are arbitrary real numbers.
Prove that \(2 \mid (n^2 - n)\) for all \(n \in \mathbb{N}\).
Prove that \(64 \mid (9^n - 8n - 1)\) for all \(n \in \mathbb{N}\).
Prove that \(3^n > n^2\) for all \(n \in \mathbb{N}\).
Prove that \(\frac{2n+1}{3n-1} < \frac{2}{3} + \frac{1}{n}\) for all positive integers \(n\).