1.3: The Natural Numbers and Mathematical Induction

We will assume familiarity with the set \(\mathbb{N}\) of natural numbers, with the usual arithmetic operations of addition and multiplication on \(\mathbb{n}\), and with the notion of what it means for one natural number to be less than another.

In addition, we will also assume the following property of the natural numbers.

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\).

To paraphrase the previous property, every nonempty subset of positive integers has a smallest element.

The principle of mathematical induction is a useful tool for proving facts about sequences.

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\)

To paraphrase, the principle says that, given a list of propositions \(P(n)\), one for each \(n \in \mathbb{N}\), if \(P(1)\) is true and, moreover, \(P(k+1)\) is true whenever \(P(k)\) is true, then all propositions are true.

We will refer to this principle as mathematical induction or simply induction. Condition (a) above is called the base case and condition (b) the inductive step. When proving (b), the statement \(P(k)\) is called the inductive hypothesis.

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.

There is also a generalized version of this theorem where the base case is for some integer \(n_{0}>1\).

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.

Exercise \(\PageIndex{1}\)

Prove the following using Mathematical Induction.

1. \(1^{2}+2^{2}+\cdots+n^{2}=\frac{n(n+1)(2 n+1)}{6} \text { for all } n \in \mathbb{N}\).
2. \(1^{3}+2^{3}+\cdots+n^{3}=\frac{n^{2}(n+1)^{2}}{4} \text { for all } n \in \mathbb{N}\).
3. \(1+3+\cdots+(2 n-1)=n^{2} \text { for all } n \in \mathbb{N}\).

Answer

Add texts here. Do not delete this text first.

Exercise \(\PageIndex{2}\)

Prove that for all \(n \in \mathbb{N}\), \(9^{n}-5^{n}\) is divisible by \(4\).

Answer

Add texts here. Do not delete this text first.

Exercise \(\PageIndex{3}\)

Prove that for all \(n \in \mathbb{N}\), \(7^{n}-1\) is divisible by \(3\)

Answer

Add texts here. Do not delete this text first.

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.

Exercise \(\PageIndex{5}\)

Given a real number \(a \neq 1\), prove that

\[1+a+a^{2}+\cdots+a^{n}=\frac{1-a^{n+1}}{1-a} \text { for all } n \in \mathbb{N}.\]

Answer

Add texts here. Do not delete this text first.

Exercise \(\PageIndex{6}\)

The Fibonacci sequence is defined by

\[a_{1}=a_{2}=1 \text { and } a_{n+2}=a_{n+1}+a_{n} \text { for } n \geq 1.\]

Prove

\[a_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right].\]

Answer

Add texts here. Do not delete this text first.

Exercise \(\PageIndex{7}\)

Let \(a \geq-1\). Prove by induction that

\[(1+a)^{n} \geq 1+n a \text { for all } n \in \mathbb{N}.\]

Answer

Add texts here. Do not delete this text first.

Exercise \(\PageIndex{8}\)

Let \(a, b \in \mathbb{R}\) and \(n \in \mathbb{N}\). Use Mathematical Induction to prove the binomial theorem

\[(a+b)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l}
n \\
k
\end{array}\right) a^{k} b^{n-k},\]

where \(\left(\begin{array}{l}
n \\
k
\end{array}\right)=\frac{n !}{k !(n-k) !}\).

Answer

Add texts here. Do not delete this text first.