Information Technology Reference
In-Depth Information
2
2
2
(
1
+
2
+
...
n
+(
n
+
1
))
=(
1
+
2
+
...
n
)
+(
n
+
1
)
+
2
(
1
+
2
+
...
n
)(
n
+
1
)=
1
3
2
3
n
3
2
+
+
...
+(
n
+
1
)
+
n
(
n
+
1
)(
n
+
1
)=
1
3
2
3
n
3
2
1
3
2
3
3
+
+
...
+(
+
)
(
+
)=
+
+
...
(
+
)
.
n
1
n
1
n
1
Tables 5.11, 5.12, 5.13, and 5.14 respectively display classical definitions by induc-
tion (on the variable
n
) of the arithmetical sum, product, exponential, and factorial
operations. These definitions have two equations, the first one for the initial case,
while in the second one the left member provides the definition of the operation
by assuming, by induction hypothesis, that the right member is already defined for
smaller values of the variable. In the definition of product, the definition of sum is
assumed, and, in the definition of exponentiation, the definition of product is as-
sumed. They can be proved to be correct (they define the expected operations) by
using the induction principle.
Ta b l e 5 . 1 1
The inductive definition of sum
n
+
0
=
n
m
+(
n
+
1
)=(
m
+
n
)+
1
Ta b l e 5 . 1 2
The inductive definition of product
n
∗
0
=
0
m
∗
(
n
+
1
)=(
m
∗
n
)+
m
Ta b l e 5 . 1 3
The inductive definition of exponentiation
m
0
=
1
m
n
+
1
m
n
=
∗
m
Ta b l e 5 . 1 4
The inductive definition of factorial
n
! (the product of all the numbers equal to or
lower than
n
)
=
0!
1
(
n
+
1
)
!
=
n
!
∗
(
n
+
1
)
The definition in Table 5.15 characterizes the property of prime numbers by in-
duction (a prime number is greater than 1 and has no divisor different from itself).
