Skip to main content

Beginning Activity Beginning Activity 1: Exploring Statements of the Form \(\left( \forall n \in \N \right)\left( P(n) \right)\)
A4US

One of the most fundamental sets in mathematics is the set of natural numbers \(\N\text{.}\) In this section, we will learn a new proof technique, called mathematical induction, that is often used to prove statements of the form \(\left( \forall n \in \N \right)\left( P(n) \right)\text{.}\) In Section 4.2, we will learn how to extend this method to statements of the form \(\left( \forall n \in T \right)\left( P(n) \right)\text{,}\) where \(T\) is a certain type of subset of the integers \(\Z\text{.}\)

For each natural number \(n\text{,}\) let \(P(n)\) be the following open sentence:

\begin{equation*} 4 \text{ divides } \left( {5^n - 1} \right)\!\text{.} \end{equation*}

1.

Does this open sentence become a true statement when \(n = 1\text{?}\) That is, is 1 in the truth set of \(P(n)\text{?}\)

2.

Does this open sentence become a true statement when \(n = 2\text{?}\) That is, is 2 in the truth set of \(P(n)\text{?}\)

3.

Choose at least four more natural numbers and determine whether the open sentence is true or false for each of your choices.

All of the examples that were used should provide evidence that the following proposition is true:

\begin{equation*} \text{For each natural number } n, 4 \text{ divides } \left( {5^n - 1} \right)\text{.} \end{equation*}

We should keep in mind that no matter how many examples we try, we cannot prove this proposition with a list of examples because we can never check if 4 divides \(\left( {5^n - 1} \right)\) for every natural number \(n\text{.}\) Mathematical induction will provide a method for proving this proposition.

For another example, for each natural number \(n\text{,}\) we now let \(Q( n )\) be the following open sentence:

\begin{equation} 1^2 + 2^2 + \, \cdots \, + n^2 = \frac{{n(n + 1)(2n + 1)}}{6}\text{.}\tag{15} \end{equation}

The expression on the left side of the previous equation is the sum of the squares of the first \(n\) natural numbers. So when \(n = 1\text{,}\) the left side of equation (15) is \(1^2\text{.}\) When \(n = 2\text{,}\) the left side of equation (15) is \(1^2 + 2^2\text{.}\)

4.

Does \(Q ( n )\) become a true statement when

(a)

\(n = 1\text{?}\) (Is 1 in the truth set of \(Q ( n )\text{?}\))

(b)

\(n = 2\text{?}\) (Is 2 in the truth set of \(Q ( n )\text{?}\))

(c)

\(n = 3\text{?}\) (Is 3 in the truth set of \(Q ( n )\text{?}\))

5.

Choose at least four more natural numbers and determine whether the open sentence is true or false for each of your choices. A table with the columns \(n\text{,}\) \(1^2 + 2^2 + \, \cdots \, + n^2\text{,}\) and \(\dfrac{{n(n + 1)(2n + 1)}}{6}\) may help you organize your work.

All of the examples we have explored, should indicate the following proposition is true:

For each natural number \(n\text{,}\) \(1^2 + 2^2 + \, \cdots \, + n^2 = \dfrac{{n(n + 1)(2n + 1)}}{6}\text{.}\)
In this section, we will learn how to use mathematical induction to prove this statement.