Natural numbers and mathematical induction

Natural numbers and mathematical induction


	Natural numbers and mathematical induction

Calculus takes its origin in the properties of natural numbers,

$\begin{displaymath} {\rm N} = \{0,\;1,\;2,\;\dots \}. \end{displaymath}$

The formal definition of natural numbers

${\rm N}$

is based on

Peano axioms.

A set A of elements is called natural numbers if it possesses the following properties.

i.

Every element

$a\in A$

has an element that is called successor and denoted by

ii.

Elements

$a,b \in A$

and

$a\not= b$

have different successors,

$a+1 \not= b + 1.$

iii.

There is an element in A that is not a successor of any element from A. This special element is denoted by "0"

iv.

If a logical statement

$S(a)$

is trues for

and

implies that

then

$\begin{displaymath} S(a)=true \;\;\;\; \forall\;\;a\in A. \end{displaymath}$

The history of natural numbers is outlined in

http://en.wikipedia.org/wiki/Natural_number

Notice that the last Piano axiom justifies the widely known principle of

Mathematical Induction.

i.

(Basis) The statement

is true for

ii.

(Inductive step) If (induction hypothesis )

$\begin{displaymath} S(n)=true \end{displaymath}$

then

$\begin{displaymath} S(n+1)=true. \end{displaymath}$

If it is possible for a statement

to prove items (i.) and (ii.) then

for any

$n\in {\rm N}.$

Let us illustrate the principle of mathematical induction by the following example.

Example .

Our goal is to use mathematical induction in order to prove that

$\begin{displaymath} \forall \;\; n \in {\rm N} \;\;\;1+2+3+\dots + n = \frac{n\cdot (n+1)}{2} \end{displaymath}$

The statement

$\begin{displaymath} 1+2+3+\dots + n = \frac{n\cdot (n+1)}{2} \end{displaymath}$

We need to show that

$\begin{displaymath} \forall \;\; n \in {\rm N} \;\;\;S(n)=true. \end{displaymath}$

In order to conduct our proof by means of mathematical induction we need to show first that

for

Basis. One can see that

means

$\begin{displaymath} 0=\frac{0 \cdot (0+1)}{2} \end{displaymath}$

and it is a valid statement. That means we have shown that

Inductive step. Suppose (induction hypothesis ) that

which means

$\begin{displaymath} 1+2+3+\dots + n = \frac{n\cdot (n+1)}{2} \end{displaymath}$

(1)

is valid.

Our goal is to show that

as well. That means we need to prove that

$\begin{displaymath} 1+2+3+\dots + n + (n+1) = \frac{(n+1) \cdot ((n+1)+1)}{2} \end{displaymath}$

is true.

After adding

to the left and right hand sides of (1) we obtain

$\begin{displaymath} 1+2+3+\dots + n +(n+1) = (n+1)+ \frac{n\cdot (n+1)}{2} \end{displaymath}$

(2)

Since

$\begin{displaymath} \frac{n\cdot (n+1)}{2} + (n+1) = \frac{(n+1) \cdot ((n+1)+1)}{2} \end{displaymath}$

the statement (1) implies (2) and in accordance with mathematical induction we have proved that

$\begin{displaymath} 1+2+3+\dots + n = \frac{n\cdot (n+1)}{2} \end{displaymath}$

is valid for all

$n\in {\rm N}.$

Definition 1

(Prime number) A natural number

$p \in {\rm N} \;\;(p\not= 0)$

is called prime if it is devisable without remainder only by

and itself, p.

Prime numbers occupy a special prominent place among all natural numbers. Any natural number can be build in certain unique way out of prime numbers. In more precise terms, the following theorem holds.

Theorem 1.1

For any natural number

$n \in {\rm N }$

such that

$n \not= 0$

there exist a finite set of prime numbers

$\begin{displaymath} p_1 < p_2 < \dots < p_m \end{displaymath}$

such that

$\begin{displaymath} n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots p_m^{\alpha_m}, \end{displaymath}$

(3)

where

$\begin{displaymath} \alpha_1, \; \alpha_2, \; \dots \alpha_m \end{displaymath}$

are integers. Moreover, the representation (3) is unique.

The proof of this theorem is left for reader as an exercise. Hint, use mathematical induction.

Next:ExercisesUp:realNumbersPrevious:realNumbers

Sergey Nikitin 2005-08-28