section-math-induction.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section2.1Mathematical Induction

¶

Suppose we wish to show that

$$\begin{equation*} 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \end{equation*}$$

for any natural number $n\text{.}$ This formula is easily verified for small numbers such as $n = 1\text{,}$ 2, 3, or 4, but it is impossible to verify for all natural numbers on a case-by-case basis. To prove the formula true in general, a more generic method is required.

Suppose we have verified the equation for the first $n$ cases. We will attempt to show that we can generate the formula for the $(n + 1)$th case from this knowledge. The formula is true for $n = 1$ since

$$\begin{equation*} 1 = \frac{1(1 + 1)}{2}. \end{equation*}$$

If we have verified the first $n$ cases, then

$$\begin{align*} 1 + 2 + \cdots + n + (n + 1) & = \frac{n(n + 1)}{2} + n + 1\\ & = \frac{n^2 + 3n + 2}{2}\\ & = \frac{(n + 1)[(n + 1) + 1]}{2}. \end{align*}$$

This is exactly the formula for the $(n + 1)$th case.

This method of proof is known as . Instead of attempting to verify a statement about some subset $S$ of the positive integers ${\mathbb N}$ on a case-by-case basis, an impossible task if $S$ is an infinite set, we give a specific proof for the smallest integer being considered, followed by a generic argument showing that if the statement holds for a given case, then it must also hold for the next case in the sequence. We summarize mathematical induction in the following axiom.

Principle2.1First Principle of Mathematical Induction

Let $S(n)$ be a statement about integers for $n \in {\mathbb N}$ and suppose $S(n_0)$ is true for some integer $n_0\text{.}$ If for all integers $k$ with $k \geq n_0\text{,}$ $S(k)$ implies that $S(k+1)$ is true, then $S(n)$ is true for all integers $n$ greater than or equal to $n_0\text{.}$

Example2.2

For all integers $n \geq 3\text{,}$ $2^n \gt n + 4\text{.}$ Since

$$\begin{equation*} 8 = 2^3 \gt 3 + 4 = 7, \end{equation*}$$

the statement is true for $n_0 = 3\text{.}$ Assume that $2^k \gt k + 4$ for $k \geq 3\text{.}$ Then $2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\text{.}$ But

$$\begin{equation*} 2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4 \end{equation*}$$

since $k$ is positive. Hence, by induction, the statement holds for all integers $n \geq 3\text{.}$

Example2.3

Every integer $10^{n + 1} + 3 \cdot 10^n + 5$ is divisible by 9 for $n \in {\mathbb N}\text{.}$ For $n = 1\text{,}$

$$\begin{equation*} 10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15 \end{equation*}$$

is divisible by 9. Suppose that $10^{k + 1} + 3 \cdot 10^k + 5$ is divisible by 9 for $k \geq 1\text{.}$ Then

$$\begin{align*} 10^{(k + 1) + 1} + 3 \cdot 10^{k + 1} + 5& = 10^{k + 2} + 3 \cdot 10^{k + 1} + 50 - 45\\ & = 10 (10^{k + 1} + 3 \cdot 10^{k} + 5) - 45 \end{align*}$$

is divisible by 9.

Example2.4

We will prove the binomial theorem using mathematical induction; that is,

$$\begin{equation*} (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}, \end{equation*}$$

where $a$ and $b$ are real numbers, $n \in \mathbb{N}\text{,}$ and

$$\begin{equation*} \binom{n}{k} = \frac{n!}{k! (n - k)!} \end{equation*}$$

is the binomial coefficient. We first show that

$$\begin{equation*} \binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}. \end{equation*}$$

This result follows from

$$\begin{align*} \binom{n}{k} + \binom{n}{k - 1} & = \frac{n!}{k!(n - k)!} +\frac{n!}{(k-1)!(n - k + 1)!}\\ & = \frac{(n + 1)!}{k!(n + 1 - k)!}\\ & =\binom{n + 1}{k}. \end{align*}$$

If $n = 1\text{,}$ the binomial theorem is easy to verify. Now assume that the result is true for $n$ greater than or equal to 1. Then

$$\begin{align*} (a + b)^{n + 1} & = (a + b)(a + b)^n\\ & = (a + b) \left( \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\right)\\ & = \sum_{k = 0}^{n} \binom{n}{k} a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n + 1 - k}\\ & = a^{n + 1} + \sum_{k = 1}^{n} \binom{n}{k - 1} a^{k} b^{n + 1 - k} + \sum_{k = 1}^{n} \binom{n}{k} a^k b^{n + 1 - k} + b^{n + 1}\\ & = a^{n + 1} + \sum_{k = 1}^{n} \left[ \binom{n}{k - 1} + \binom{n}{k} \right]a^k b^{n + 1 - k} + b^{n + 1}\\ & = \sum_{k = 0}^{n + 1} \binom{n + 1}{k} a^k b^{n + 1- k}. \end{align*}$$

We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.

Principle2.5Second Principle of Mathematical Induction

Let $S(n)$ be a statement about integers for $n \in {\mathbb N}$ and suppose $S(n_0)$ is true for some integer $n_0\text{.}$ If $S(n_0), S(n_0 + 1), \ldots, S(k)$ imply that $S(k + 1)$ for $k \geq n_0\text{,}$ then the statement $S(n)$ is true for all integers $n \geq n_0\text{.}$

A nonempty subset $S$ of ${\mathbb Z}$ is if $S$ contains a least element. Notice that the set ${\mathbb Z}$ is not well-ordered since it does not contain a smallest element. However, the natural numbers are well-ordered.

Principle2.6Principle of Well-Ordering

Every nonempty subset of the natural numbers is well-ordered.

The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.

Lemma2.7

The Principle of Mathematical Induction implies that $1$ is the least positive natural number.

Proof

Let $S = \{ n \in {\mathbb N} : n \geq 1 \}\text{.}$ Then $1 \in S\text{.}$ Assume that $n \in S\text{.}$ Since $0 \lt 1\text{,}$ it must be the case that $n = n + 0 \lt n + 1\text{.}$ Therefore, $1 \leq n \lt n + 1\text{.}$ Consequently, if $n \in S\text{,}$ then $n + 1$ must also be in $S\text{,}$ and by the Principle of Mathematical Induction, and $S = \mathbb N\text{.}$

Theorem2.8

The Principle of Mathematical Induction implies the Principle of Well-Ordering. That is, every nonempty subset of $\mathbb N$ contains a least element.

Proof

We must show that if $S$ is a nonempty subset of the natural numbers, then $S$ contains a least element. If $S$ contains 1, then the theorem is true by Lemma 2.7. Assume that if $S$ contains an integer $k$ such that $1 \leq k \leq n\text{,}$ then $S$ contains a least element. We will show that if a set $S$ contains an integer less than or equal to $n + 1\text{,}$ then $S$ has a least element. If $S$ does not contain an integer less than $n+1\text{,}$ then $n+1$ is the smallest integer in $S\text{.}$ Otherwise, since $S$ is nonempty, $S$ must contain an integer less than or equal to $n\text{.}$ In this case, by induction, $S$ contains a least element.

Induction can also be very useful in formulating definitions. For instance, there are two ways to define $n!\text{,}$ the factorial of a positive integer $n\text{.}$

• The explicit definition: $n! = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n\text{.}$

• The inductive or recursive definition: $1! = 1$ and $n! = n(n - 1)!$ for $n \gt 1\text{.}$

Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly, often results in better understanding of complex issues.