11.4 Three Principles

Three Methods

Principle of Mathematical Induction (PMI)

Principle of Complete Induction (PCI)

Principle of Well Ordering

Useful for proving theorems of the form \(\left(\forall n)P(n\right)\).
Definition of functions \(f(n)\).

Principle of Mathematical Induction

Let \(S \subseteq \mathbb{N}\) be a subset such that:

\(1 \in S\).
\(\forall n \, (n \in S \Rightarrow n+1 \in S)\).

Then \(S = \mathbb{N}\).

Example

Why \(17 \in S\)?
- \(1 \in S \Rightarrow 1 \in S \Rightarrow 2 \in S\).
- then \(2 \in S\).
- \(2 \in S \Rightarrow 2 \in S \Rightarrow 3 \in S\).
- then \(3 \in S\).
- \(3 \in S \Rightarrow 3 \in S \Rightarrow 4 \in S\).
So \(4 \in S\).... \(17 \in S\).

Particular definition

In general, a subset \(S \subseteq \mathbb{R}\) is called inductive if \(\forall x \, (x \in S \Rightarrow x+1 \in S)\).

For example, \(\{5,6,7,8,\ldots\}\) is inductive.

\(S = \{2, 4, 6, 8, \dots \}\) is not inductive because \(2 \in S \Rightarrow 3 \in S\) is false.

For example, \([1,\infty)\) is inductive.

Fact: \(\mathbb{N}\) is the smallest inductive subset of \(\mathbb{R}\) that contains \(1\).

Proof of \(\forall n \, P(n)\) by using the PMI

To show that \(\forall n \, P(n)\) is true, it is enough to show:

\(P(1)\) is true.
\(P(n) \Rightarrow P(n+1)\) for all \(n\).

Why? Let \(S\) be the true set of \(P(n)\).

By (1), \(1 \in S\), so \(P(1)\) is true.
Suppose \(n \in S\), so \(P(n)\) is true.
By (2), \(P(n) \Rightarrow P(n+1)\) is true, so \(P(n+1)\) is true.

So \(n+1 \in S\). By the PMI, \(S = \mathbb{N}\).

Example

Prove that the sum of the first \(n\) odd numbers is \(n^2\) for all \(n\). \(P(n): 1 + 3 + 5 + \dots + (2n - 1) = n^2\)

Proof:

Base Case: We first prove \(P(1)\).

For \(n = 1\), we have:
- Left-Hand Side (L.H.S) \(= 1\)
- Right-Hand Side (R.H.S) \(= 1^2 = 1\)
So the result is true in this case. (We proved that \(P(1)\) is true)
Inductive Step: Assume that \(1 + 3 + \dots + (2n - 1) = n^2\) (Inductive Hypothesis, I.H.).

We want to show:
\(1 + 3 + \dots + (2n - 1) + 2(n + 1) - 1 = (n + 1)^2\)

Now,
\(\text{L.H.S} = (1 + 3 + \dots + (2n - 1)) + 2(n + 1) - 1\)

Using the I.H., this becomes:
\(= n^2 + 2n + 1 = (n + 1)^2 = \text{R.H.S}\)

Therefore, the result is true for all \(n\) by induction.

Remark

To show \(P(n) \Rightarrow P(n+1)\) in general, we use the direct method.

So we assume \(P(n)\) is true. This assumption is called the inductive hypothesis (IH).

We use the IH, \(P(n)\), and previous knowledge to deduce \(P(n+1)\).

After proving \(P(1)\) and \(P(n) \Rightarrow P(n+1)\), we can say: "The result is true for all \(n\) by induction."

Remark

If we want to show \((\forall n \geq 17) , P(n)\), it is enough to show:

\(P(17)\) is true.
\((\forall n \geq 17 ), (P(n) \Rightarrow P(n+1))\).

PMI and Recursive Definitions

To define a function \(f(n)\) for all \(n\), it is enough to:

Define \(f(1)\).
Define \(f(n+1)\) in terms of \(f(n)\).

Why? Let \(S = \{ n \in \mathbb{N} : f(n) \text{ is defined} \}\). Check that \(S = \mathbb{N}\) using PMI.

Example

Definition of \(n!\) (n factorial).

\(1! = 1\)
\((n+1)! = n! \cdot (n+1)\)

For example, \(10! = 9! \cdot 10 = 8! \cdot 9 \cdot 10 = 7! \cdot 8 \cdot 9 \cdot 10 = \dots = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10\)

Definition of \(a^n\).

\(a^1 = a\)
\(a^{n+1} = a^n \cdot a\)

\(\sum\) and \(\prod\). Let \((a_n)\) be a sequence of real numbers.

We define \(\sum_{k=1}^n a_k\) (sum from 1 to \(n\)) as follows:

\(\sum_{k=1}^1 a_k = a_1\)
\(\sum_{k=1}^{n+1} a_k = \sum_{k=1}^n a_k + a_{n+1}\)

We define \(\prod_{k=1}^n a_k\) (product from 1 to \(n\)) as follows:

\(\prod_{k=1}^1 a_k = a_1\)
\(\prod_{k=1}^{n+1} a_k = \prod_{k=1}^n a_k \cdot a_{n+1}\)

For example, \(n! = \prod_{k=1}^n k\).

Example

Prove that \(\prod_{i=1}^n (4i - 2) = \frac{(2n)!}{n!}\) for all \(n\).

Proof:

For \(n = 1\):

Left-Hand Side (LHS) \(= 4 \cdot 1 - 2 = 2\).
Right-Hand Side (RHS) \(= \frac{(2 \cdot 1)!}{1!} = \frac{2!}{1!} = \frac{2 \cdot 1}{1} = 2\).

Thus, the result is true for \(n=1\).

We now assume \(\prod_{i=1}^n (4i - 2) = \frac{(2n)!}{n!}\) (Inductive Hypothesis, I.H.). We want to prove \(\prod_{i=1}^{n+1} (4i - 2) = \frac{(2(n+1))!}{(n+1)!}\)

Left-Hand Side (LHS):
\(\prod_{i=1}^{n+1} (4i - 2) = \left( \prod_{i=1}^n (4i - 2) \right) \cdot (4(n+1) - 2)\) \(= \frac{(2n)!}{n!} \cdot (4n + 2)\)

Right-Hand Side (RHS):
\(\frac{(2n+2)!}{(n+1)!} = \frac{(2n+2)(2n+1)(2n)!}{(n+1) \cdot n!}= \frac{2(2n+1) \cdot (2n)!}{n!} = (4n+2) \cdot \frac{(2n)!}{n!}\)

Thus, \(\text{LHS} = \text{RHS}\).

Therefore, the result is true for all \(n \in \mathbb{N}\).

PCI (Principle of Complete Induction)

If \(S \subseteq \mathbb{N}\) satisfies:

\(1 \in S\)
\(\forall n \left( \left( \forall k \leq n, k \in S \Rightarrow P(k) \right) \Rightarrow P(n+1) \right)\)

Then \(S = \mathbb{N}\).

Proof of \(\forall n, P(n)\) by using the PCI.

It is enough to prove two things:

\(P(1)\) is true.
\(\forall n \geq 1 \left( \left( \forall k \leq n, P(k) \right) \Rightarrow P(n+1) \right)\)

Why? Let \(S = \{ n : P(n) \text{ is true} \}\). Check that \(S = \mathbb{N}\) by using the PCI.

Remark:

To show that \(\forall n \geq 5, P(n)\) is true, it is enough to show:

\(P(5)\) is true.
\(\forall n \geq 5 \left( \forall 5 \leq k \leq n, P(k) \Rightarrow P(n+1) \right)\)

Example

Every natural number \(n \geq 2\) has a prime divisor.

Let \(P(n): n\) has a prime divisor.

Proof:

If \(n = 2\), \(2\) is a prime number and \(2 \mid 2\), so the result is true.

Let \(n \geq 2\), and assume that the result is true for every \(k\) such that \(2 \leq k \leq n\). We want to show the result is true for \(n+1\) (Inductive Hypothesis, I.H.).

If \(n+1\) is prime, then \(n+1\) is a prime divisor of \(n+1\), and we are done.
Otherwise, \(n+1 = a \cdot b\) with \(2 \leq a, b \leq n\).

By the I.H., \(a\) has a prime divisor \(p\). But then \(p\) is also a prime divisor of \(n+1 = a \cdot b\).

Hence, the result is true for all \(n \geq 2\).

PCI and Recursive Definition

To define \(f(n)\) for every \(n \in \mathbb{N}\), it is enough to:

Define \(f(1)\), and
Define \(f(n+1)\) in terms of \(f(1), f(2), \dots, f(n)\).

Why? Let \(S = \{ n \in \mathbb{N} : f(n) \text{ is defined} \}\). Check that \(S = \mathbb{N}\) by using the PCI.

Example

Fibonacci Sequence

Define the sequence \(f_1, f_2, f_3, \dots\) as follows:

\(f_1 = 1\)
\(f_2 = 1\)
\(f_{n+1} = f_n + f_{n-1}\)

For example:

\(f_3 = f_2 + f_1 = 1 + 1 = 2\)
\(f_4 = f_3 + f_2 = 2 + 1 = 3\)
\(f_5 = f_4 + f_3 = 3 + 2 = 5\)

Theorem: \(f_n = \frac{1}{\sqrt{5}} \left( \alpha^n - \beta^n \right)\)

where \(\alpha = \frac{1 + \sqrt{5}}{2}\) and \(\beta = \frac{1 - \sqrt{5}}{2}\).

Observation: \(\alpha, \beta\) are roots of \(x^2 - x - 1 = 0\).

\(\alpha + \beta = 1\) and \(\alpha \beta = -1\)
\(\alpha^2 = \alpha + 1\), \(\beta^2 = \beta + 1\)
\(\alpha - \beta = \sqrt{5}\)

Proof:

For \(n = 1\), \(f_1 = 1\) and \(\frac{1}{\sqrt{5}} (\alpha - \beta) = \frac{\sqrt{5}}{\sqrt{5}} = 1\). So the result is true.

Now we show that \(\forall n \geq 1, \left( \forall 1 \leq k \leq n, P(k) \right) \Rightarrow P(n+1)\).

For \(n=1\), we show this conditional by proving that \(P(2)\) is true.

We have \(f_2 = 1\) by definition. On the other hand,
\(\frac{1}{\sqrt{5}} (\alpha^2 - \beta^2) = \frac{1}{\sqrt{5}} (\alpha - \beta)(\alpha + \beta) = \frac{\sqrt{5}}{\sqrt{5}} \cdot 1 = 1\), so the conditional is true for \(n = 1\).

We now show the condition for \(n\geq 2\)

We assume that the result is true for \(k\) such that \(1\leq k\leq n\)

We want to show the result for \(n+1\), that is, \(f_{n+1} = \frac{1}{\sqrt{5}} \left( \alpha^{n+1} - \beta^{n+1} \right)\).

Left-Hand Side (LHS):
\(f_n + f_{n-1} = \frac{1}{\sqrt{5}} \left( \alpha^n - \beta^n \right) + \frac{1}{\sqrt{5}} \left( \alpha^{n-1} - \beta^{n-1} \right)\)\(=\frac{1}{\sqrt5}\left(\alpha^{n-1}\cdot\alpha-\beta^{n-1}\cdot\beta\right)+\frac{1}{\sqrt5}\left(\alpha^{n-1}-\beta^{n-1}\right)\)

\(=\)\(\frac{1}{\sqrt{5}} \left[ \alpha^{n-1} (\alpha + 1) - \beta^{n-1} (\beta + 1) \right]\)\(= \frac{1}{\sqrt{5}} \left( \alpha^{n-1} \alpha^2 - \beta^{n-1} \beta^2 \right)\)\(= \frac{1}{\sqrt{5}} \left( \alpha^{n+1} - \beta^{n+1} \right) = \text{R.H.S.}\)

So the result is true for \(n+1\).

Therefore, the result is true for all \(n\) by complete induction.

Principle of Well-Ordering

Every non-empty subset \(S \subseteq \mathbb{N}\) has a first (smallest) element.

We can use this principle to prove theorems of the form \(\forall n, P(n)\) by contradiction.

‍