3.1: Proof by Induction

Inductive reasoning is the process of drawing conclusions after examining particular observations. This reasoning is very useful when studying number patterns. In many situations, inductive reasoning strongly suggests that the statement is valid, however, we have no way to present whether the statement is true or false, for example, Goldbach conjecture. But, in this class, we will deal with problems that are more accessible and we can often apply mathematical induction to prove our guess based on particular observations. For example, when we predict a \(n^{th}\) term for a given sequence of numbers, mathematics induction is useful to prove the statement, as it involves positive integers.

Process of Proof by Induction

There are two types of induction: regular and strong. The steps start the same but vary at the end. Here are the steps. In mathematics, we start with a statement of our assumptions and intent:

Let \(p(n), \forall n \geq n_0, \, n, \, n_0 \in \mathbb{Z_+}\) be a statement. We would show that p(n) is true for all possible values of n.

1. Show that p(n) is true for the smallest possible value of n: In our case \(p(n_0)\). AND
2. For Regular Induction: Assume that the statement is true for \(n = k,\) for some integer \(k \geq n_0\). Show that the statement is true for n = k + 1.

OR

For Strong Induction: Assume that the statement p(r) is true for all integers r, where \(n_0 ≤ r ≤ k \) for some \(k ≥ n_0\). Show that p(k+1) is true.

If these steps are completed and the statement holds, we are saying that, by mathematical induction, we can conclude that the statement is true for all values of \(n \geq n_0.\)

We shall use the following template for proof by induction:

Template for proof by induction

In order to prove a mathematical statement involving integers, we may use the following template:

Suppose \(p(n), \forall n \geq n_0, \, n, \, n_0 \in \mathbb{Z_+}\) be a statement.

For regular Induction:

• Base Case: We need to show that p(n) is true for the smallest possible value of n: In our case show that \(p(n_0)\) is true.
• Induction Hypothesis: Assume that the statement \(p(n)\) is true for any positive integer \(n = k,\) for s \(k \geq n_0\).
• Inductive Step: Show that the statement \(p(n)\) is true for \(n=k+1.\).

For strong Induction:

• Base Case: Show that p(n) is true for the smallest possible value of n: In our case \(p(n_0)\).
• Induction Hypothesis: Assume that the statement \(p(n)\) is true for all integers r, where \(n_0 ≤ r ≤ k \) for some \(k ≥ n_0\).
• Inductive Step: Show that the statement \(p(n)\) is true for \(n=k+1.\).

If these steps are completed and the statement holds, by mathematical induction, we can conclude that the statement is true for all values of \( n\geq n_0.\)

Example \(\PageIndex{1}\)

Prove for .

Solution

Let . Then is true since clearly . Thus the statement is true for .

Assume that is true for some .

We will show that .

Consider .

Since and , we have .

Thus the statement is true for all .

By induction, for all .◻

Exercise \(\PageIndex{1}\)

Prove that \(n < 2^n \) for \(n\in \mathbb{N}\).

Answer

Hint: \(k+1 < 2^k(1+1)\).

Example \(\PageIndex{2}\)

Prove that \(1 + 2 + ... + n = \displaystyle \frac{n(n + 1)}{2}, \, \forall n \in \mathbb{Z}\).

Solution:

Base step: Choose \(n = 1\). Then L.H.S =\(1\). and R.H.S \( = \frac{(1)(1 + 1)}{2}=1\)

Induction Assumption: Assume that \( 1 + 2 + ... +k= \displaystyle\frac{k(k + 1)}{2}\), for \(k \in \mathbb{Z}\).

We shall show that \(1 + 2 + ... + k + (k + 1) = \displaystyle\frac{(k + 1)[(k + 1) + 1]}{2} = \frac{(k + 1)(k + 2)}{2}\)

Consider \(1 + 2 + ... + k + (k + 1) \)

\(= \displaystyle \frac{k(k + 1)}{2} + (k + 1)\)

\(= (k + 1) \left( \displaystyle\frac{k}{2} + \displaystyle\frac{1}{1}\right)\)

\(= (k + 1) \left( \displaystyle\frac{k + 2}{2}\right)\)

\(= \displaystyle \frac{(k + 1)(k + 2)}{2}\).

Thus, by induction we have \(1 + 2 + ... + n = \displaystyle\frac{n(n + 1)}{2}, \, \forall n \in \mathbb{Z}\).

We will explore examples that are related to number patterns in the next section.