Information Technology Reference
In-Depth Information
After the presentation of this argument, William Dunham [178] concludes by
saying: ”Surely this established that Euler's train of thought had not derailed. If this
argument could recover previously known results such as this, there seemed all the
more reason to embrace his initial conclusion.” (the infinite product representation
of sin
x
x
,
Euler, Introduction to Analysis of the Infinite, Book I, pp. 154-155
)
1
.
/
5.5
Induction and Recurrence
Natural numbers are generated by means of the basic counting process. In fact, we
start from an initial number, called zero, and then by applying the successor opera-
tion, at each step, we get a new number from the last one previously generated. Apart
from the specific manners to identify the elements of this sequence, the essence of
this (infinite) process is the combination of
zero
and
successor
. A definition of nat-
ural number which expresses this perspective is due to the Italian mathematician
Giuseppe Peano at the beginning of the last century:
zero is a number, and the suc-
cessor of any number is a number too
. We remark that the successor operation is
always defined and its result applied to a number
n
is always different from all the
numbers from zero to
n
in the generation process. This structure characterizes the
set
of the natural numbers and is the essence of the
mathematical induction
,a
very powerful method for proving and defining properties of natural numbers. The
explicit and formal identification of the principle of induction was given by Peano,
but it was used, in an implicit or intuitive manner, by many mathematicians be-
fore Peano (primitive forms of induction are present in Greek mathematics) such
as: Maurolico, Tartaglia, Pascal, and Dedekind. The name induction seems to be
a little misleading, because it suggests an analogy to the process of inferring gen-
eral properties from particular cases. However, this connection is not completely
wrong. In fact, the primitive forms of induction emerge when some properties are
verified in some specific numerical cases, but a pattern occurs which is not specific
to single cases, because it follows a common general schema. The principle of in-
duction claims that in order to prove or to define a property
P
over
N
N
it is sufficient
to provide:
Ta b l e 5 . 8
The
initial step
and the
induction step
of an induction schema
i) The proof or definition of
P
(
0
)
(validity or definition of
P
for zero)
ii) The proof or definition of
P
(
n
+
1
)
by assuming that
P
(
n
)
holds or is defined (
n
generic).
1
Another famous Euler's jewel, related to Riemann's zeta function on the distribution of
prime numbers, is the so called sum-product formula
p
k
=
∏
p
∈
P
∑
k
∈
N
1
,where
P
is the
p
−
set of prime numbers.
