Opening the book…
Suppose \(P(n)\) is a predicate where the variable \(n\) has domain the positive, whole numbers. If
\(P(1)\) is true, and
\((\forall k) (P(k) \rightarrow P(k+1))\) is true,
then \((\forall n)P(n)\) is true.
It is usual to take the principle of mathematical induction as an axiom; that is, we assume that mathematical induction is valid without proving it.
Below is an outline of the idea behind why it is reasonable to assume that mathematical induction is valid. However, this outline does not constitute a proof since it technically uses mathematical induction implicitly.
Suppose \(n\) is fixed. We have a sequence of valid arguments:
\(\begin{equation}
\begin{array}
P(1) \rightarrow P(2) & \qquad P(2) \rightarrow P(3) & \qquad \cdots & \qquad P(n-1) \rightarrow P(n) \\
P(1) & \qquad P(2) & & \qquad P(n-1) \\
\hline P(2) & \hline \qquad P(3) && \hline \qquad P(n)
\end{array}
\end{equation}\)
Each is valid (modus ponens). So if we make the two assumptions stated in the principles (i.e. that \(P(1)\) is true and that \(P(k) \rightarrow P(k+1)\) is always true) we can trace the flow of truth from premises to conclusion in each argument in turn:
Premises true so conclusion is true.
Premises true (using conclusion of the first argument) so conclusion is true.
…
Premises true (using conclusion of the \((n-2)^{th}\) argument) so conclusion is true.
The conclusion of \((n-1)^{th}\) argument is \(P(n)\text{,}\) so \(P(n)\) is true.
Now, here is some specific terminology associated to proofs by induction.
the statement \(P(1)\) in a proof by mathematical induction
the portion of a proof by mathematical induction that establishes the statement \((\forall k) ( P(k) \rightarrow P(k+1) )\)
the assumption \(P(k)\) made as the first step in the induction step of a proof by mathematical induction
To prove a universal statement indexed by whole numbers:
Base case.
Start by proving the statement obtained from the universally quantified predicate for the base case \(n = 1\text{.}\)
Induction step.
Next, assume that \(k\) is a fixed number such that \(k \ge 1\text{,}\) and that the statement obtained from the universally quantified predicate is true for \(n = k\text{.}\) Based on this assumption, try to prove that the next case, \(n=k+1\text{,}\) is also true.
Prove that the sum of the first \(n\) positive integers is
Solution
We want to prove \((\forall n)P(n)\text{,}\) where \(P(n)\) is as follows.
We will prove this by induction.
Base case.
\(1 = (1\cdot2)/2\) is obviously true.
Induction step.
Assume the statement is true for \(n=k\text{;}\) i.e. assume that
\begin{equation*} 1 + 2 + \cdots + k = k(k+1)/2 \text{.} \end{equation*}
We want to show that this implies the statement is true for \(n = k+1\text{;}\) i.e. show
\begin{equation*} 1 + 2 + \cdots + k + (k+1) = (k+1)(k+2)/2\text{.} \end{equation*}
We have
\begin{align*} 1 + 2 + \cdots + k + (k+1) & = (1 + 2 + \cdots + k) + (k+1) \\ & = \dfrac{k(k+1)}{2} + (k+1) \\ & = \dfrac{k^2 + 3k + 2}{2} \\ & = \dfrac{(k+1)(k+2)}{2} \text{.} \end{align*}
Prove that \(n^3 + (n+1)^3 + (n+2)^3\) is always divisible by \(9\) for every \(n \ge 1\text{.}\)
Solution
We want to prove \((\forall n)P(n)\text{,}\) where \(P(n)\) is as follows.
\begin{align*} P(1) & \colon \quad 1^3 + 2^3 + 3^3 \text{ is divisible by } 9 \\ P(2) & \colon \quad 2^3 + 3^3 + 4^3 \text{ is divisible by } 9 \\ P(3) & \colon \quad 3^3 + 4^3 + 5^3 \text{ is divisible by } 9 \\ & \vdots \\ P(n) & \colon \quad n^3 + (n+1)^3 + (n+2)^3 \text{ is divisible by } 9 \\ & \vdots \end{align*}
We will prove this by induction.
Base case.
For \(n=1\text{,}\) \(n^3 + (n+1)^3 + (n+2)^3 = 36 = 9\cdot 4\text{.}\)
Induction step.
Assume \(k^3 + (k+1)^3 + (k+2)^3\) is divisible by \(9\text{.}\) This means that there exists some whole number \(m\) so that
\begin{equation*} k^3 + (k+1)^3 + (k+2)^3 = 9 m \text{.} \end{equation*}
We want to show that \((k+1)^3 + (k+2)^3 + (k+3)^3\) is also divisible by \(9\text{.}\) To make the connection between this sum of cubes and the “previous case” sum of cubes above, we can add in (and simultaneously subtract out) a \(k^3\) term:
\begin{align*} (k+1)^3 + (k+2)^3 + (k+3)^3 & = (k^3 + (k+1)^3 + (k+2)^3) + (k+3)^3 - k^3 \\ & = 9m + (k+3)^3 - k^3 \\ & = 9m + (k^3 + 9k^2 + 27k + 27) - k^3 \\ & = 9(m + k^2 + 3k + 3) \text{.} \end{align*}
Since we have factored our sum of cubes into a product involving \(9\text{,}\) that sum of cubes is divisible by \(9\text{.}\)
Prove that \(3^{3n} + 1\) is divisible by \(7\) whenever \(n\) is odd.
Solution
We do not want to use \(n\) as our induction index, since it jumps by twos. But \(n\) odd means that \(n = 2m - 1\) for some \(m\ge 1\text{,}\) so we want to prove \((\forall m)P(m)\text{,}\) where \(P(m)\) is as follows.
\begin{align*} P(1) & \colon \quad 3^3 + 1 \text{ is divisible by } 7 \\ P(2) & \colon \quad 3^9 + 1 \text{ is divisible by } 7 \\ P(3) & \colon \quad 3^{15} + 1 \text{ is divisible by } 7 \\ & \vdots \\ P(m) & \colon \quad 3^{6m-3} + 1 \text{ is divisible by } 7 \\ & \vdots \end{align*}
We will prove this by induction.
Base case.
For \(m=1\text{,}\) \(3^3+1 = 28 = 7\cdot 4\text{.}\)
Induction step.
Assume \(3^{6k-3} + 1\) is divisible by \(7\text{.}\) This means that there exists some whole number \(\ell\) so that
\begin{equation*} 3^{6k-3} + 1 = 7 \ell \text{.} \end{equation*}
We want to show \(3^{6(k+1)-3} + 1\) is divisible by \(7\text{.}\) We have
\begin{align*} 3^{6 (k + 1) - 3} + 1 & = (3^{6k - 3}) (3^6) + 1 \\ & = (3^{6k-3} + 1 - 1) (3^6) + 1 \\ & = (3^{6k-3} + 1) (3^6) - 3^6 + 1 \\ & = (7 \ell) (3^6) - 728 \\ & = 7 (3^6 \ell - 104) \text{.} \end{align*}
Since we have our expression factored into a product involving \(7\text{,}\) our expression is divisible by \(7\) as desired.
Indexing of statements does not have to start at \(1\text{.}\)
Prove \(2^n \lt n!\) whenever \(n \ge 4\text{.}\)
- Note
-
This statement is actually false for \(n=1,2,3\text{.}\)
Solution
Base case.
For \(n=4\text{,}\) \(2^4 = 16\) and \(4! = 24\text{.}\)
Induction step.
Assume \(2^k \lt k!\) for some \(k \ge 4\text{.}\) We want to show \(2^{k+1} \lt (k+1)!\text{.}\) We have
\begin{equation*} 2^{k+1} = 2(2^k) \lt 2(k!) \lt (k+1)(k!) = (k+1)! \text{.} \end{equation*}
This page titled 7.1: Principle of Mathematical Induction was last modified on Tue, 01 Sep 2026 03:35:22 GMT and is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform.
The book could not be loaded just now.