In this section, we inductively prove mathematical statements such as

1. \(1^3+2^3+3^3+\cdots +n^3=\left(\frac{n(n+1)}{2}\right)^2\) for all positive integers \(n\).


2. \(n^3-n\) is divisible by \(6\) for each nonnegative integer \(n\).


3. \(2^n>n^2\) for all integers \(n>4\).

Mathematical induction:
The statement \(P(n)\) is true for all positive integers \(n\) if we complete the following two steps.
Basis step: Show \(P(1)\) is true.
Inductive step: Assume that \(P(k)\) is true for some positive integer \(k\) (inductive hypothesis). Show \(P(k+1)\) is true.

Example. Prove that \(1^3+2^3+3^3+\cdots +n^3=\left(\frac{n(n+1)}{2}\right)^2\) for all positive integers \(n\).

Proof. For all positive integers \(n\), let \(P(n)\) be the statement \[ \text{``$1^3+2^3+3^3+\cdots +n^3=\left(\frac{n(n+1)}{2}\right)^2$."} \] Basis step: \(1^3=\left(\frac{1(1+1)}{2}\right)^2\). Thus \(P(1)\) is true.
Inductive step: Assume that \(P(k)\) is true for some positive integer \(k\), i.e., \[1^3+2^3+3^3+\cdots +k^3=\left(\frac{k(k+1)}{2}\right)^2 \text{ (inductive hypothesis)}.\] We show \(P(k+1)\) is true, i.e., \[1^3+2^3+3^3+\cdots +k^3+(k+1)^3=\left(\frac{(k+1)(k+2)}{2}\right)^2.\] \[\begin{eqnarray*} 1^3+2^3+3^3+\cdots +k^3+(k+1)^3 &=& (1^3+2^3+3^3+\cdots +k^3)+(k+1)^3\\ &=& \left(\frac{k(k+1)}{2}\right)^2+(k+1)^3 \text{ (by the inductive hypothesis)}\\ &=& (k+1)^2 \left[\left(\frac{k}{2}\right)^2+(k+1)\right] \\ &=& (k+1)^2 \left[\frac{k^2+4k+4}{4}\right] \\ &=& (k+1)^2 \left(\frac{k+2}{2}\right)^2 \\ &=& \left(\frac{(k+1)(k+2)}{2}\right)^2. \end{eqnarray*}\] By mathematical induction, \(P(n)\) is true for all positive integers \(n\).

Remark. For some problems with a given integer \(a\), we need to prove that \(P(n)\) is true for all integers \(n\geq a\). In a proof by mathematical induction, we modify the basis step and inductive step as follows:

Basis step: Show \(P(a)\) is true.
Inductive step: Assume that \(P(k)\) is true for some integer \(k\geq a\) (inductive hypothesis). Show \(P(k+1)\) is true.

Example. Prove that \(2^n > n^2\) for all integers \(n > 4\).

Proof. For all integers \(n\geq 5\), let \(P(n)\) be the statement \[\text{``$2^n > n^2$."}\] Basis step: \(2^5=32 > 25=5^2\). Thus \(P(5)\) is true.
Inductive step: Assume that \(P(k)\) is true for some integer \(k\geq 5\), i.e., \[2^k>k^2 \text{ (inductive hypothesis)}.\] We show \(P(k+1)\) is true, i.e., \[2^{k+1}>(k+1)^2.\] \[\begin{eqnarray*} 2^{k+1} &=& 2\cdot 2^k\\ &>& 2\cdot k^2 \text{ (by the inductive hypothesis)}\\ &=& k^2+k^2 \\ &>& k^2+4k \text{ (since \(k>4\implies k^2 > 4k\))}\\ &=& k^2+2k+2k \\ &>& k^2+2k+1 \text{ (since \(k>4\implies 2k > 8 > 1\))}\\ &=& (k+1)^2. \end{eqnarray*}\] By mathematical induction, \(P(n)\) is true for all integers \(n > 4\).

Example. Prove that \(n^3-n\) is divisible by \(6\) for each nonnegative integer \(n\).

Proof. For all integers \(n\geq 0\), let \(P(n)\) be the statement \[\text{``$n^3-n \text{ is divisible by } 6$."}\] Basis step: \(0^3-0=0\) is divisible by \(6\). Thus \(P(0)\) is true.
Inductive step: Assume that \(P(k)\) is true for some integer \(k\geq 0\), i.e., \[k^3-k \text{ is divisible by } 6 \text{ (inductive hypothesis)}.\] We show \(P(k+1)\) is true, i.e., \((k+1)^3-(k+1) \text{ is divisible by } 6.\) \[\begin{eqnarray*} && (k+1)^3-(k+1)\\ &=& (k^3+3k^2+3k+1)-k-1\\ &=& k^3+3k^2+3k-k\\ &=& (k^3-k)+3k(k+1) \end{eqnarray*}\] Since \(k\) or \(k+1\) is even, \(k(k+1)\) is even and consequently \(3k(k+1)\) is divisible by \(6\). By the inductive hypothesis, \(k^3-k\) is divisible by \(6\). Thus \[(k+1)^3-(k+1)=(k^3-k)+3k(k+1)\] is divisible by \(6\).
By mathematical induction, \(P(n)\) is true for all integers \(n\geq 0\).

Remark. To see why mathematical induction works, we first look at the well-ordering property of natural numbers.

The well-ordering principle: Every non-empty set of positive integers contains a least element.

Now suppose that \(P(1)\) is true. Also suppose that if \(P(k)\) is true for some positive integer \(k\), then \(P(k+1)\) is true. We prove that \(P(n)\) is true for all positive integers \(n\). If not, let \(S\) be the set of all positive integers \(n > 1\) for which \(P(n)\) is not true. By the well-ordering principle, \(S\) has a least element, say \(k\). Then \(P(k)\) is false and \(P(k-1)\) is true. Since \(P(k-1)\) is true, \(P((k-1)+1)=P(k)\) is true by our hypothesis. So we get a contradiction. Thus no such \(S\) exists and \(P(n)\) is true for all positive integers \(n\).

Last edited