Axioms (Peano’s Postulates). The natural numbers are defined as a set N\mathbb{N} together with a unary “successor” function S:N→NS : \mathbb{N} \to \mathbb{N} and a special element 1∈N1 \in \mathbb{N} satisfying the following postulates:

I. 1∈N1 \in \mathbb{N}.

II. If n∈Nn \in \mathbb{N}, then S(n)∈NS(n) \in \mathbb{N}.

III. There is no n∈Nn \in \mathbb{N} such that S(n)=1S(n) = 1.

IV. If n,m∈Nn, m \in \mathbb{N} and S(n)=S(m)S(n) = S(m), then n=mn = m.

V. If A⊂NA \subset \mathbb{N} is a subset satisfying the two properties:

  • 1∈A1 \in A
  • if n∈An \in A, then S(n)∈AS(n) \in A,
    then A=NA = \mathbb{N}.

Theorem (Mathematical Induction). For each n∈Nn \in \mathbb{N}, let P(n)P(n) be a proposition. Suppose the following two results:

(A) P(1)P(1) is true.

(B) If P(n)P(n) is true, then P(S(n))P(S(n)) is true.

Then P(n)P(n) is true for all n∈Nn \in \mathbb{N}.

Statement (A) is called the base case and statement (B) is called the inductive step. The assumption that PP is true of nn is called the inductive hypothesis.

  1. Prove that for all positive integers nn,
12+22+32+⋯+n2=n(2n+1)(n+1)6. 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(2n+1)(n+1)}{6}.

Proof:

For each n∈Nn\in \mathbb{N}, Let P(n)P(n) be a supposition that 12+22+32+⋯+n2=n(2n+1)(n+1)61^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(2n+1)(n+1)}{6}
When n=1n=1, 12=1(2⋅1+1)(1+1)6=11^2=\frac{1(2\cdot1+1)(1+1)}{6}=1   ⟹  P(1)\implies P(1) is true

Suppose P(n)P(n) is true:

Since 12+22+32⋯+(n+1)2=(12+22+32⋯+n2)+(n+1)21^2+2^2+3^2\dots+(n+1)^2=(1^2+2^2+3^2\dots+n^2)+(n+1)^2
Replace 12+22+32+⋯+n21^2 + 2^2 + 3^2 + \cdots + n^2 with n(2n+1)(n+1)6\frac{n(2n+1)(n+1)}{6}
Then12+22+32⋯+(n+1)2=(12+22+32⋯+n2)+(n+1)2=n(2n+1)(n+1)6+(n+1)2=(n+1)(2n2+7n+66)=(n+1)(2n+3)(n+2)61^2+2^2+3^2\dots+(n+1)^2=(1^2+2^2+3^2\dots+n^2)+(n+1)^2=\frac{n(2n+1)(n+1)}{6}+(n+1)^2=(n+1)\left(\frac{2n^2+7n+6}{6} \right)=\frac{(n+1)(2n+3)(n+2)}{6}
P(n+1)P(n+1) holds.

Thus, by mathematical induction, P(n)P(n) holds for all n∈Nn \in \mathbb{N} ∎

  1. Prove that if n≥4n \geq 4, then n2≤2nn^2 \leq 2^n.

Proof:

Let P(n)P(n) be the proposition that n2≤2nn^2 \leq 2^n for all n≥4n\geq4.
When n=4n=4, 42=244^2=2^4. P(4)P(4) holds.

Suppose P(n)P(n) holds i.e. n2≤2nn^2\leq2^n
(n+1)2=n2+2n+1≤2n+2n+1<2n+2n=2n+1(n+1)^2=n^2+2n+1\leq2^n+2n+1<2^n+2^n=2^{n+1} ,(n≥4,2n+1≤n2)(n\geq4,2n+1\leq n^2)
i.e. P(n+1)P(n+1) holds.

Thus, by mathematical induction, P(n)P(n) holds for each n∈Nn\in \mathbb{N}∎

  1. Prove Bernoulli’s Inequality:

    If 1+x>0, then (1+x)n≥1+nx for any n∈N.\text{If } 1 + x > 0, \text{ then } (1 + x)^n \geq 1 + nx \text{ for any } n \in \mathbb{N}.

Proof:

let P(n)P(n) be the proposistion that If 1+x>0, then (1+x)n≥1+nx\text{If } 1 + x > 0, \text{ then } (1 + x)^n \geq 1 + nx, for all n∈N.n\in \mathbb{N}.

When n=1n=1, 1+x≥1+x1+x\geq1+x, P(1)P(1) holds.

Suppose P(n)P(n) is true i.e. If 1+x>0, then (1+x)n≥1+nx\text{If } 1 + x > 0, \text{ then } (1 + x)^n \geq 1 + nx
Then (1+x)n+1=(1+x)n(1+x)≥(1+nx)(1+x)=1+(n+1)x+nx2>1+(n+1)x(1+x)^{n+1}=(1+x)^n(1+x)\geq(1+nx)(1+x)=1+(n+1)x+nx^2>1+(n+1)x
i.e. P(n+1)P(n+1) is true.

Thus, by mathematical induction, P(n)P(n) is true for all n∈Nn\in \mathbb{N}.∎

  1. Prove the theorem.

Proof:

Suppose that (A) P(1)P(1) is true, and (B) If P(n)P(n) is true, then P(S(n))P(S(n)) is true.

Noticing that the condition we have and what we want to prove has similar form with axiom V, we consider constructing a subset A∈NA\in \mathbb{N} and prove A=NA=\mathbb{N}:

Let set A={n∈N∣ P(n) is true }⊂NA=\{ n\in \mathbb{N}| \ P(n) \text{ is true }\}\subset \mathbb{N}

Given that:

- 1∈A1\in A by (A)
- if n∈An\in A , then S(n)∈AS(n) \in A by (B)

By Axiom V, A=NA=\mathbb{N}. i.e. P(n)P(n) is true for all n∈Nn\in \mathbb{N}

Thus, if (A) and (B) hold, then P(n)P(n) is true for all n∈Nn \in \mathbb{N}.∎