Information Technology Reference
In-Depth Information
if we reformulate the previous schema in a logical form where an arrow denotes the
proof consequence and
is the universal quantification asserting the validity of a
proposition for all the values of the variable it refers to.
∀
Ta b l e 5 . 9
Proof by induction of
∀
n
∈
N
P
(
n
)
i)
)
ii)
∀
n
∈
N
P
(
0
P
(
n
)
⇒
P
(
n
+
1
)
The above induction proof is of a completely new kind with respect to the well-
known traditional geometric proof of Greek mathematics, developed in the context
of
figurate numbers
. For the sake of completeness, we want to mention it. Consider
an arrangement of
n
2
balls forming a square of side
n
. This arrangement can be
constructed by putting an initial ball and then by surrounding it by three other balls.
In general, for passing from a square to the next square, that is from
n
2
2
,
you need to add a row of
n
balls, a column of
n
balls and a further common ball
extending the added row and column. Therefore, 2
n
to
(
n
+
1
)
+
1 is the whole number of
balls for passing from
n
2
2
. This means that in general a square of
n
2
balls is obtained by increasingly arranging
n
odd numbers of balls which extend the
square sides. Table 5.10 shows the construction of a square of 9 objects, according
to the outlined procedure. The following interesting proposition, due to the Greek
mathematician Nichomachus, has a very simple proof by induction.
to
(
n
+
1
)
Ta b l e 5 . 1 0
The construction of a square of 9 objects by arranging 1
+
3
+
5 objects
∗
o
∗
o
∗∗ → ∗ ∗
Proposition 5.1 (Nichomachus' Theorem)
n
i
=
1
i
2
n
i
=
1
i
3
=
Proof.
(Proof by induction) The initial step is evident. The induction step is estab-
lished by the following identities (where the passage from the last but one equation
follows by induction hypothesis and by the identity 1
+
2
+
...
n
=
n
(
n
+
1
)
/
2, which
will be proved in a next section (Sect. 5.6.1, Eq. (5.3)):
