Mathematical Foundation of Computer Science

DHARM

18 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

recurrence relation only applies for n larger than the base cases. To study more about recursive
functions see chapter 3 section 3.5.

1.6 MATHEMATICAL INDUCTION AND PIANO’S AXIOMS

Induction is the mechanism for proving a statement about an infinite set of objects. In many
cases induction is done over set of natural numbers i.e., N = {0, 1, 2, 3.......}. However induction
method is equally valid over more general sets which have following properties,

• The set is partial ordered, which means an ordered relationship is defined between
  some pairs of elements of the set, and


• The set contains no infinite chain of decreasing elements.
  Using the principal of mathematical induction we can prove a collection of statements
  which can be put in one–to–one correspondence with the set of natural numbers. So in this
  section we shall examine the set of natural numbers and study the important properties or
  axioms of the set of natural numbers which leads us to formulate the principle of mathemati-
  cal induction.
  Let Ø the empty set. The set of natural numbers N can be generated by the starting with
  the empty set Ø and its successor sets Ø∪{Ø}, Ø∪{Ø}∪{Ø∪{Ø}}, Ø∪{Ø}∪{Ø∪{Ø}}
  ∪{Ø∪{Ø}∪{Ø∪{Ø}}}, .........These sets can be simplified to Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}},
  ..........If the set Ø be rename as 0 then {Ø} = 1, {Ø, {Ø}} = {0, 1}= 2, and {Ø, {Ø}, {Ø, {Ø}}} = {0,
  1, 2} = 3, .......so we obtain the set {0, 1, 2, 3, ...........} where each element is the successor set
  of the previous element except for the element 0 which is assumed to be present in the set.
  Thus we conclude that the set of natural numbers N can be obtained from the following axi-
  oms,


• 0 ∈ N


• If n ∈ N, then its successor, i.e. n ∪ {n} ∈ N.


• If a subset X ⊆ N follows the properties
  (i) 0 ∈ X, and
  (ii) if n ∈ X, then n ∪ {n} ∈ X
  then, X = N.
  These axioms are known as Peano axioms.
  Last property of the Peano axioms provides the basis of the principle of mathematical
  induction. This axiom can be expressed in an easy computational form as,
  Assume n is the induction variable. Let P(n) be any proposition defined for all n ∈ N and
  (i) If P(0) is true, (ii) If P(k) ⇒ P(k+1) or, its successor for any k ∈ N, then P(n) holds for all n
  ∈ N.
  For example let proposition P(n) be defined as

ii n n n

i

n

()/ ( )( )/+=++

=

∑^12126

1

Now show that P(n) is true for every n ≥ 0.

Basic Step

The proof is by induction on n, the upper limit of the sum. The base case is n = 0. We
must show that P(0) is true. Proposition P(0) is 0 = 0(0 + 1) (0 + 2) /6, which is obviously true.