8.3: Other Versions of Induction

Last updated
Save as PDF

Page ID: 23929

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

It is sometimes difficult to apply the Principle of Mathematical Induction in the form we have stated in Axiom \(8.1.2\). The following proposition provides some alternative versions that are more useful in some of those situations. All of them follow quite easily from the approach using “well-ordering” that will be discussed in the following section.

Proposition \(8.3.1\).

Suppose \(P(n)\) is a predicate of natural numbers, and \(m \in \mathbb{N}^{+}\).

(Strong induction) If
1. \(P(1)\) is true, and
2. for every \(n \geq 2\), \[((\text { for every } k \in\{1,2, \ldots, n-1\}, P(k)) \Rightarrow P(n)) .\]
  then \(P(n)\) is true for all \(n \in \mathbb{N}^{+}\).
(Generalized induction) If
1. \(P(m)\) is true, and
2. for every \(n > m\), \((P(n-1) \Rightarrow P(n))\),
  then \(P(n)\) is true for all \(n \geq m\).
(Strong induction with multiple base cases) If
1. \(P(k)\) is true for all \(k \in\{1,2, \ldots, m\}\), and
2. for every \(n > m\), \[((\text { for every } k \in\{1,2, \ldots, n-1\}, P(k)) \Rightarrow P(n)),\]
  then \(P(n)\) is true for all \(n \in \mathbb{N}^{+}\).
If
1. \(P(1)\) is true, and
2. for every \(k \in \mathbb{N}^{+}\), \(P(k) \Rightarrow P(k+1)\),
  then \(P(n)\) is true for all \(n \in \mathbb{N}^{+}\).
Suppose \(S \subset \mathbb{N}^{+}\). If
1. \(1 \in S\), and
2. for every \(n \in S\), \((n+1 \in S)\),
  then \(S = \mathbb{N}^{+}\).

Read after finishing Example \(8.3.3.\)

Proof

BY INDUCTION.

Define \(P(n)\) to be the assertion \[F_{n}<2^{n}.\]

We use strong induction with 2 base cases.

Base cases. We have \[F_{1}=1<2=2^{1}\]
and \[F_{2}=1<4=2^{2},\]
so \(P(1)\) and \(P(2)\) are true.
Induction step. Assume \(n \geq 3\), and that \(P(n − 1)\) and \(P(n − 2)\) are true. We have \[\begin{aligned}
F_{n} &=F_{n-1}+F_{n-2} \\
&<2^{n-1}+2^{n-2} \\
&<2^{n-1}+2^{n-1} \\
&=2^{n}
\end{aligned}\]
(Induction Hypotheses)
so \(P(n)\) is true.

By the Principle of Mathematical Induction (in the form of strong induction with multiple base cases), we conclude that \(P(n)\) is true for all \(n \in \mathbb{N}^{+}\).

Remark \(8.3.2\).

There are many other versions of induction. For example, if you wish to prove that \(P(n)\) is true for all \(n \in \mathbb{N}\) (rather than only for all \(n \in \mathbb{N}^{+}\)), then

your base case would be to prove \(P(0)\), and
your induction step would be to prove \(P(n-1) \Rightarrow P(n)\), for all \(n \geq 1\).

Example \(8.3.3\).

Prove \(F_{n} < 2^{n}\), for every \(n \in \mathbb{N}^{+}\).