Peano’s Induction Principle - Induction

Mathematical Writing - Vivaldi Franco 2014

Peano’s Induction Principle
Induction

This is a third form of mathematical induction; it was proposed by Dedekind6 and formalised by Peano. The principle of induction states that:

($$C$$)

If $${\fancyscript{P}}$$ is a predicate over $$\mathbb {N}$$ such that

$$ \mathrm{i)}\quad {\fancyscript{P}}(1) \quad \textit{is true;} \qquad \mathrm{ii)}\quad \forall k\in \mathbb {N},\quad {\fancyscript{P}}(k)\Rightarrow {\fancyscript{P}}(k+1); $$

then $${\fancyscript{P}}(n)$$ is true for all $$n\in \mathbb {N}$$.

The first condition is called the basis of the induction (or the base case); the second the inductive step. The bi-unique correspondence between predicates $$\fancyscript{P}$$ over $$\mathbb {N}$$ and subsets $$S$$ of $$\mathbb {N}$$, given by [see Eqs. (4.15 and 4.16)]

$$ S=\{n\in \mathbb {N}\,:\, {\fancyscript{P}}_S(n)\}, \qquad {\fancyscript{P}}_S(x)=(x\in S) $$

allows us to reformulate the induction principle in the language of sets.

($$C^\prime $$)

If $$S$$ is a subset of $$\mathbb {N}$$ such that

$$ \mathrm{i)}\quad 1\in S; \qquad \mathrm{ii)}\quad \forall k\in \mathbb {N},\quad k\in S \Rightarrow (k+1)\in S; $$

then $$S=\mathbb {N}$$.

The principle of induction follows from well-ordering ($$(A)\Rightarrow (C)$$). To show this, we define the set

$$ S^{\,\prime }=\mathbb {N}{\backslash }S\,=\,\{n\in \mathbb {N}\,:\, \lnot {\fancyscript{P}}(n)\}. $$

We prove that $$S^{\,\prime }$$ is empty by contradiction. If $$S^{\,\prime }$$ is non-empty, then, by the well-ordering axiom, $$S^{\,\prime }$$ has a least element $$k$$. Since $$1\in S$$, we have $$k\not =1$$, and since $$k$$ is the smallest element of $$S^{\,\prime }$$, it follows that $$k-1\in S$$. Then, putting $$j=k-1$$, we find from condition ii) that $$j+1=k\in S$$, which contradicts the fact that $$k\in S^{\,\prime }$$.

The base case of Peano’s induction could be any integer, not just 1. Indeed if $${\fancyscript{P}}(n)$$ is valid for all $$n\geqslant k$$, then by letting $$m=n-k+1$$, the range $$n\geqslant k$$ becomes $$m\geqslant 1$$.

Peano’s induction provides straightforward proofs of finite sums and products formulae:

$$\begin{aligned} \forall n\in \mathbb {N},&\sum _{j=1}^na_j =F(n) \end{aligned}$$

(8.2)

$$\begin{aligned} \forall n\in \mathbb {N},&\prod _{j=1}^na_j =G(n) \end{aligned}$$

(8.3)

where $$(a_j)$$ is a sequence of numbers (or more generally of elements of a commutative ring), and $$F$$ and $$G$$ are explicit functions of $$n$$, hopefully easier to compute than the original sum or product.

In an inductive proof of (8.2), the base case consists of verifying that $$a_1=F(1)$$. For the inductive step, we assume that the formula holds for some $$n=k$$, and using the induction hypothesis we obtain:

$$ \sum _{j=1}^{k+1}a_j=\sum _{j=1}^ka_j+a_{k+1}=F(k)+a_{k+1}. $$

Thus the proof reduces to the verification of the statements

$$\begin{aligned} a_1=F(1),\qquad F(k)+a_{k+1}=F(k+1)\quad k\geqslant 1 \end{aligned}$$

(8.4)

which no longer involve summation. For example, to prove the formula

$$ \sum _{j=1}^n j^2 =\frac{n(n+1)(2n+1)}{6} \qquad n=1,2,\ldots $$

we must verify that

$$ 1^1=\frac{1\cdot 2\cdot 3}{6},\qquad \frac{k(k+1)(2k+1)}{6}+(k+1)^2=\frac{(k+1)(k+2)(2k+3)}{6}. $$

For a product formula, the expressions (8.4) are replaced by

$$\begin{aligned} a_1=G(1),\qquad G(k)\times a_{k+1}=G(k+1)\quad k\geqslant 1. \end{aligned}$$

(8.5)

In some cases the identities (8.4) and (8.5) may be established using a computer algebra system. This is an instance of computer-assisted proof 7—see Exercise 8.1.

A similar arrangement applies to the inductive proof of inequalities. However, even in the simplest cases, such proofs are not as mechanical as those of summation and product formulae, as the following example illustrates.

Proposition

If $$n > 3$$, then $$2^n \geqslant n^2$$.

PROOF. We prove it by induction on $$n$$. The base case $$n = 4$$ is immediate: $$2^4 \geqslant 4^2$$. Assume now that for some $$k\geqslant 4$$ we have $$2^k\geqslant k^2$$. Then

$$ 2^{k+1}=2\cdot 2^k \geqslant 2\cdot k^2 $$

where the inequality follows from the induction hypothesis. To complete the proof, we must show that for all $$k\geqslant 4$$ we have $$2\cdot k^2\geqslant (k+1)^2$$. Now the polynomial

$$ p(k)=2\cdot k^2-(k+1)^2=k^2-2k-1 $$

has roots $$1\pm \sqrt{2}$$, with

$$ -1 < 1-\sqrt{2} < 1+\sqrt{2} < 3. $$

Thus, for $$k\geqslant 3$$, we have $$p(k)>0$$, or $$2k^2 > (k+1)^2$$. Hence $$2^{k+1}\geqslant (k+1)^2$$, completing the induction. $$\square $$

The next example warns us that a straightforward inductive strategy doesn’t always work.

Proposition

For all integers $$n\geqslant 0$$ and real numbers $$x > -1$$, we have

$$\begin{aligned} (1+x)^n > nx. \end{aligned}$$

(8.6)

We attempt to prove this by induction on $$n$$.

Base case: $$n = 0$$. Since $$x>-1$$, we have $$(1+x)^0 = 1 > 0 = 0x$$, as desired.

Inductive step: Assume (8.6) for some $$n = k\geqslant 0$$. Then

$$ \begin{array}{rcl} (1 + x)^{k+1} &{} = &{} (1+x)(1+x)^k\\ &{} > &{} (1+x)kx \quad \text { (by induction hypothesis) }\\ &{} = &{} kx + kx^2\quad \text {???} \end{array} $$

We don’t seem to be getting anywhere.

PROOF. We prove the stronger inequality $$(1+x)^n \geqslant 1+ nx$$. This is the Bernoulli inequality—see p. 139. Base case: $$n = 0$$. Since $$x>-1$$, we have $$(1+x)^0 = 1 \geqslant 1 + 0x$$.Inductive step: Assume the inequality for $$n = k\geqslant 0$$. Then

$$ \begin{array}{rcl} (1 + x)^{k+1} &{} = &{} (1+x)(1+x)^k \\ &{} \geqslant &{} (1+x)(1 + kx)\quad \text { (by induction hypothesis) }\\ &{} = &{} 1 + (k+1)x + kx^2 \geqslant 1 + (k+1)x. \end{array} $$

The inductive step is complete. $$\square $$