Strong induction is often found in proofs of results for objects that are defined inductively.
An inductive definition (or recursive definition) defines the elements in a sequence in terms of earlier elements in the sequence. It usually involves specifying one or more base cases and one or more rules for obtaining “later” cases.
For example, the following definition defines \(f_n\) for all \(n \in\mathbb{N}\).
\[\begin{align} f_n & = 1 && \text {if } n = 0, \\ f_{n} & = n f_{n-1} && \text{if } n > 0, \\ \end{align}\]We prove by induction that \(f_n = n!\).
Let \(P(n)\) denote the predicate “\(f_n = n!\). We prove by induction that \(P(n)\) holds for all \(n\in \mathbb{N}\).
Basis. When \(n = 0\), \(f_n = 1\) by definition. Since \(1 = 0!\), \(P(0)\) holds.
Inductive step. Assume that \(P(k)\) holds for some natural number \(k\); that is, \(f_k = k!\).
Since \(k + 1 > 0\), by definition, \(f_{k+1} = (k+1)f_k\). Now, by the induction hypothesis, \(f_k = k!\). Thus, \(f_{k+1} = (k+1) k! = (k+1) \displaystyle\prod_{i=0}^k i = \prod_{i=0}^{k+1} i = (k+1)!\). Hence, \(P(k+1)\) holds. By the principle of mathematical induction, \(f_n = n!\) for all \(n \in \mathbb{N}\).
Our “definitions” for the summation and product notations using \(\sum\) and \(\prod\) were a bit too casual. We now give an inductive definition for each.
Let \(a\) and \(b\) be integers such that \(k \leq 0\). Let \(f(i)\) be an expression defined for every integer \(i\) such that \(a \leq i \leq a+k\). Then \(\displaystyle\sum_{i=a}^{a+k} f(i)\) is defined as follows: \[\begin{align} & \sum_{i=a}^{a+k} f(i) = f(a) && \text{ if } k = 0, \\ & \sum_{i=a}^{a+k} f(i) = \left(\sum_{i=a}^{a+k-1} f(i)\right) + f(a+k) && \text{ if } k > 0. \end{align}\]
Similarly, \(\displaystyle\prod_{i=a}^{a+k} f(i)\) is defined as follows: \[\begin{align} & \prod_{i=a}^{a+k} f(i) = f(a) && \text{ if } k = 0, \\ & \prod_{i=a}^{a+k} f(i) = \left(\prod_{i=a}^{a+k-1} f(i)\right) f(a+k) && \text{ if } k > 0. \end{align}\]
Expand \(\displaystyle\sum_{i=2}^4 i^2\).
Using the inductive definition of summation, we have \[\begin{align} \sum_{i=2}^4 i^2 & = \left(\sum_{i=2}^3 i^2\right) + 4^2 \\ & = \left(\sum_{i=2}^3 i^2\right) + 4^2 \\ & = \left(\left(\sum_{i=2}^2 i^2\right) + 3^2\right) + 4^2 \\ & = \left(\left(2^2\right) + 3^2\right) + 4^2 \\ \end{align}\]
Let \(n\) be a positive integer. Then \(\displaystyle\sum_{i=1}^n 1 = n\).
Proof.
Let \(P(n)\) denote the predicate “\(\displaystyle\sum_{i=1}^n 1 = n\)”. We prove by induction that \(P(n)\) holds for all positive integers \(n\).
Basis. When \(n = 1\), \(\displaystyle\sum_{i=1}^n 1 = 1\). Hence, \(P(1)\) holds.
Inductive step. Assume that \(P(k)\) holds for some positive integer \(k\); that is, \(\displaystyle\sum_{i=1}^k 1 = k\).
By definition of the summation notation, \(\displaystyle\sum_{i=1}^{k+1} 1 = \left(\sum_{i=1}^k 1\right)+ 1.\) By the induction hypothesis \(\displaystyle\sum_{i=1}^k 1 = k.\) Hence, \(\displaystyle\sum_{i=1}^{k+1} 1 = k+1\). Hence, \(P(k+1)\) holds.
By the principle of mathematical induction, \(P(n)\) holds for all positive integers \(n\).
The sequence of Fibonacci numbers \(F_0, F_1, F_1,\ldots\) is defined inductively by \[\begin{align} F_0 & = 0 \\ F_1 & = 1 \\ F_n & = F_{n-1} + F_{n-2} \text{ if } n \geq 2 \end{align}\]
For example, \(F_4 = F_3 + F_2 = (F_2 + F_1) + (F_1 + F_0) = ( (F_1+F_0) + F_1) + (F_1 + F_0) = ( (1+0) + 1) + (1 + 0) = 3\).
There is a form of mathematical induction called strong induction (also called complete induction or course-of-values induction) in which the inductive step requires showing that \(P(k+1)\) assuming that \(P(0),\ldots, P(k)\) hold.
In practice, we only need the results for a handful of previous values.
For every natural number \(n \geq 2\), \(n\) is a product of primes.
Proof. Let \(P(n)\) denote the predicate “\(n\) is a product of primes”. We prove that \(P(n)\) holds for all natural numbers \(n \geq 2\).
Basis. When \(n = 2\), \(P(n)\) holds since \(2\) is a prime.
Inductive step. Assume that \(P(j)\) holds for all \(j = 2,\ldots,k\) where \(k \geq 2\) is a natural number.
Consider the number \(k+1\). If it is a prime, then \(P(k+1)\) holds trivially. Otherwise, \(k+1 = q r\) where \(q\) and \(r\) are natural numbers greater than 1. Note that \(p\) and \(q\) are both less than \(k\). Thus, \(P(q)\) and \(P(r)\) hold by the induction hypothesis, giving that \(q\) and \(r\) can be expressed as products of primes. Hence, \(k+1\) is also a product of primes, implying that \(P(k+1)\) holds. By the principle of strong induction, \(P(n)\) holds for all natural numbers \(n \geq 2\).
For each \(n \in \mathbb{N}\), the Fibonacci number \(F_n\) equals \(\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left( \frac{1-\sqrt{5}}{2}\right)^n\right)\).
Proof.
Let \(P(n)\) denote the predicate “\(F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left( \frac{1-\sqrt{5}}{2}\right)^n\right)\).” We prove by strong induction that \(P(n)\) holds for all \(n\in \mathbb{N}\).
We consider two base cases.
When \(n = 0\), \(\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left( \frac{1-\sqrt{5}}{2}\right)^n\right) = \frac{1}{\sqrt{5}}(1-1) = 0 = F_0 = F_n\). Hence, \(P(0)\) holds
When \(n = 1\), \(\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left( \frac{1-\sqrt{5}}{2}\right)^n\right) =\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right) - \left( \frac{1-\sqrt{5}}{2}\right)\right) = \frac{1}{\sqrt{5}}(\sqrt{5}) = 1 = F_1 = F_n\). Hence, \(P(1)\) holds.
Inductive step.
Let \(k \geq 1\). Assume that \(P(0),\ldots, P(k)\) hold. We prove that \(P(k+1)\) holds.
Then, \[\begin{align} F_{k+1} & = F_{k} + F_{k-1} \\ & = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{k} - \left( \frac{1-\sqrt{5}}{2}\right)^{k}\right) + \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{k-1} - \left( \frac{1-\sqrt{5}}{2}\right)^{k-1}\right) & (\text{by } P(k) \text{ and } P(k-1))\\ & = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{k} - \left( \frac{1-\sqrt{5}}{2}\right)^{k} + \left(\frac{1+\sqrt{5}}{2}\right)^{k-1} - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\right) \\ & = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{k-1} \left( \frac{1+\sqrt{5}}{2} + 1\right) - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1} \left(\frac{1-\sqrt{5}}{2} + 1\right)\right) \\ & = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{k-1} \left( \frac{3+\sqrt{5}}{2}\right) - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1} \left(\frac{3-\sqrt{5}}{2}\right)\right) \\ & = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{k-1} \left( \frac{6+2\sqrt{5}}{4}\right) - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1} \left(\frac{6-2\sqrt{5}}{4}\right)\right) \\ & = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{k-1} \left( \frac{1+2\sqrt{5}+(\sqrt{5})^2}{2^2}\right) - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1} \left(\frac{1-2\sqrt{5}+(\sqrt{5})^2}{2^2}\right)\right) \\ & = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{k-1} \left( \frac{1+\sqrt{5}}{2}\right)^2 - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1} \left(\frac{1-\sqrt{5}}{2}\right)^2\right) \\ & = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{k+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{k+1}\right). \end{align}\] Hence, \(P(k+1)\) holds.
By the principle of strong induction, \(F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left( \frac{1-\sqrt{5}}{2}\right)^n\right)\) for all \(n \in \mathbb{N}\).
Prove that for every positive integer \(n\), \(\displaystyle \sum_{i=1}^n \frac{1}{2^i} = 1 - \frac{1}{2^n}\).
Prove that \(\displaystyle\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\) for all \(n \in \mathbb{N}\).
Let \(n\) be a positive integer. Let \(f(i)\) and \(g(i)\) be expressions defined for all integers \(i\) such that \(1 \leq i \leq n\). Prove that \(\displaystyle \prod_{i=1}^n \left(f(i)g(i))\right) = \left(\prod_{i=1}^n f(i) \right)\left( \prod_{i=1}^n g(i)\right)\).
Let \(n\) be a natural number. Let \(f(i)\) be an expression defined for all integers \(i\) such that \(0 \leq i \leq n\).
Let \(k\) be an integer. Prove that \(\displaystyle \sum_{i=0}^n f(i) = \sum_{i = k}^{n+k} f(i-k)\).
Prove that \(\displaystyle \sum_{i=0}^n f(i) = \sum_{i = 0}^n f(n-i)\).
Consider the sequence of numbers \(a_0, a_1, a_2,\ldots\) defined by \[\begin{align*} a_0 & = -1, \\ a_1 & = 1, \\ a_n & = 3a_{n-1} - 2a_{n-2} ~\text{if } n \geq 2. \end{align*}\] Prove that \(a_n = 2^{n+1} - 3\) for all \(n \in \mathbb{N}\).