Information Technology Reference
In-Depth Information
of length 2
n
are
2
n
n
. Let us partition the
Proof.
The sequences
S
over
{
1
,−
1
}
sequences of
S
in the classes
S
0
,
n
, consists
of the sequences having
i
as maximum negative value of their partial sums. The
sequences that we want to count coincide with those of class
S
0
. These classes have
the same number of elements. In fact, we can transform, by means of a one-to-one
correspondence, the class
S
i
+
1
in the class
S
i
,for0
S
1
,
S
2
,...,
S
n
,where
S
i
,for0
≤
i
≤
≤
i
≤
n
. This transformation,
given a sequence of
S
i
+
1
, interchanges the value
−
1 of the position where the partial
sum
is reached with the value 1 of its next position (this value is necessarily
1). This means that
−
(
i
+
1
)
|
S
i
+
1
|
=
|
S
i
|
,for0
≤
i
≤
n
. Therefore,
|
S
i
|
=
|
S
|/
(
n
+
1
)
,for
0
n
, and in particular, for the set
S
0
whose cardinality we want to count, we
have that
≤
i
≤
|
S
0
|
=
|
S
|/
(
n
+
1
)
, that is, the number of our sequences is that one asserted
by the theorem.
7.4.3
Bernoulli Numbers
Jakob Bernoulli developed in his
Ars Conjectandi
a generalization of Faulhaber's
method for computing the sums of powers. He introduced an interesting sequence
of numbers,
B
(
i
)
with
i
0, which now are called Bernoulli numbers. He reported
proudly of having computed the sum of the first thousand tenth powers “intra semi-
quadrantem horae” (in seven minutes and a half).
Bernoulli numbers can be defined, by induction, in the following way.
>
Initial Step.
Let us consider the following equation:
B
2
2
B
1
B
2
−
+
1
=
that becomes:
2
B
1
=
1
by obtaining
B
1
2. This value is the first Bernoulli number
B
(
1
)
.
=
1
/
Induction Step.
For
i
>
1, consider the equation:
i
+
1
B
i
+
1
(
B
−
1
)
=
i
,powers
B
j
with the Bernoulli numbers
B
(
j
)
, computed at the
previous steps (power
B
i
+
1
disappears). The value of
B
i
resulting from the obtained
equation is the Bernoulli number
B
(
i
)
.
replace in it, for
j
<
Bernoulli proved the following theorem (see [218]).
Theorem 7.11 (Bernoulli's formula for the sums of powers).
The sum of powers
∑
i
=
1
,
n
i
k
−
1
is given by the following equation, where double curly brackets mean
that, after applying Newton's binomial formula, the powers B
i
have to be replaced
with the Bernoulli numbers B
(
i
)
.
