704
Appendix
n
∑
k=1
(−1)
n−k
n
k
k
2
p
=
(
0, if 2p < n,
(2p −1)!! = if 1 ·3 ·5. ..(2p −1), for n = 2p.
(A.54)
n
∑
k=1
(−1)
n−k
n
k
k
q
p
=
(
0, if pq < n,
(pq)!
(q!)
p
p!
, for n = pq.
(A.55)
n
∑
k=1
(−1)
n−k
n
k
k
2
n/2
=
n!
2
n/2
for even n > 2. (A.56)
n−r
∑
k=0
(−2)
−k
n
r + k
n + r + k
k
= (−1)
(n−1)/2
2
r−n
n
n−r
2
. (A .57)
n
n
0
n
1
n
2
n
3
n
4
n
5
n
6
n
7
n
8
n
9
n
10
n
11
n
12
n
13
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
9 1 9 36 84 126 126 84 36 9 1
10 1 10 45 120 210 252 210 120 45 10 1
11 1 11 55 165 330 462 462 330 165 55 11 1
12 1 12 66 220 495 792 924 792 495 220 66 12 1
13 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
Inverse relations
a
n
=
∑
k
(−1)
k
n
k
b
k
, b
n
=
∑
k
(−1)
k
n
k
a
k
, (A.58)
a
n
=
∑
k
n
k
b
k
, b
n
=
∑
k
(−1)
n−k
n
k
a
k
, (A .59)
a
n
=
∑
k
k
n
b
k
, b
n
=
∑
k
(−1)
k−n
k
n
a
k
, (A .60)
a
n
=
⌊n/2⌋
∑
k=0
n
k
b
n−2k
, b
n
=
⌊n/2⌋
∑
k=0
(−1)
k
n
n −k
n −k
k
a
n−2k
, (A.61)
Appendix A: Binomial Coefficients
705
where b
0
= a
0
,
a
n
=
n
∑
k=0
2k
k
b
n−k
, b
n
=
n
∑
k=0
1
1 −2k
2k
k
a
n−k
, (A.62)
a
n
=
∑
k
n + p
k + p
b
k
, b
n
=
∑
k
(−1)
n+k
n + p
k + p
a
k
, (A.63)
a
n
=
∑
k
n
k
n
n−1−k
kb
k
, b
n
=
∑
k
(−1)
n+k
n
k
k
n−k
a
k
, (A.64)
a
n
=
∑
k
n + 2k
k
b
n+2k
, b
n
=
∑
k
(−1)
k
n + 2k
n + k
n + k
k
a
n+2k
. (A.65)
Finite Differences
∆
x
x
n
=
x
n −1
, ∆
x
n
x
=
n −1
x + 1
n
x
, (A .66)
∇
x
x
n
=
x −1
n −1
, ∇
x
n
x
=
n −2x + 1
n
n + 1
x
, (A.67)
∆
x
x
m
= m(x + 1)
m−1
, ∆
x
x
m
= mx
m−1
, (A.68)
∇
x
x
m
= mx
m−1
, ∇
x
x
m
= m(x −1)
m−1
, (A.69)
where ∆ is the forward finite difference operator and ∇ is the backward finite difference
operator:
∆ f (x) = f (x + 1) − f (x), ∇ f (x) = f (x) − f (x −1).
A generalized hypergeometric function
p
F
q
(a
1
,...,a
p
;b
1
,...,b
q
;x) is a function that can be
defined in the form of a hypergeometric series, i.e., a series for which the ratio of successive
terms can be written as
c
k+1
c
k
=
(k + a
1
)(k + a
2
)···(k + a
p
)
(k + b
1
)(k + b
2
)···(k + b
q
)
x
k + 1
.
(The factor of k + 1 in the denominator is present for historical reasons of notation.)
The function
2
F
1
(a,b;c; x) corresponding to p = 2, q = 1 is the most frequently used hyper-
geometric function, and so it is frequently known as the hypergeometric equation or hyper-
geometric series or, more explicitly, Gauss’s hypergeometric function (Gauss 1812). This
function is also commonly denoted as
2
F
1
(a,b;c; x) ≡ F
a,b
c
x
=
∑
k>0
a
k
b
k
c
k
x
k
k!
(A.70)
706
APPENDIX
Appendix B: T he Bernoulli Numbers
The Bernoulli numbers can be defined either through the exponential generating function
(L.33) or by the recurrence relation (M.12), which leads to
B
n
= −
1
n + 1
n−1
∑
k=0
n + 1
k
B
k
, n > 1, B
0
= 1. (B.1)
The Bernoulli numbers vanish for odd indices beyond 1: B
2k+1
= 0 for k > 1, and those with
even indices have alternating signs (see Table 581).
n 0 1 2 3 4 5 6 7 8 9 10 11 12
B
n
1 −1/2 1/6 0 −1/30 0 1/42 0 −1/30 0 5/66 0 −691/2730
The Appell polynomials over the sequence of the Bernoulli numbers are called the Bernoulli
polynomials:
B
n
(x) =
n
∑
k=0
n
k
B
k
x
n−k
, n > 0. (B.2)
The Bernoulli numbers, which are the values of the Bernoulli polynomials at x = 0 or x =
1, that is, B
n
= B
n
(0), n > 0 and B
n
= B
n
(1), n > 2, are known to have several explicit
representations:
B
n
=
n
∑
k=0
1
k + 1
k
∑
j=0
(−1)
j
k
j
j
n
=
n
2
n
−1
n−1
∑
k=1
(−1)
k+1
k!
2
k+1
n −1
k
, n > 0, B
0
= 1. (B.3)
B
2m
=
m
∑
i=1
(−1)
i−1
m!(m + 1)!
i(i + 1)(m −i)!(m + i + 1)!
i
∑
k=1
k
2m
for each positive integer m. (B.4)
The first ten Bernoulli polynomials and Bernoulli numbers are presented in Table 581.
The Bernoulli polynomials satisfy the following relations:
d
dx
B
n
(x) = nB
n−1
(x),
d
k
dx
k
B
n
(x) = k!
n
k
B
n−k
(x). (B.5)
Z
y
x
B
n
(t)dt =
B
n+1
(y) −B
n+1
(x)
n + 1
,
Z
x+1
x
B
n
(t)dt = x
n
, n > 1. (B.6)
Symmetry relation:
B
n
(1 −x) = (−1)
n
B
n
(x), n > 0. (B.7)
Addition formula:
B
n
(x + y) =
n
∑
k=0
n
k
B
k
(y)x
n−k
, n > 0. (B.8)
Appendix B: The Bernoulli Numbers
707
Raabe’s multiplication formula:
B
n
(mx) = m
n−1
m−1
∑
k=0
B
n
x +
k
m
, n > 0, m > 1. (B.9)
The binomial convolutions, attributed to L. Euler:
n
∑
k=0
n
k
B
k
(
α
)B
n−k
(
β
) = n(
α
+
β
−1)B
n−1
(
α
+
β
) −(n −1)B
n
(
α
+
β
). (B.10)
n
∑
k=0
n
k
B
k
B
n−k
= −nB
n−1
−(n −1)B
n
, n > 1. (B.11)
Fourier series:
B
n
(x) = −
n!
(2
π
i)
n
∞
∑
k=−∞
k
−n
e
2
π
ikx
(0 < x < 1). (B.12)
The sums Φ
m
(n) =
∑
n
k=1
k
m
are expressed via the Bernoulli numbers:
n
∑
k=1
k
m
=
m+1
∑
j=1
m
j −1
B
m+1−j
j
=
m
∑
k=0
m
k
(n + 1)
m+1−k
m + 1 −k
B
k
=
1
m + 1
m
∑
k=0
m + 1
k
(n + 1)
m−k+1
B
k
, (B.13)
or more succinctly via the Bernoulli polynomials:
n
∑
k=1
k
m
=
1
m + 1
[B
m+1
(n + 1) −B
m+1
(1)]. (B.14)
n
∑
k=1
(a + bk)
p
=
b
p
p + 1
[B
p+1
(n + 1 + a/b) −B
p+1
(a/b)], p > 1, n > 0. (B.15)
Asymptotics
Since the zeta function,
ζ
(s) =
∑
k>1
k
−s
, can be expressed via Bernoulli numbers for even
integer values as
ζ
(2n) =
∞
∑
k=1
1
k
2n
= (−1)
n−1
(2
π
)
2n
2(2n)!
B
2n
∼1, as n → ∞ , (B .16)
we get the following approximations:
B
2n
∼ (−1)
n+1
2
(2n)!
(2
π
)
2n
,
(2
π
)
n
2(n)!
B
n
(x) ∼ cos
2
π
x +
π
+
n
π
2
, n → ∞ . (B.17)
Get Methods in Algorithmic Analysis now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
