Information Technology Reference
In-Depth Information
Induction is strictly related to two other notions:
iteration
and
recurrence
.It-
eration is a special case of induction obtained by applying an operation a num-
ber of times, and at each step to the result of its previous application. This notion
can be formally defined by means of a sort of exponentiation, as it is expressed in
Tab le 5 . 1 9.
Ta b l e 5 . 1 9
The inductive definition of iteration
f
0
(
x
)=
x
f
n
+
1
(
x
)=
f
(
f
n
(
x
))
For example, the iteration of the successor function
s
of exponent 3 and argument
4is:
s
3
s
2
s
1
s
0
(
4
)=
s
(
(
4
)) =
s
(
s
(
(
4
))) =
s
(
s
(
s
(
(
4
)))) =
s
(
s
(
s
(
4
))) =
7
.
5.5.1
Fibonacci Sequence
Recurrence is a form of induction where a function is defined on natural numbers
by starting from some initial values, and then by defining the values of the function
in terms of some of the values it takes on smaller arguments.
One of the most famous examples of recurrent definition is the following, due
to Leonardo Fibonacci (Leonardo Pisano) and presented in his famous
Liber Abaci
(1202 A.D.), whereby the Indo-Arabic positional notation for numbers was intro-
duced in Europe:
Ta b l e 5 . 2 0
The recurrent definition of Fibonacci sequence
F
(
1
)=
F
(
2
)=
1
F
(
n
+
)=
F
(
n
+
)+
F
(
n
)
2
1
Ta b l e 5 . 2 1
The first eight values of Fibonacci sequence
F
(
1
)=
1
,
F
(
2
)=
1
,
F
(
3
)=
2
,
F
(
4
)=
3
,
F
(
5
)=
5
,
F
(
6
)=
8
,
F
(
7
)=
13
,
F
(
8
)=
21
√
5
2.
In fact, for increasing values of the sequence, the ratio between a Fibonacci number
and its predecessor approximates to
The Fibonacci sequence is strictly related to the
golden ratio
φ
=(
1
+
)
/
φ
.
