4 Proof by induction
We have seen several type of proofs so far:
direct proof (sometimes known as deductive proof);
proof by case analysis;
proof by contradiction;
proof using the contrapositive.
In this chapter, we introduce a new type of proof, called proof by induction.
Let \(n_0 \in \mathbb{Z}_+\) and let \(P(n)\) be a statement for \(n\geq n_0\). A proof by induction is where one prove that:
\(P(n_0)\) is true, and
\(P(n) \implies P(n+1)\) for all \(n\geq n_0\).
□
The word induction comes from the Latin in and ductus meaning “to lead”. An inductive proof is one where a starting case leads into the next case and so on.
(In contrast, deduction has the prefix de meaning “down from”. When we do a proof by deduction, we start from certain rules and truths that “lead down” to specific things that must follow as a consequence.)Statement: Show that, for every \(n\in\mathbb{Z}_+\), we have \[1+2+3+\cdots+n=\sum_{i=1}^n=\frac{n(n+1)}{2}.\]
Proof: For \(n\in\mathbb{Z}_+\), let \(P(n)\) be the following statement. \[1+2+3+\cdots+n=\frac{n(n+1)}{2}.\] We will show that \(P(n)\) is a true statement, for all \(n\in\mathbb{Z}_+\) by giving a proof by induction.
First, let us consider \(P(1)\). We have \(1=\frac{1(1+1)}{2}\), hence, \(P(1)\) holds.
Now, suppose that \(P(k)\) is true for some positive integer \(k\), that is
\[1+2+3+\cdots+k=\frac{k(k+1)}{2}.\]
Then
\[\begin{align*}
1+2+3+\cdots+k+(k+1)&=\frac{k(k+1)}{2}+(k+1)\\
&=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}\\
&=\frac{k^2+3k+2}{2}\\
&=\frac{(k+1)(k+2)}{2}.
\end{align*}\]
This shows that if \(P(k)\) is true then \(P(k+1)\) is true. By the Principle of Mathematical Induction, it follows that \(P(n)\) is true for all natural numbers \(n\).
It is not enough to show \(P(n)\implies P(n+1)\), we need to also show \(P(n_0)\) holds. As we saw in the above example, we often have that \(n_0=1\). However, this is not always the case. The following example highlights these two points.
Let \(P(n)\) be the statement \(n^2\leq 2^{n-1}\). To highlight the importance of the base case, let us first show that for \(n\geq 3\) we have \(P(n) \implies P(n+1)\).
Suppose that \(P(k)\) is a true statement for some natural number \(k\geq 3\), that is \(k^2\leq 2^{k-1}\).
ThenIf we set \(n_0=1\), we do have \(P(1)\) holds (since \(1\leq 1\)), but have not proven \(P(1) \implies P(2)\) (since \(1\not\geq 3\)). In fact, we can not prove \(P(1) \implies P(2)\) since \(P(2)\) is false (\(2^2\not\leq 2^1\)).
Since we have shown that for \(n\geq 3\) we have \(P(n) \implies P(n+1)\), we might want to set \(n_0=3\). However, \(P(3)\) is also false since \(3^2\not\leq 2^2\). In fact, we can check that \(P(3), P(4), P(5)\) and \(P(6)\) are all false. However, \(P(7)\) is true since we have that \(7^2=49\leq 64 = 2^6\).
Therefore, we have \(n_0=7\) and by the Principle of mathematical induction, we have shown that \(n^2\leq 2^{n-1}\) for all \(n\in\mathbb{Z}_+\) such that \(n\geq 7\).Sometimes, the principle of induction is not strong enough, either because we need more than one base case, or because to prove \(P(n)\) is true we need to know \(P(m)\) is true for some unknown \(m<n\). This is where we can use the strong principle of mathematical induction.
Let \(n_0 \in \mathbb{Z}_+\) and let \(P(n)\) be a statement for \(n\geq n_0\). A proof by strong induction is where one prove that:
\(P(n_0), P(n_0+1),\dots P(n_0+k)\) is true (for some \(k\geq 0\)), and
for all \(n\geq n_0+k\), show that \(P(i)\) is true for all \(i\leq n \implies P(n+1)\) is true.
□
Statement: Suppose that \(x_1 = 3\) and \(x_2 = 5\) and for \(n \geq 3\), define \(x_n = 3x_{n-1} -2x_{n-2}\). Show that \(x_n = 2^n + 1\), for all \(n\in\mathbb{Z}_+\).
Proof: Let \(P(n)\) be the statement “\(x_n= 2^n+1\)”. We will show that \(P(n)\) is a true statement, for all \(n\in\mathbb{Z}_+\), by giving a proof by induction. First, we consider our base cases \(n_0=1\) and \(n_{0+1}=2\). We have the given initial conditions \(x_1=3\) and \(x_2=5\). Using the formula \(x_n=2^n+1\), we indeed have \(x_1= 2^{1}+1=3\) and \(x_2= 2^2+1= 5\).Therefore, \(P(1)\) and \(P(2)\) hold.
Let \(n\in\mathbb{Z}_+\) and suppose for all \(i\in \mathbb{Z}_+\) such that \(i \leq n\) we have \(P(n)\) holds. Then by our assumption \(x_{n-1}= 2^{n-1}+1\) and \(x_n = 2^n +1\). We have: This shows that if \(P(i)\) is true, for \(1\leq i\leq n\), then \(P(n+1)\) is true. By the Strong Principle of Mathematical Induction, it follows that \(P(n)\) is true for all natural numbers \(n\). \(\square\)Statement: Show that every natural number can be written as the sum of distinct powers of \(2\). That is for all \(n\in\mathbb{Z}_+\), we can write \(n=2^{a_1}+2^{a_2}+\dots+2^{a_r}\) with \(a_i \in \mathbb{Z}\), \(a_i\geq 0\), and \(a_i\neq a_j\) if \(i\neq j\).
Proof: Let \(P(n)\) be the statements “there exists \(a_1,\dots a_r \in \mathbb{Z}\) such that \(a_i\geq0\), \(a_i\neq a_j\) if \(i\neq j\) and \(n=2^{a_1}+2^{a_2}+\dots+2^{a_r}\)”. We check that our base case \(n_0=1\) is true. Indeed \(1=2^0\) so \(P(1)\) holds.
Let \(n\in\mathbb{Z}_+\) and suppose for all \(i\in \mathbb{Z}_+\) such that \(i \leq n\) we have \(P(n)\) holds. Consider \(A = \{n+1-2^\ell: \ell\in\mathbb{Z}_{>0} \wedge n+1-2^\ell\geq 0\}\). We note that \(A \subseteq \mathbb{Z}_{\geq 0}\) by definition. Taking \(\ell = 1\), we see that \(n-1\in A\), so \(A \neq \emptyset\). So, by the Well Ordering Principle, \(A\) has a minimal element, call it \(m\). If \(m=0\) then \(n+1 = 2^\ell\) and \(P(n+1)\) holds. If \(m\neq 0\), then since \(P(m)\) holds, we have there exists \(a_1,\dots a_r \in \mathbb{Z}\) such that \(a_i\geq0\), \(a_i\neq a_j\) if \(i\neq j\) and \(m=2^{a_1}+2^{a_2}+\dots+2^{a_r}\). Then \(n+1 = 2^\ell+2^{a_1}+2^{a_2}+\dots+2^{a_r}\), so we just need to show \(\ell \neq a_i\) for all \(i\). For a contradiction, suppose \(\ell = a_i\) for some \(i\). Then \(n+1 \geq 2^\ell+2^\ell = 2^{\ell+1}\), so \(0\leq n+1-2^{\ell+1}<m\) which contradicts the definition of \(m\). Therefore the powers are distinct and \(P(n+1)\) holds.
Therefore, by the principle of strong induction, we have showed that every natural number can be written as the sum of distinct powers of \(2\).
A proof by induction is a special case of a proof by strong induction (taking \(k=0\))! We present these two ideas separately as it is easier to understand induction before understanding strong induction. However, most mathematician will say “induction” to mean both induction and strong induction and do not distinguish between the two (so feel free to also not distinguish between the two).