Information Technology Reference
In-Depth Information
This schema can be easily changed and extended in many ways. For example, if
we want to prove
P
only for all the numbers greater than or equal to
k
, it applies
by just taking
k
instead of zero (the property in question is not exactly
P
(
n
)
,but
(
+
)
P
n
k
for all values of
n
). In other cases it is more convenient to prove or define
(
+
)
(
)
≤
P
n
. Or, more generally,
what we want to prove or to define is not directly related to natural numbers, but
to a sequence
S
0
n
1
by assuming that
P
j
holds or is defined for all
j
of structures indexed by natural numbers. In this case the
initial step applies to
S
0
and the induction step proves or defines something for
S
n
+
1
by assuming it holds or is defined for the structure
S
n
(or for all structures
with indexes smaller than
n
,
S
1
,...
1). In the literature there are many methods indicating
different schemas of induction; however, they are all consequences of the basic form
considered above. Often, the numerical variable used in the schema of induction (
n
in our formulation) is called the induction variable, and a proof or definition by
induction is said to be developed
over the variable n
.
Given a quite obvious validity of the induction, it is surprising that its generality
was discovered in relatively recent times. Moreover, despite its simplicity, very often
induction proofs and definitions are not so easy to be correctly developed and their
construction and analysis requires a good mathematical maturity.
We provide an initial example of proof by induction, due to Maurolico, of the
fact that
n
2
is the sum of the first
n
odd numbers:
+
n
i
=
1
(
2
i
−
1
)
.
n
2
=
(5.1)
The initial step trivially holds. For the induction step, we need to prove the following
equation, by assuming the previous one:
n
1
i
=
1
(
2
i
−
1
)
.
+
2
(
+
)
=
n
1
In fact,
2
n
2
1
but, for the induction hypothesis, we can replace
n
2
by the right member of Eq. (5.1),
thereby obtaining the same equation instantiated at the value
n
(
n
+
1
)
=
+
2
n
+
+
1, as required by
the induction step:
n
+
1
i
=
1
(
2
i
−
1
)
.
The above example shows a peculiarity of induction, that is, a sort of tautological
flavor, which is intrinsic to the induction schema. In fact, it seems that we use in
the proof the same claim we want to prove. This impression is related to the basic
mechanism of the induction step, where essentially an hypothetical statement is
transformed into a universal statement. This phenomenon is more clearly apparent
n
i
=
1
(
2
i
−
1
)+(
2
n
+
1
)=
2
(
n
+
1
)
=
