## Mathematical Induction |

In this section, we inductively prove mathematical statements such as

- \(1^3+2^3+3^3+\cdots +n^3=\left(\frac{n(n+1)}{2}\right)^2\) for all positive integers \(n\).
- \(n^3-n\) is divisible by \(6\) for each nonnegative integer \(n\).
- \(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