3.5 Mathematical Induction

The induction principle is a way of formalizing the intuitive idea that if you begin at $1$ and start counting ``$1,2,3,\ldots$'', then eventually you will reach any preassigned number (such as for example, $200004$).

3.55   Assumption (The Induction Principle)     Let $k$ be an integer, and let $P$ be a proposition form over $\mbox{{\bf Z}}_{\geq k}$. If

$P(k)$ is true,

and

``for all $n \in \mbox{{\bf Z}}_{\geq k}[ P(n) \mbox{$\Longrightarrow$} P(n+1)]$'' is true,

then

``for all $n \in \mbox{{\bf Z}}_{\geq k}[ P(n)]$'' is true.

In order to prove ``for all $n \in \mbox{{\bf Z}}_{\geq k},P(n)$'' by using the induction principle, you should

1. Prove that $P(k)$ is true.

2. Take a generic element $n$ of $\mbox{{\bf Z}}_{\geq k}$ and prove $(P(n) \mbox{$\Longrightarrow$} P(n+1))$.

Recall that the way to prove `` $P(n) \mbox{$\Longrightarrow$}P(n+1)$'' is true, is to assume that $P(n)$ is true and show that then $P(n+1)$ must be true.

3.56   Example. We will use the induction principle to do exercise 2.10. For all $n \in \mbox{{\bf Z}}_{\geq 1}$, let

$$P(n) = \left[\sum_{p=1}^n p^3 = \frac{n^2 (n+1)^2}{4}\right].$$

Then $P(1)$ says

$$\sum_{p=1}^1 p^3 = \frac{(1^2)(1+1)^2}{4}$$

which is true, since both sides of this equation are equal to $1$. Now let $n$ be a generic element of $\mbox{{\bf Z}}_{\geq 1}$ Then

$$\begin{eqnarray*} P(n) & \iff &\sum_{p=1}^n p^3 = \frac{n^2(n+1)^2}{4}\\ & \mbo... ...um_{p=1}^{n+1} p^3 = \frac{(n+1)^2(n+2)^2}{4}\\ & \iff& P(n+1). \end{eqnarray*}$$

It follows from the induction principle that $P(n)$ is true for all $n \in \mbox{{\bf Z}}_{\geq 1}$, which is what we wanted to prove. $\diamondsuit$

3.57   Example. We will show that for all $n \in \mbox{{\bf Z}}_{\geq 4}[ n! > 2^n].$

Proof: Define a proposition form $P$ over $\mbox{{\bf Z}}_{\geq 4}$ by

$$P(n) = [n! > 2^n].$$

Now $4! = 24 > 16 = 2^4$, so $4! > 2^4$ and thus $P(4)$ is true.

Let $n$ be a generic element of $\mbox{{\bf Z}}_{\geq 4}.$ Since $n \in \mbox{{\bf Z}}_{\geq 4}$, we know that

$$n+1 \geq 4+1 > 2.$$

Hence

$$P(n) \mbox{$\Longrightarrow$} (n! > 2^n > 0) \mbox{ and } (n+1 > 2 > 0) \mbox{{}}$$

$$\mbox{$\Longrightarrow$} (n+1) \cdot n! > 2 \cdot 2^n \mbox{{}}$$

$$\mbox{$\Longrightarrow$} ((n+1)! > 2^{n+1}) \mbox{$\Longrightarrow$}P(n+1). \mbox{{}}$$

Hence, for all $n \in \mbox{{\bf Z}}_{\geq 4}[ P(n) \mbox{$\Longrightarrow$}P(n+1)].$ It follows from the induction principle that for all $n \in \mbox{{\bf Z}}_{\geq 4}[ n! > 2^n].$  $\diamondsuit$