8.3: Other Versions of Induction

Proposition \(8.3.1\).

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

1. (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}^{+}\).
2. (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\).
3. (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}^{+}\).
4. 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}^{+}\).
5. 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.

1. 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.
2. 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}^{+}\).