$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.S: Mathematical Induction (Summary)

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Important Definitions

• Inductive set, page 171

• Factorial, page 201

• Recursive definition, page 200

• Fibonacci numbers, page 202

• Geometric sequence, page 206

• Geometric series, page 206

The Various Forms of Mathematical Induction

1. The Principle of Mathematical Induction
If $$T$$ is a subset of $$\mathbb{N}$$ such that

(a) $$1 \in T$$, and
(b) For every $$k \in \mathbb{N}$$, if $$k \in T$$, then $$(k + 1) \in T$$.

then $$T = \mathbb{N}$$
Procedure for a Proof by Mathematical Induction
To prove $$(\forall n \in \mathbb{N}$$(P(n))\)
$\begin{array} {rcl} {\text{Basis step}} &: & {\text{Prove} P(1).} \\ {\text{Inductive step}} &: & {\text{Prove that for each} k \in \mathbb{N}, \text{if} P(k) \text{is true, then} P(k + 1) \text{is true.}} \end{array}$

2. The Extended Principle of Mathematical Induction
Let $$M$$ be an integer. If $$T$$ is a subset of $$\mathbb{Z}$$ such that

(a) $$M \in T$$, and
(b) For every $$k \in \mathbb{Z}$$ with $$k \ge M$$, if $$k \in T$$, then $$(k + 1) \in T$$.

then $$T$$ contains all integers greater than or equal to $$M$$.
Using the Extended Principle of Mathematical Induction
Let $$M$$ be an intteger. To prove $$(\forall n \in \mathbb{Z} \text{with} n \ge M) (P(n))$$
$\begin{array} {rcl} {\text{Basis step}} &: & {\text{Prove} P(M).} \\ {\text{Inductive step}} &: & {\text{Prove that for each} k \in \mathbb{Z} \text{with} k \ge M, \text{if} P(k) \text{is true, then} P(k + 1) \text{is true.}} \end{array}$
We can then conclude that $$P(n)$$ is true for all $$n \in \mathbb{Z}$$ with $$n \ge M$$.

3. The Second Principle of Mathematical Induction
Let $$M$$ be an integer. If $$T$$ is a subset of $$\mathbb{Z}$$ such that

(a) $$M \in T$$, and
(b) For every $$k \in \mathbb{Z}$$ with $$k \ge M$$, if $$\{M, M + 1, ..., k\} \subseteq T$$, then $$(k + 1) \in T$$.

then $$T$$ contains all integers greater than or equal to $$M$$.
Using the Second Principle of Mathematical Induction
Let $$M$$ be an intteger. To prove $$(\forall n \in \mathbb{Z} \text{with} n \ge M) (P(n))$$
$\begin{array} {rcl} {\text{Basis step}} &: & {\text{Prove} P(M).} \\ {\text{Inductive step}} &: & {\text{Let} k \in \mathbb{Z} \text{with} k \ge M. \text{Prove that if} P(M), P(M + 1), ..., P(k) \text{are true, then} P(k + 1) \text{is true.}} \end{array}$
We can then conclude that $$P(n)$$ is true for all $$n \in \mathbb{Z}$$ with $$n \ge M$$.

Important Results

• Theorem 4.9. Each natural number greater than 1 is either a prime number or is a product of prime numbers.

• Theorem 4.14. Let $$a, r \in \mathbb{R}$$. If a geometric sequence is defined by $$a_1 = a$$ and for each $$n \in \mathbb{N}$$, $$a_{n + 1} = r \cdot a_n$$, then for each $$n \in \mathbb{N}$$, $$a_n = a \cdot r^{n - 1}$$.

• Theorem 4.15. Let $$a, r \in \mathbb{R}$$. If the sequence $$S_1, S_2, ..., S_n, ...$$ is defined by $$S_1 = a$$ and for each $$n \in \mathbb{N}$$, $$S_{n + 1} = a + r \cdot S_n$$, then for each $$n \in \mathbb{N}$$, $$S_n = a + a \cdot r + a \cdot r^2 + \cdot\cdot\cdot + a \cdot r^{n - 1}$$. That is, the geometric series $$S_n$$ is the sum of the first n terms of the corresponding geometric sequence.

• Theorem 4.16. Let $$a, r \in \mathbb{R}$$ and $$r \ne 1$$. If the sequence $$S_1, S_2, ..., S_n, ...$$ is defined by $$S_1 = a$$ and for each $$n \in \mathbb{N}$$, $$S_{n + 1} = a + r \cdot S_n$$, then for each $$n \in \mathbb{N}$$, $$S_n = a (\dfrac{1 - r^n}{1 - r})$$.