Discrete Math Home

## Mathematical Induction

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