Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 3.2.1 Principle of strong induction

Strong induction is another form of mathematical induction that can often be used when we cannot easily use mathematical induction. For strong induction , replace the inductive step in the Principle of Mathematical Induction by a stronger assumption. In its most basic form, there are two parts:
  1. Prove \(P(1)\) is true.
    🔗
    🔗
  2. Prove that for all positive integers \(k\text{,}\) if \(P(j)\) is true for all \(1\leq j\leq k\text{,}\) then \(P(k + 1)\) is true.
    🔗
    🔗
🔗
Then symbolically, mathematical induction says
\begin{equation*} (P(1)\land \forall k((P(1)\land P(2)\land \dots\land P(k)) \implies P(k + 1))) \implies \forall n P(n). \end{equation*}
🔗
For the inductive step, we need to show “\(P(n_0)\land P(n_0 + 1)\land \cdots\land P(k)\) implies \(P(k + 1)\text{.}\)” For fixed (generic) \(k \geq n_0\text{,}\) assume \(P(j)\) is true for all \(n_0\leq j\leq k\text{.}\) Prove \(P(k + 1)\) is true.
🔗

Example 3.2.1.2. Natural numbers are products of primes.

Prove that every positive integer greater than \(1\) can be written as a product of primes.

Proof.

Let \(P(n)\) be the proposition “\(n\) can be written as a product of primes.” We want to show \(P(n)\) is true for all \(n \geq 2\text{.}\) We proceed by induction on \(n\text{.}\)
🔗
Basis step: \(P(2)\) is true since \(2\) is prime.
🔗
Inductive step: Fix \(k \geq 2\text{.}\) Suppose \(P(j)\) is true for all \(0 \leq j\leq k\) so that \(j\) can be written as a product of primes when \(0\leq j\leq k\text{.}\) We want to show \(k + 1\) can be written as a product of primes. There are two cases to consider.
\(k + 1\) is prime
🔗
In this case, \(P(k + 1)\) is trivially true.
🔗
\(k + 1\) is composite
🔗
In this case, there exist integers \(a\) and
🔗
Therefore by strong induction, every integer greater than or equal to \(2\) can be written as a product of primes.
🔗
🔗
🔗
🔗
When we use the inductive hypothesis, it is important to verify that we are in the range where we can use it. See the example below.
🔗

Example 3.2.1.3. Find the flaw.

Find the flaw in the following proof that \(3^n = 1\) for every nonnegative integer \(n\text{.}\)
🔗
Let \(P(n)\) be the proposition \(3^n = 1\text{.}\)
🔗
Basis step: \(P(0)\) is true since \(3^0 = 1\text{.}\)
🔗
Inductive step: (Uses strong induction.) Fix \(k \geq 0\text{.}\) Assume \(P(j)\) is true for all \(0\leq j\leq k\text{.}\) In particular, we assume that \(3^j = 1\) for all \(0\leq j\leq k\text{.}\) We wish to show that \(3^{k + 1} = 1\text{.}\) We compute
\begin{equation*} 3^{k + 1} = 3^k \cdot 3^1 = \frac{3^k\cdot 3^k}{3^{k-1}} = \frac{1 \cdot 1}{1} = 1, \end{equation*}
since by the inductive hypothesis, \(3^k = 1\) and \(3^{k - 1} = 1\text{.}\) Thus, by induction, \(3^n = 1\) for all \(n \geq 0\text{.}\)
🔗
🔗

Example 3.2.1.4. Paying with \(3\) Ruble and \(5\) Ruble banknotes.

Every amount of \(8\) Rubles or more can be paid using \(3\) Ruble and \(5\) Ruble banknotes.
🔗
Front of a 3 Ruble banknote from the Soviet Union
Back of a 3 Ruble banknote from the Soviet Union
Back of a 5 Ruble banknote from the Soviet Union
Back of a 5 Ruble banknote from the Soviet Union
Solution.
Let \(R(n)\) be the proposition “an amount of \(n\) Rubles can be paid with \(3\) Ruble and \(5\) Ruble banknotes.”
🔗
We want to prove \(R(n)\) is true for \(n \geq 8\text{.}\) We proceed by induction on \(n\text{.}\)
🔗
Basis steps:
\begin{align*} 8 \amp = 1 \cdot 3 + 1 \cdot 5 \\ 9 \amp = 3 \cdot 3 + 0 \cdot 5 \\ 10 \amp = 0 \cdot 3 + 2 \cdot 5 \end{align*}
🔗
Inductive step: Fix \(k \geq 10\text{.}\) Suppose \(P(j)\) is true for all \(j\in\NN\) with \(8 \leq j\leq k\text{.}\) That is, \(j\) Rubles can be formed using \(3\) Ruble and \(5\) Ruble bank notes. We want to form \(k + 1\) Rubles.
🔗
Let \(j = (k + 1) - 3 = k - 2\text{.}\) Then \(j\leq k\text{.}\) Since \(k \geq 10\text{,}\) we have \(j = k - 2 \geq 10 - 2=8\text{.}\) By the inductive hypothesis, we can form \(j\) Rubles using \(3\) Ruble and \(5\) Ruble banknotes. Just add another \(3\) Ruble banknote to get \(j + 3 = k - 2 + 3 = k + 1\) Rubles. Thus \(R(k + 1)\) is true.
🔗
Therefore by strong induction, \(R(n)\) is true for all \(n \geq 8\text{.}\)
🔗
🔗
🔗

Example 3.2.1.5. Fibonacci sequence bound.

Recall the Fibonacci sequence is defined by \(f_0 = 0\text{,}\) \(f_1 = 1\text{,}\) and
\begin{equation*} f_{n + 1} = f_n + f_{n -1}, \quad \text{for }n \geq 1. \end{equation*}
Prove that \(f_n\leq 2^n\) for all \(n \geq 0\text{.}\)

Proof.

Let \(P(n)\) be the proposition “\(f_n\leq 2^n\text{.}\)” We proceed by induction on \(n\text{.}\)
🔗
Basis step: It is clear that \(f_0 = 0\leq 2^0\) and \(f_1 = 1\leq 2^1\text{,}\) so \(P(0)\) and \(P(1)\) are true.
🔗
Inductive step: Fix \(k \geq 1\text{.}\) Assume \(P(j)\) is true for \(0\leq j \leq k\) so that \(f_j\leq 2^j\) for \(0\leq j \leq k\text{.}\) We want to prove \(f_{k + 1}\leq 2^{k + 1}\text{.}\) We have
\begin{align*} f_{k + 1} \amp = f_k + f_{k - 1} \\ \amp \leq 2^k + 2^{k - 1} \\ \amp \leq 2 \cdot 2^k \\ \amp = 2^{k + 1}. \end{align*}
Thus \(P(k + 1)\) is true.
🔗
Therefore by strong induction, \(f_n\leq 2^n\) for all \(n \geq 0\text{.}\)
🔗
🔗
🔗
🔗
🔗
PrevTopNext