Information Technology Reference
In-Depth Information
Proof.
(by induction). Let
n
i
=
1
i
k
S
k
(
n
)=
If
k
=
1, then
S
k
(
n
)=
T
(
n
)=
n
(
n
+
1
)
/
2 and the statement of the theorem holds.
Assume that a polynomial of degree
(
k
−
1
)
was determined such that:
i
k
S
k
−
1
(
i
)=
/
k
+
P
k
−
1
(
i
)
(5.7)
then, we can put:
n
−
1
i
=
1
S
k
−
1
(
i
)=
n
−
1
i
=
1
i
k
n
−
1
i
=
1
P
k
−
1
(
i
)
/
k
+
therefore:
n
−
1
i
=
1
S
k
−
1
(
i
)=
S
k
(
k
+
n
Q
k
(
n
−
1
)
(5.8)
where
Q
k
(
is, by induction hy-
pothesis, a polynomial of variable
n
having degree
k
. On the other hand, the sum
∑
n
−
1
)=
P
k
−
1
(
n
−
1
)+
P
k
−
1
(
n
−
2
)+
...
P
k
−
1
(
1
)
n
−
1
1
S
k
−
1
(
i
)
can be put in the following way:
i
=
1
+
2
k
−
1
1
+
2
k
−
1
3
k
−
1
+
+
+
+
...
+
1
.
.
.
.
2
k
−
1
3
k
−
1
k
−
1
+
1
+
+
+
...
+(
n
−
2
)
2
k
−
1
3
k
−
1
k
−
1
k
−
1
+
1
+
+
+
...
+(
n
−
2
)
+(
n
−
1
)
or equivalently:
1
k
−
1
2
k
−
1
3
k
−
1
k
−
1
(
n
−
1
)
+(
n
−
2
)
+(
n
−
3
)
+
...
+[
n
−
(
n
−
1
)](
n
−
1
)
which is the difference of two terms:
⎧
⎨
n
1
k
−
1
n
2
k
−
1
n
3
k
−
1
+
+
+
...
=
nS
k
−
1
(
n
−
1
)
⎩
1
k
2
k
3
k
+
+
+
...
=
S
k
(
n
−
1
)
In conclusion:
n
−
1
i
=
1
S
k
−
1
(
i
)=
nS
k
−
1
(
n
−
1
)
−
S
k
(
n
−
1
)
(5.9)
and if we equate the right members of Eqs. (5.8) and (5.9), we get:
S
k
(
k
+
n
nS
k
−
1
(
n
−
1
)
−
S
k
(
n
−
1
)=
Q
k
(
n
−
1
)
that is:
