1.3: The Natural Numbers and Mathematical Induction (2024)

Well-Ordering Property of the Natural Numbers

If \(A\) is a non empty subset of \(\mathbb{N}\), then there exists an element \(\ell \in A\) such that \(\ell \leq x\) for all \(x \in A\).

Theorem \(\PageIndex{1}\): Principle of Mathematical Induction

For each natural number \(n \in \mathbb{N}\), suppose that \(P(n)\) denotes a proposition which is either true or false. Let \(A=\{n \in \mathbb{N}: P(n) \text { is true }\}\). Suppose the following conditions hold:

1. \(1 \in A\).
2. For each \(k \in \mathbb{N}\), if \(k \in A\), then \(k+1 \in A\).

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

Proof

Suppose conditions (a) and (b) hold. Assume, by way of contradiction, that \(A \neq \mathbb{N}\). Set \(B=\mathbb{N} \backslash A\), that is \(B=\{n \in \mathbb{N}: P(n) \text { is false }\}\). Then \(B\) is a nonempty subset of \(\mathbb{N}\). By the Well-Ordering Property of the natural numbers, there exists a smallest element \(\ell \in B\) and, hence, we have that \(P(k)\) is true. By condition (b), we obtain that \(P(k+1)\) is true. But \(k+1= \ell\), and \(P(\ell)\) is false, since \(\ell \in B\). This is a contradiction, so the conclusion follows. \(\square\)

Example \(\PageIndex{1}\)

Prove using induction that for all \(n \in \mathbb{N}\)

\[1+2+\cdots+n=\frac{n(n+1)}{2}.\]

Solution

The statement \(P(n)\) is the equality \(1+2+\cdots+n=\frac{n(n+1)}{2}\). Now the base case says that \(1=\frac{1(1+1)}{2}\), which is clearly true.

Suppose \(P(k)\) is true for some \(k \in \mathbb{N}\). That is, suppose that \(1+2+\cdots+n=\frac{k(k+1)}{2}\) (this is the inductive hypothesis). Now we have

\[1+2+\cdots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}.\]

This shows that \(P(k+1)\) is true. We have now proved conditions (a) and (b) of Theorem 1.3.1. Therefore, by the principle of mathematical induction we conclude that

\[1+2+\cdots+n=\frac{n(n+1)}{2} \text { for all } n \in \mathbb{N}.\]

Example \(\PageIndex{2}\)

Prove using induction that for all \(n \in \mathbb{N}, 7^{n}-2^{n}\) is divisible by 5.

Solution

For \(n=1\), we have \(7-2=5\), which is clearly a multiple of 5.

Suppose that \(7^{k}-2^{k}\) is a multiple of 5 for some \(k \in \mathbb{N}\). That is, there is an integer \(j\) such that \(7^{k}-2^{k}=5 j\). Let us write \(7^{k}-2^{k}=5 j\). Now, substituting this expression below, we have

\[7^{k+1}-2^{k+1}=7 \cdot 7^{k}-2 \cdot 2^{k}=7\left(2^{k}+5 j\right)-2 \cdot 2^{k}=7 \cdot 2^{k}-2 \cdot 2^{k}+7 \cdot 5 j=2^{k}(7-2)+5 \cdot 7 j=5\left(2^{k}+7 j\right)\]

It follows that \(7^{k+1}-2^{k+1}\) is a multiple of 5. This proves the inductive step.

We conclude by induction that \(7^{n}-2^{n}\) is divisible by 5 for all \(n \in \mathbb(N)\).

Example \(\PageIndex{3}\)

Prove using induction that for all \(n \in \mathbb{N}\)

\[n+1 \leq 2^{n}\]

Solution

For \(n=1\), we have \(1+1=2=2^{1}\), so the base case is true.

Suppose next that \(k+1 \leq 2^{k}\) for some \(k \in \mathbb{N}\). Then \(k+1+1 \leq 2^{k}+1\). Since \(2^{k}\) is a positive integer, we also have \(1 \leq 2^{k}\). Therefore,

\[(k+1)+1 \leq 2^{k}+1 \leq 2^{k}+2^{k}=2 \cdot 2^{k}=2^{k+1}.\]

We conclude by the principle of mathematical induction that \(n+1 \leq 2^{n}\) for all \(n \in \mathbb{N}\).

The following result is known as the Generalized Principle of Mathematical Induction. It simply states that we can start the induction process at any integer \(n_{0}\), and then we obtain the truth of all statements \(P(n)\) for \(n \geq n_{0}\).

Theorem \(\PageIndex{2}\) - Generalized Principle of Mathematical Induction.

Let \(n_{0} \in \mathbb{N}\) and for each natural \(n \geq n_{0}\), suppose that \(P(n)\) denotes a proposition which is either true or false. Let \(A=\{n \in \mathbb{N}: P(n) \text{ is true}\}\). Suppose the following two conditions hold:

1. \(n_{0} \in A\).
2. For each \(k \in \mathbb{N}\), \(k \geq n_{0}\), if \(k \in A\), then \(k+1 \in A\).

Proof

Suppose conditions (a) and (b) hold. Assume, by way of contradiction, that \(A \nsupseteq\{k \in \mathbb{N}: \left.k \geq n_{0}\right\}\). Set \(B=\left\{n \in \mathbb{N}: n \geq n_{0}, P(n) \text { is false }\right\}\). Then \(B\) is a nonempty subset of \(\mathbb{N}\). By the Well-Ordering Property of natural numbers, there exists a smallest element \(\ell \in B\). By condition (a), \(n_{0} \notin B\). Hence, \(\ell \geq n_{0}+1\). It follows that \(k=\ell-1 \geq n_{0}\). Since \(k<\ell\), \(k \notin B\) and, so, we have that \(P(k)\) is true. By condition (b), we obtain that \(P(k+1)\) is true. But \(k+1= \ell\), and \(P(\ell)\) is false, since \(\ell \in B\). This is a contradiction, so the conclusion follows. \(\square\)

Example \(\PageIndex{4}\)

Prove by induction that \(3 n<2^{\prime}\) for all \(n \geq 4\).

Solution

The statement is true for \(n=4\) since \(12<16\). Suppose next that \(3 k<2^{k}\) for some \(k \in \mathbb{N}\), \(k \geq 4\). Now,

\[3(k+1)=3 k+3<2^{k}+3<2^{k}+2^{k}=2^{k+1},\]

where the second inequality follows since \(k \geq 4\) and, so, \(2^{k} \geq 16>3\). This shows that \(P(k+1)\) is true. Thus, by the generalized principle of induction, the inequality holds for all \(n \geq 4\).

Next we present another variant of the induction principle which makes it easier to prove the inductive step. Despite its name, this principle is equivalent to the standard one.

Theorem \(\PageIndex{3}\) - Principle of Strong Induction.

For each natural \(n \in \mathbb{N}\), suppose that \(P(n)\) denotes a proposition which is either true or false. Let \(A=\{n \in \mathbb{N}: P(n) \text { is true }\}\). Suppose the following two conditions hold:

1. \(1 \in A\).
2. For each \(k \in \mathbb{N}\), if \(1,2, \ldots, k \in A\), then \(k+1 \in A\)

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

Proof

Add proof here and it will automatically be hidden

Remark \(\PageIndex{4}\)

Note that the inductive step above says that, in order to prove \(P(k+1)\) is true, we may assume not only that \(P(k)\) is true, but also that \(P(1), P(2), \ldots, P(k-1)\) are true.

Example \(\PageIndex{5}\)

Prove by induction that every positive integer greater than 1 is either a prime number or a product of prime numbers.

Solution

Clearly, the statement is true for \(n=2\). Suppose the statement holds for any positive integer \(m \in\{2, \ldots, k\}\), where \(k \in \mathbb{N}\), \(k \geq 2\). If \(k+1\) is prime, the statement holds for \(k+1\). Otherwise, there are positive integers \(p, q>1\) such that \(k+1=pq\). Since \(p, q \leq k\), by the inductive assumption applied to both \(p\) and \(q\) we can find prime numbers \(r_{1}, \ldots, r_{\ell}\) and \(s_{1}, \ldots, s_{m}\) such that \(p=r_{1} \cdots r_{\ell}\) and \(q=s_{1} \cdots s_{m}\) (note that \(\ell\) and \(m\) may both equal 1). But then

\[k+1=r_{1} \cdots r_{\ell} s_{1} \cdots s_{m}\]

Thus, the statement holds true for \(k+1\). The conclusion now follows by the principle of Strong Induction.

Example \(\PageIndex{4}\)

Prove the following using induction.

1. \(2 n+1 \leq 2^{n}\) for \(n \geq 3\) (\(n \in \mathbb{N}\)).
2. \(n^{2} \leq 3^{n}\) for all \(n \in \mathbb{N}\). (Hint: show first that for all \(n \in \mathbb{N}\), \(2 n \leq n^{2}+1\). This does not require induction..)
3. \(n^{3} \leq 3^{n}\) for all \(n \in \mathbb{N}\). (Hint: Check the cases \(n=1\) and \(n=2\) directly and then use induction for \(n \geq 3\).)

Solution

Add text here.