# 8.3: Other Versions of Induction

$$\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}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

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}^{+}$$.

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}^{+}$$.

## 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

1. your base case would be to prove $$P(0)$$, and
2. 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}^{+}$$.

This page titled 8.3: Other Versions of Induction is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.