Power Sums of Binomial Coefficients

Askar Dzhumadil’daev and Damir Yeliussizov Kazakh-British Technical University 59 Tole bi St 050000 Almaty Kazakhstan

                      dzhuma@hotmail.com
                      yeldamir@gmail.com

Abstract We establish an analog of Faulhaber’s theorem for a power sum of binomial coefficients. We study reciprocal power sums of binomial coefficients and Faulhaber coefficients for a power sum of triangular numbers.

1 Introduction

While the sum of powers of consecutive nonnegative integers was studied by many mathematicians from ancient times, two names should be especially mentioned: Jacob Bernoulli (1654-1705) and Johann Faulhaber (1580-1635). It is well known that

∑_{i=1}^{n} i = \frac{n^{2}}{2} + \frac{n}{2} = \frac{n(n + 1)}{2},

∑_{i=1}^{n} i^{2} = \frac{n^{3}}{3} + \frac{n^{2}}{2} + \frac{n}{6} = \frac{n(n + 1)(2n + 1)}{6},

∑_{i=1}^{n} i^{3} = \frac{n^{4}}{4} + \frac{n^{3}}{2} + \frac{n^{2}}{4} = (\frac{n(n + 1)}{2})^{2} .

In general,

∑_{i=1}^{N−1} i^{m} = \frac{1}{m + 1} ∑_{i=0}^{m} \binom{m + 1}{i}B_{i}N^{m+1−i},

where B_{i} are Bernoulli numbers.

Faulhaber [2, 5] noticed that odd power sums can be represented as a polynomial in t = n(n + 1)/2. For example,

∑_{i=1}^{n} i^{3} = t^{2},

∑_{i=1}^{n} i^{5} = \frac{4t^{3} − t^{2}}{3} ,

∑_{i=1}^{n} i^{7} = \frac{12t^{4} − 8t^{3} + 2t^{2}}{6} .

He computed these sums up to degree 17. The first proof of Faulhaber’s theorem was given by Jacobi [4]. The general formula for odd power sums can be written as

∑_{i=1}^{n} i^{2p+1} = \frac{1}{2^{2p+2}(2p + 2)} ∑_{i=0}^{p} \binom{2p + 2}{2i}(2 − 2^{2i})B_{2i}((8t + 1)^{p+1−i} − 1).

Faulhaber knew that odd power sums are divisible by t^{2} and even power sums can be expressed in terms of odd power sums. If

∑_{i=1}^{n} i^{2p+1} = c_{1}t^{2} + c_{2}t^{3} + ⋯ + c_{p}t^{p+1},

then

∑_{i=1}^{n} i^{2p} = \frac{2n + 1}{2(2p + 1)}(2c_{1}t + 3c_{2}t^{2} + ⋯ + (p + 1)c_{p}t^{p}).

In our paper we consider the power sum of binomial coefficients

f_{k,m}(N) = ∑_{i=0}^{N−1} \binom{i + k − 1}{k}^{m},

and for k = 1 we obtain the usual power sum

f_{1,m}(N) = ∑_{i=1}^{N−1} i^{m}.

We establish an analog of Faulhaber’s theorem for any positive integer k. Namely, we show that:

• f_{k,m}(N) is a polynomial in N and it can therefore be considered as a polynomial f_{k,m}(x) in any variable x;

• f_{k,m}(x) can be expressed as:

\binom{x+k−1}{k+1}^{2}Q_{k,m}((2x + k − 2)^{2}), if m, k are odd and m > 1;

\binom{x+k−1}{k+1}(2x + k − 2)Q_{k,m}((2x + k − 2)^{2}), if k is odd and m is even;

\binom{x+k−1}{k+1}Q_{k,m}((2x + k − 2)^{2}), otherwise; for some polynomials Q_{k,m}(x) with rational coefficients.

For example,

f_{3,3}(N) = ∑_{i=0}^{N−1} \binom{i + 2}{3}^{3} = \binom{N + 2}{4}^{2} \frac{(2N + 1)^{2} − 10}{15},

f_{3,2}(N) = ∑_{i=0}^{N−1} \binom{i + 2}{3}^{2} = \binom{N + 2}{4}(2N + 1)\frac{5(2N + 1)^{2} − 41}{420},

f_{2,2}(N) = ∑_{i=0}^{N−1} \binom{i + 1}{2}^{2} = \binom{N + 1}{3}\frac{3N^{2} − 2}{10}.

By Faulhaber’s theorem, any odd power sum can be expressed as a combination of powers of triangular numbers

∑_{i=0}^{N} i^{2m−1} = \frac{1}{2m} ∑_{i=0}^{m−1} F_{i}(m)(N(N + 1))^{m−i},

and any even power sum can be expressed as

∑_{i=0}^{N} i^{2m} = (N − \frac{1}{2}) ∑_{i=0}^{m} F̃_{i}(m)(N(N − 1))^{m−i},

where F̃_{i}(m) = \frac{m+1−i}{(2m+1)(m+1)}F_{i}(m + 1). ^{1}

Knuth [5] showed that the coefficients F_{i}(m) have many interesting properties. Our generalization of Faulhaber’s theorem tends to consider the inverse problem: expressing the power sum of triangular numbers f_{2,m}(N) in terms of powers of N. We show that this expression can be presented as a combination of odd powers of N,

f_{2,m}(N) = ∑_{i=1}^{N−1} (\frac{i(i + 1)}{2})^{m} = \frac{1}{2^{m}} ∑_{i=0}^{m} \overline{F}_{i}(m)N^{2m−2i+1}.

We find the following duality relations between coefficients \overline{F} _{i}^{(m)} and F_{i}(m), F̃_{i}(m):

\overline{F}_{i}(m + i) = (−1)^{i−1} \frac{m + i}{m(2m + 1)}F_{i}(−m),

\overline{F}_{i}(m + i − 1) = (−1)^{i}F̃_{i}(−m).

Properties of \overline{F}_{i}(m) which similar to the properties of F_{i}(m) are also established.

We study integer divisibility properties of f_{k,m}(N) for integer N. We consider an analog of the Riemann zeta function

ζ(s) = ∑_{i=1}^{∞} \frac{1}{i^{s}}

1F_{i}(m) is referred to the sequences \underline{A093556}, \underline{A093557} and F̃_{i}(m) is referred to the sequences \underline{A093558}, \underline{A093559} in [7].

for binomial coefficients. Let

ζ_{k}(m) = ∑_{i=1}^{∞} \binom{i + k − 1}{k}^{−m}.

We prove that (for positive integers k, m and l = ⌈m/2⌉)

ζ_{k}(m) ∈ \begin{cases}ℚ + ℚζ(2) + ⋯ + ℚζ(2l), & if km is even; \\ ℚ + ℚζ(3) + ⋯ + ℚζ(2l − 1), & if km is odd and km > 1. \end{cases}

In case of k = 2 we obtain the formula for ζ_{2}(m),

\frac{ζ_{2}(m)}{2^{m}} = (−1)^{m−1}\binom{2m − 1}{m} + (−1)^{m}2 ∑_{i=1}^{⌊m/2⌋} \binom{2m − 2i − 1}{m − 1}ζ(2i).

The structure of our paper is as follows. In section 2, we consider the sum of products of binomial coefficients, which has combinatorial origin and is used in establishing polynomial properties of f_{k,m}(x). In section 3, an analog of Faulhaber’s theorem for the powers of binomial coefficients is proved. In section 4, we study integer properties for f_{k,m}(x) and for f_{k,−1}. In section 5, the properties of infinite sum ζ_{k}(m) are derived. In section 6, we focus on the partial case k = 2 and express the power sum of triangular numbers f_{2,m}(N) as a sum of powers of N.

2 Sum of products of binomial coefficients

2.1 A generalized Worpitzky identity

Let

f_{k_{1},...,k_{m}}(N) = ∑_{i=0}^{N−1} \binom{i + k_{1} − 1}{k_{1}} ⋯ \binom{i + k_{m} − 1}{k_{m}},  (1)

where k_{1} ≤ ⋯ ≤ k_{m}.

To study f_{k_{1},...,k_{m}}, we need a generalization of Worpitzky identity for multisets. To formulate this identity let us introduce Eulerian numbers for multisets.

Let m = 1^{k_{1}} ⋯ m^{k_{m}} be a multiset where l repeats k_{l} times, l = 1, …, m. Let S_{m} be the set of permutations of m and set K = k_{1} + ⋯ + k_{m}.

For a permutation σ = σ(1) … σ(K) ∈ S_{m}, let i be a descent index if i = K or σ(i) > σ(i + 1), i < K. A descent number des(σ) is defined as a number of descent indices of σ and Eulerian number a_{m,p} is defined as a number of permutations with p descents,

a_{m,p} = |{σ ∈ S_{m}|des(σ) = p}|.

For m = 1^{1}2^{1} ⋯ m^{1}, we obtain the usual Eulerian numbers a_{m,p} (\underline{A008292} in [7]) and the well-known Worpitzky identity

x^{m} = ∑_{p>0} \binom{x + m − p}{m}a_{m,p}.

Example 1. Let m = 1^{2}2^{2}. Then

S_{1^{2}2^{2}} = {1122, 1212, 2112, 2121, 2211, 1221},

and des(1122) = 1, des(1212) = 2, des(2112) = 2, des(2121) = 3,

des(2211) = 2, des(1221) = 2.

Therefore,

a_{1^{2}2^{2},1} = 1, a_{1^{2}2^{2},2} = 4, a_{1^{2}2^{2},3} = 1, and a_{1^{2}2^{2},i} = 0, if i ≠ 1, 2, 3.

Theorem 2 ([1]). For any nonnegative integers k_{1}, …, k_{m},

∏_{i=1}^{m} \binom{x + k_{i} − 1}{k_{i}} = ∑_{p>0} \binom{x + K − p}{K}a_{m,p},

where a_{m,p} are Eulerian numbers of permutations of the multiset m = 1^{k_{1}} ⋯ m^{k_{m}}.

Example 3. If m = 1^{2}2^{2}, then

\binom{x + 1}{2}^{2} = \binom{x + 3}{4} + 4\binom{x + 2}{4} + \binom{x + 1}{4}.

For a more detailed overview and other properties of Eulerian numbers on multisets and generalized Worpitzky identity, see [1].

2.2 Sum of products of binomial coefficients as a polynomial

Theorem 4. Let 0 ≤ k_{1} ≤ ⋯ ≤ k_{m}. Then the sum (1) induces a polynomial f_{k_{1},...,k_{m}}(x) of degree K + 1 with rational coefficients. As a polynomial with rational coefficients, the polynomial f_{k_{1},...,k_{m}}(x) is divisible by \binom{x+k_{m}−1}{k_{m}+1}.

Proof. By Theorem 2,

f_{k_{1},...,k_{m}}(N) = ∑_{p>0} ∑_{i=0}^{N−1} \binom{i + K − p}{K}a_{m,p} = ∑_{p>0} \binom{N + K − p}{K + 1}a_{m,p},

for any positive integer N. Therefore, we can substitute any variable x in N and see that

f_{k_{1},...,k_{m}}(x) ∈ ℚ[x], deg f_{k_{1},...,k_{m}}(x) = K + 1.

If k_{m} = 0, then k_{1} = ⋯ = k_{m} = 0, and

f_{0,...,0}(N) = N − 1.

Therefore, f_{0,...,0}(x) = x − 1. So, in this case divisibility of f_{k_{1},...,k_{m}}(x) by \binom{x+k_{m}−1}{k_{m}+1} is evident.

Suppose now that k_{m} > 0. Let us consider a difference polynomial

Δf(x) = f_{k_{1},...,k_{m}}(x + 1) − f_{k_{1},...,k_{m}}(x).

By (1),

Δf(x) = \binom{x + k_{1} − 1}{k_{1}} ⋯ \binom{x + k_{m} − 1}{k_{m}}.

Therefore, Δf(x) has k_{m} zeros: 0, −1, …, −(k_{m} − 1). Hence,

f_{k_{1},...,k_{m}}(1) − f_{k_{1},...,k_{m}}(0) = Δf(0) = 0,
f_{k_{1},...,k_{m}}(0) − f_{k_{1},...,k_{m}}(−1) = Δf(−1) = 0,
…
f_{k_{1},...,k_{m}}(−(k_{m} − 2)) − f_{k_{1},...,k_{m}}(−(k_{m} − 1)) = Δf(−(k_{m} − 1)) = 0.

If k_{m} > 0, then \binom{i+k_{m}−1}{k_{m}} = 0 for i = −k_{m} + 1. Therefore,

f_{k_{1},...,k_{m}}(−k_{m} + 1) = 0.

We thus obtain a polynomial f_{k_{1},...,k_{m}}(x) with k_{m} + 1 zeros

1, 0, −1, …, −(k_{m} − 1).

This means that f_{k_{1},...,k_{m}}(x) is divisible by \binom{x+k_{m}−1}{k_{m}+1}.

Set f_{k,m}(x) = f_{k,k,...,k}(x). In other words, f_{k,m}(x) is a polynomial defined by the following relations

f_{k,m}(N) = ∑_{i=0}^{N−1} \binom{i + k − 1}{k}^{m}.  (2)

Corollary 5. The polynomial f_{k,m}(x) has the following properties

• f_{k,m}(x) ∈ ℚ[x],

• deg f_{k,m}(x) = km + 1,

• f_{k,m}(x) is divisible by \binom{x+k−1}{k+1}.

A more detailed version of this result is given in the next section.

3 Faulhaber’s theorem for powers of binomial coefficients

3.1 Formulation of the main result

We know that f_{1,m}(N) = ∑_{i=1}^{N−1} i^{m} is a polynomial in N of degree m + 1. By Faulhaber’s theorem [2, 5], the polynomial f_{1,m}(x) is divisible by the polynomial f_{1,1}(x) = x(x − 1)/2.

For odd m, the polynomial f_{1,m}(x) is divisible by f_{1,1}(x)^{2} and the quotient is a polynomial in f_{1,1}(x). For even m, the polynomial f_{1,m}(x) can be presented as product of f_{1,1}(x)(2x − 1) and a polynomial in f_{1,1}(x).

The following theorem is an analog of Faulhaber’s theorem for the sum of powers of binomial coefficients.

Theorem 6. There exist polynomials Q_{k,m}(x) ∈ ℚ[x], such that

f_{k,m}(x) = \begin{cases}\binom{x+k−1}{k+1}^{2}Q_{k,m}((2x + k − 2)^{2}), & if m, k are odd, m > 1; \\ \binom{x+k−1}{k+1}(2x + k − 2)Q_{k,m}((2x + k − 2)^{2}), & if k is odd, m is even; \\ \binom{x+k−1}{k+1}Q_{k,m}((2x + k − 2)^{2}), & otherwise. \end{cases}

Note that f_{k,1}(x) = \binom{x+k−1}{k+1} and our theorem states that the polynomial f_{k,m}(x) is divisible by f_{k,1}(x). Moreover, if m and k are odd (m > 1), then f_{k,m}(x) is divisible by f_{k,1}(x)^{2}.

Let us show Theorem 6 for some small values of k.

If k = 1, then there are polynomials Q_{1,m}(x) ∈ ℚ[x], such that the polynomial f_{1,m}(N) = ∑_{i=1}^{N−1} i^{m} can be expressed as:

f_{1,m}(x) = \begin{cases}\binom{x}{2}^{2}Q_{1,m}((2x − 1)^{2}), & if m is odd and m > 1; \\ \binom{x}{2}(2x − 1)Q_{1,m}((2x − 1)^{2}), & if m is even. \end{cases}

Note that the polynomial Q_{1,m}((2x−1)^{2}) = Q_{1,m}(8\frac{x(x−1)}{2} +1) can be written as a polynomial in \binom{x}{2} = \frac{x(x−1)}{2}. Hence, Faulhaber’s theorem is a particular case of Theorem 6.

If k = 2, then for any m > 0, there exists a polynomial Q_{2,m}(x) ∈ ℚ[x], such that

f_{2,m}(x) = \binom{x + 1}{3}Q_{2,m}(x^{2}).

Since

\binom{x + 1}{3} = \frac{x(x^{2} − 1)}{6},

this implies that f_{2,m}(x) is an odd polynomial.

If k = 3, then f_{3,3}(x) = \binom{x+2}{4}^{2}Q_{3,3}(x), where

Q_{3,3}(x) = \frac{1}{15}(4x^{2} + 4x − 9).

Then for each positive integer m, (m > 1), there exists a polynomial Q_{3,m}(x) ∈ ℚ[x], such that

f_{3,m}(x) = \binom{x + 2}{4}^{2}Q_{3,m}(Q_{3,3}(x)), if m is odd, and

f_{3,m}(x) = \binom{x + 2}{4}(2x + 1)Q_{3,m}(Q_{3,3}(x)), if m is even.

3.2 Reflective functions

The proof of Theorem 6 is based on the notion of reflective functions introduced by Knuth [5]. The function f(x) is called r-reflective if for all x, we have

f(x) = f(−x − r);

and f(x) is called anti-r-reflective if for all x, we have

f(x) = −f(−x − r).

In other words, reflective functions are even or odd functions shifted by r/2.

Note that the

• sum of two (anti)-r-reflective functions is (anti)-r-reflective;

• product of two r-reflective functions is r-reflective;

• product of anti-r-reflective and r-reflective is anti-r-reflective function and

• product of two anti-r-reflective functions is r-reflective.

Lemma 7. Let ∇f(x) = f(x) − f(x − 1). Suppose that f(0) = f(−r) = 0 and the function f is defined on the set of integers. Then the following is true:

• if the function ∇f is (r − 1)-reflective, then f is anti-r-reflective and

• if the function ∇f is anti-(r − 1)-reflective, then f is r-reflective.

Proof. Suppose that ∇f is (r − 1)-reflective. Then we have

f(N) − f(0) = ∑_{i=1}^{N} ∇f(i) = ∑_{i=1}^{N} ∇f(−i − r + 1) = f(−r) − f(−N − r),

which gives f(N) = −f(−N − r) and this implies that f is anti-r-reflective.

Now if ∇f is anti-(r − 1)-reflective, then

f(N) − f(0) = ∑_{i=1}^{N} ∇f(i) = − ∑_{i=1}^{N} ∇f(−i − r + 1) = −f(−r) + f(−N − r).

So, f(N) = f(−N − r) and f is r-reflective.

Lemma 8 ([5], Lemma 4). A polynomial f(x) is r-reflective if and only if it can be presented as a polynomial in x(x+r) (or (2x+r)^{2}); it is anti-r-reflective if and only if it can be presented as 2x + r times a polynomial in x(x + r) (or (2x + r)^{2}).

Lemma 9. The polynomial \binom{x+k−1}{k} is (k−1)-reflective if k is even and anti-(k−1)-reflective if k is odd.

Proof. The proof follows from the identity \binom{x+k−1}{k} = (−1)^{k}\binom{−x}{k}.

By Theorem 4, there exist polynomials g_{k,m}(x) ∈ ℚ[x], such that

f_{k,m}(x) = \binom{x + k − 1}{k + 1}g_{k,m}(x).

Lemma 10. Reflective properties of functions f_{k,m} and g_{k,m} are

• f_{k,m}(x) is (k − 2)-reflective if km + 1 is even and anti-(k − 2)-reflective if km + 1 is odd.

• g_{k,m}(x) is (k − 2)-reflective if (m − 1)k is even and anti-(k − 2)-reflective if (m − 1)k is odd.

Proof. Let ∇f = f(x) − f(x − 1). Since ∇f_{k,m}(x) = \binom{x+k−2}{k}^{m}, we see that ∇f_{k,m}(x) is (k − 3)-reflective if km is even and anti-(k − 3)-reflective, otherwise. By Theorem 4, f(0) = f(−(k − 2)) = 0. Thus, by Lemma 7, f_{k,m}(x) is anti-(k − 2)-reflective if km is even and (k − 2)-reflective, otherwise.

Note that g_{k,m} = f_{k,m}/\binom{x+k−1}{k+1}. Therefore by Lemma 9, g_{k,m}(x) is (k − 2)-reflective if km − k is even and anti-(k − 2)-reflective, otherwise.

Lemma 11. Let k be an odd number. Then f_{k,m}(x) is divisible by \binom{x+k−1}{k+1}(2x + k − 2) if m is even and is divisible by \binom{x+k−1}{k+1}^{2} if m is odd and m > 1.

Proof. Suppose that m is even. By Lemma 10, the function g_{k,m} is anti-(k − 2)-reflective. The anti-(k − 2)-reflectivity condition for x = \frac{2−k}{2} gives us

g_{k,m}(−\frac{2 − k}{2} − k + 2) = g_{k,m}(\frac{2 − k}{2} ) = −g_{k,m}(\frac{2 − k}{2} ).

Hence, g_{k,m}(\frac{2−k}{2}) = 0 and g(x) is divisible by (2x + k − 2).

Now consider the case m is odd (m > 1). By Lemma 10, the function g_{k,m} is (k − 2)- reflective. We have

f_{k,m}(x + 1) − f_{k,m}(x) = \binom{x + k}{k + 1}g_{k,m}(x + 1) − \binom{x + k − 1}{k + 1}g_{k,m}(x) = \binom{x + k − 1}{k}^{m}.

Hence,

(x + k)g_{k,m}(x + 1) − (x − 1)g_{k,m}(x) = (k + 1)\binom{x + k − 1}{k}^{m−1}.

Therefore, for i = 0, −1, …, −(k − 1), we obtain

(k + i)g_{k,m}(i + 1) − (i − 1)g_{k,m}(i) = 0.

In other words,

kg_{k,m}(1) = −g_{k,m}(0),
(k − 1)g_{k,m}(0) = −2g_{k,m}(−1),
(k − 2)g_{k,m}(−1) = −3g_{k,m}(−2),

⋮

g_{k,m}(−(k − 2)) = −kg_{k,m}(−(k − 1)).

Hence,

g_{k,m}(1) = (−1)^{k}g_{k,m}(−(k − 1)) = −g_{k,m}(−(k − 1)).

Since g_{k,m}(x) is (k − 2)-reflective, the reflectivity condition for x = 1 gives us

g_{k,m}(1) = g_{k,m}(−(k − 1)).

So, g_{k,m}(1) = 0 and

g_{k,m}(−(k − 1)) = ⋯ = g_{k,m}(−1) = g_{k,m}(0) = g_{k,m}(1) = 0.

Thus, g_{k,m}(x) is divisible by \binom{x+k−1}{k+1} and f_{k,m}(x) is divisible by \binom{x+k−1}{k+1}^{2}.

3.3 Proof of Theorem 6.

Let m and k be two odd positive integers and m > 1. By Lemma 11, there exist polynomials R_{k,m}(x) such that g_{k,m}(x) = \binom{x+k−1}{k+1}R_{k,m}(x). The function g_{k,m}(x) is (k − 2)-reflective and therefore, R_{k,m}(x) (according to parity of k) is also (k − 2)-reflective. So, by Lemma 8, there exist polynomials Q_{k,m}(x) ∈ ℚ[x] such that R_{k,m}(x) = Q_{k,m}((2x + k − 2)^{2}). In this case

f_{k,m}(x) = \binom{x + k − 1}{k + 1}^{2}Q_{k,m}((2x + k − 2)^{2}).

Now assume that k is odd and m is even. Then the function g_{k,m} is anti-(k −2)-reflective. By Lemma 8, there exist polynomials Q_{k,m}(x) ∈ ℚ[x], such that g_{k,m}(x) = (2x + k − 2)Q_{k,m}((2x + k − 2)^{2}). Therefore,

f_{k,m}(x) = \binom{x + k − 1}{k + 1}(2x + k − 2)Q_{k,m}((2x + k − 2)^{2}).

In all other cases g_{k,m} is (k − 2)-reflective. By Lemma 8, there exist polynomials Q_{k,m}(x) ∈ ℚ[x] such that g_{k,m}(x) = Q_{k,m}((2x + k − 2)^{2}). We have

f_{k,m}(x) = \binom{x + k − 1}{k + 1}Q_{k,m}((2x + k − 2)^{2}).

□

4 Integer divisibility for f_{k,m}(x)

4.1 Formulation of the main result

By Theorem 6, the polynomial f_{k,m}(x) is divisible by \binom{x+k−1}{k+1}^{2} if m and k are odd (m > 1). In particular, f_{k,m}(x) is divisible by x^{2}. By Theorem 6, f_{k,m}(x) is divisible by x for any k, m. Here divisibility refers to the divisibility of polynomials with rational coefficients. Now in this section, we study divisibility properties of f_{k,m}(x) for integer x.

The divisibility properties of Theorem 6 do not hold for integers. Let us give counterexamples for all three cases:

\frac{f_{3,5}(7)}{7^{2}} = \frac{1}{7^{2}} ∑_{i=1}^{6} \binom{i + 2}{3}^{5} = \frac{86650668}{7} ∉ ℤ,

\frac{f_{3,2}(5)}{5} = \frac{1}{5} ∑_{i=1}^{4} \binom{i + 2}{3}^{2} = \frac{517}{5} ∉ ℤ,

\frac{f_{4,4}(11)}{11} = \frac{1}{11} ∑_{i=1}^{10} \binom{i + 3}{4}^{4} = \frac{335469880502}{11} ∉ ℤ.

Since f_{k,m}(x) ∈ ℚ[x], for any given k and m, there is a sufficiently large prime p, such that f_{k,m}(p) is divisible by p and by p^{2} if m, k are odd and m > 1. The following theorem is a more detailed version of these statements.

Theorem 12. Let N, k, m be positive integers. Let M be an odd positive integer such that gcd(M, k!) = 1 and M − k + 1 ≤ N ≤ M + 1. Then

f_{k,m}(N) = ∑_{i=0}^{N−1} \binom{i + k − 1}{k}^{m} ≡ 0 (mod M)

in the following cases

• m, k are odd numbers, or

• gcd(M, (km + 1)!) = 1 (k, m may be even or odd).

If m, k are odd numbers and m > 1, then

f_{k,m}(N) = ∑_{i=0}^{N−1} \binom{i + k − 1}{k}^{m} ≡ 0 (mod M^{2})

in the following cases

• m is divisible by M;

• gcd(M, (km + 1)!) = 1.

Remark 13. Theorem 12 do not present all conditions for divisibility of f_{k,m}(N) by M and M^{2}. For example, if M = 13, k = 4, m = 14, N = 13, then

f_{4,14}(13) = ∑_{i=0}^{12} \binom{i + 3}{4}^{14} = 13 × 6075433069762635003999567344079450237278856,

but 4, 14 are even and gcd(13, 57!) ≠ 1. Similarly, if M = 7, k = 3, m = 9, N = 7, then

f_{3,9}(7) = ∑_{i=0}^{6} \binom{i + 2}{3}^{9} = 7^{2} × 112153022185284,

but 9 is not divisible by 7 and gcd(7, 28!) ≠ 1.

4.2 Proof

To prove Theorem 12 we need some preliminary facts. Lemma 14. Let M be an odd positive integer number such that gcd(M, k!) = 1. Then for odd numbers k, m and for all integers i such that 1 ≤ i ≤ M − k, the following relation holds

\binom{M − i + k − 1}{k}^{m} ≡ −\binom{i + k − 1}{k}^{m} + Mm\binom{i + k − 1}{k}^{m} ∑_{j=0}^{k−1} \frac{1}{i + j} (mod M^{2}).

Proof. Let us consider an expression \binom{M−i+k−1}{k} as a polynomial in M,

\binom{M − i + k − 1}{k} = \frac{(M − i + k − 1) ⋯ (M − i)}{k!}

= a_{k}M^{k} + ⋯ + a_{1}M + a_{0}

= \frac{M^{k}}{k!} + ⋯ + M(−1)^{k−1}\binom{i + k − 1}{k} ∑_{j=0}^{k−1} \frac{1}{i + j} + (−1)^{k}\binom{i + k − 1}{k}.

Note that for 0 ≤ j ≤ k − 1, all numbers i + j are relatively prime with M. Therefore,

\binom{M − i + k − 1}{k} ≡ (−1)^{k}\binom{i + k − 1}{k} + (−1)^{k−1}M\binom{i + k − 1}{k} ∑_{j=0}^{k−1} \frac{1}{i + j} (mod M^{2}).

Hence,

\binom{M − i + k − 1}{k}^{m} ≡ (−\binom{i + k − 1}{k} + M\binom{i + k − 1}{k} ∑_{j=0}^{k−1} \frac{1}{i + j} )^{m} (mod M^{2})

On expanding the right side of this congruence, we obtain the result. Lemma 15. (km + 1)!f_{k,m}(x) ∈ ℤ[x]. Proof. By Theorem 2, there are some integers a_{j} for which we can present f_{k,m}(x) in the form ∑_{j>0} a_{j}\binom{x+km−j}{km+1}. Note that (km + 1)!\binom{x+km−j}{km+1} ∈ ℤ[x]. Proof of Theorem 12. For 0 ≤ i ≤ M − k with odd k, by Lemma 14,

\binom{M − i + k − 1}{k}^{m} + \binom{i + k − 1}{k}^{m} ≡ 0 (mod M).

Therefore,

∑_{i=0}^{N−1} \binom{i + k − 1}{k}^{m} ≡ ∑_{i=1}^{M−k} \binom{i + k − 1}{k}^{m}

= \frac{1}{2} ∑_{i=1}^{M−k} (\binom{M − i + k − 1}{k}^{m} + \binom{i + k − 1}{k}^{m}) ≡ 0 (mod M).

Now suppose that m is divisible by N. Hence, by Lemma 14, we have

\binom{M − i + k − 1}{k}^{m} ≡ −\binom{i + k − 1}{k}^{m} + Mm\binom{i + k − 1}{k}^{m} ∑_{j=0}^{k−1} \frac{1}{i + j}

≡ −\binom{i + k − 1}{k}^{m} (mod M^{2}).

Therefore,

∑_{i=0}^{N−1} \binom{i + k − 1}{k}^{m} ≡ ∑_{i=1}^{M−k} \binom{i + k − 1}{k}^{m}

= \frac{1}{2} ∑_{i=1}^{M−k} (\binom{M − i + k − 1}{k}^{m} + \binom{i + k − 1}{k}^{m}) ≡ 0 (mod M^{2}).

Since gcd(M, (km + 1)!) = 1, by Lemma 15 and Theorem 6, (km + 1)!f_{k,m}(x) ∈ ℤ[x] is divisible by x(x + 1) ⋯ (x + k − 1) and by (x(x + 1) ⋯ (x + k − 1))^{2} if m, k are odd numbers and m > 1. Here divisibility refers to the divisibility of polynomials with integer coefficients.

Remark 16. In Theorem 12 we can change M to a power of some prime number p. The property gcd(M, (km + 1)!) = 1 can be changed by an inequality p > km + 1.

4.3 Integer divisibility in case k = 2

Theorem 17. Assume that p is an odd prime number and 1 ≤ m ≤ p − 1. Then

f_{2,m}(p) = ∑_{i=1}^{p−1} \binom{i + 1}{2}^{m} ≡ \begin{cases}−2 (mod p), & if m = p − 1; \\ −\frac{1}{2^{m}} \binom{m}{p−1−m} (mod p), & otherwise. \end{cases}

Proof. The following fact is known:

∑_{i=1}^{p−1} i^{t} ≡ \begin{cases}0 (mod p), & if t is not divisible by p − 1; \\ −1 (mod p), & otherwise. \end{cases}

Therefore,

f_{2,m}(p) = ∑_{i=1}^{p−1} \binom{i + 1}{2}^{m} = \frac{1}{2^{m}} ∑_{i=1}^{p−1} ∑_{j=0}^{m} \binom{m}{j}i^{m+j} = \frac{1}{2^{m}} ∑_{j=0}^{m} \binom{m}{j} ∑_{i=1}^{p−1} i^{m+j}

If m = p − 1, then m + j is divisible by p − 1 only in two cases: j = 0, m. Hence,

f_{2,p−1}(p) ≡ −\frac{1}{2^{p−1}} (\binom{p − 1}{0} + \binom{p − 1}{p − 1}) ≡ −2 (mod p).

If 1 ≤ m < p − 1, there is only one integer j ∈ [0, m] such that m + j is divisible by p − 1. Namely, j = p − 1 − m. In this case,

f_{2,m}(p) ≡ −\frac{1}{2^{m}} \binom{m}{p − 1 − m} (mod p).

Remark 18. By Theorem 17, if p − 1 − m > m, then f_{2,m}(p) ≡ 0 (mod p). This fact is compatible with Theorem 12, because p > 2m + 1.

4.4 The case f_{k,−1}(N)

Theorem 19. Let N, k be positive integer numbers and M be a positive integer such that gcd(M, k!) = 1. Then, the rational number q defined as

q = f_{(k,−1)}(N) = ∑_{i=1}^{N−1} \frac{1}{\binom{i+k−1}{k}},

is divisible by M (its denominator is relatively prime with M) in the following cases: (i) N ≡ 1 (mod M); (ii) N ≡ 1 − k (mod M) and k is odd.

To prove this result we need one

Lemma 20. Suppose that k > 1. Then

f_{k,−1}(N) = ∑_{i=1}^{N−1} \frac{1}{\binom{i+k−1}{k}} = \frac{k}{k − 1} (1 − \frac{1}{\binom{N+k−2}{k−1}}) .

Proof. Let ϕ(x) = \frac{1}{\binom{x+k−1}{k−1}}. Then it is easy to verify that

\frac{1}{\binom{i+k−1}{k}} = \frac{k}{k − 1} (\frac{1}{\binom{i+k−2}{k−1}} − \frac{1}{\binom{i+k−1}{k−1}}) = −\frac{k}{k − 1}∇ϕ(i).

Therefore,

f_{(k,−1)}(N) = ∑_{i=1}^{N−1} \frac{1}{\binom{i+k−1}{k}} = −\frac{k}{k − 1} ∑_{i=1}^{N−1} ∇ϕ(i)

= \frac{k}{k − 1}(ϕ(0) − ϕ(N − 1)) = \frac{k}{k − 1} (1 − \frac{1}{\binom{N+k−2}{k−1}}) .

Proof of Theorem 19. By Lemma 20,

f_{k,−1}(N) = \frac{k!}{k − 1} (\frac{1}{(k − 1)!} − \frac{1}{(N + k − 2) ⋯ N} ) .

Notice that for both cases (i) and (ii), the numbers N, …, N + k − 2 are relatively prime with M. So, if N ≡ 1 (mod M), then

(N + k − 2) ⋯ N ≡ (k − 1)! (mod M).

If N ≡ 1 − k (mod M) and k is odd, then

(N + k − 2) ⋯ N ≡ (−1)^{k−1}(k − 1)! ≡ (k − 1)! (mod M).

5 Power sum of reciprocals of binomial coefficients

5.1 Formulation of the main result

In this section, we consider the case of power sums of binomial coefficients with negative powers,

ζ_{k}(m) = ∑_{i=1}^{∞} \binom{i + k − 1}{k}^{−m}.

For k = 1 we have

ζ_{1}(m) = ζ(m) = ∑_{i=1}^{∞} \frac{1}{i^{m}} ,

where ζ(m) is a Riemann zeta function.

In particular, for m = 1, by Lemma 20, one can obtain the exact value

ζ_{k}(1) = ∑_{i=1}^{∞} \binom{i + k − 1}{k}^{−1} = \frac{k}{k − 1}.

It is known that for any positive integer m,

ζ(2m) = (−1)^{m+1} \frac{(2π)^{2m}}{2(2m)!}B_{2m},  (3)

where B_{2m} is a Bernoulli number.

We prove similar results for binomial coefficients. Some examples that follow from our results:

ζ_{2}(2) = ∑_{i=1}^{∞} \binom{i + 1}{2}^{−2} = \frac{4}{3}π^{2} − 12,

ζ_{2}(3) = ∑_{i=1}^{∞} \binom{i + 1}{2}^{−3} = −8π^{2} + 80,

ζ_{3}(2) = ∑_{i=1}^{∞} \binom{i + 2}{3}^{−2} = 9π^{2} − \frac{351}{4}.

Similarly,

ζ_{3}(3) = ∑_{i=1}^{∞} \binom{i + 2}{3}^{−3} = \frac{783}{4} − 162ζ(3),

ζ_{5}(3) = ∑_{i=1}^{∞} \binom{i + 4}{5}^{−3} = −\frac{1298125}{96} + 11250ζ(3),

ζ_{3}(5) = ∑_{i=1}^{∞} \binom{i + 2}{3}^{−5} = \frac{576639}{16} − \frac{47385}{2}ζ(3) − 7290ζ(5).

Below we show that these relations are based on reflectivity properties of binomial coefficients, and that ζ_{k}(m) can be expressed as a linear combination of certain values of the Riemann zeta function.

Theorem 21. For any positive integers k and m, there exist rationals λ_{0}, λ_{1}, …, λ_{⌈m/2⌉}, such that

ζ_{k}(m) = \begin{cases}λ_{0} + ∑_{i=1}^{⌈m/2⌉} λ_{i}ζ(2i), & if km is even; \\ λ_{0} + ∑_{i=1}^{⌈m/2⌉} λ_{i}ζ(2i − 1), & if km is odd. \end{cases}

5.2 Proof of Theorem 21

Let F (x) = \binom{x+k−1}{k}^{−m}. Then ζ_{k}(m) = ∑_{i=1}^{∞} F (i). Since the polynomial F (x) has k zeros x = 0, 1, …, k − 1,

F (x) = \frac{1}{\binom{x+k−1}{k}m} = ∑_{j=0}^{k−1} ∑_{i=1}^{m} \frac{a_{i,j}}{(x + j)^{i}} = \frac{1}{2} ∑_{j=0}^{k−1} ∑_{i=1}^{m} (\frac{a_{i,j}}{(x + j)^{i}} + \frac{a_{i,k−1−j}}{(x + k − 1 − j)^{i}} ) (4)

for some rational numbers a_{i,j} (1 ≤ i ≤ m, 0 ≤ j ≤ k − 1).

By Lemma 9, 1/F (x) is (k − 1)-reflective if km is even, and 1/F (x) is anti-(k − 1)- reflective, if km is odd. In other words, F (x) = eF (−x − k + 1) for almost all x (except zeros of denominator), where e = ±1. Thus, by (4) and based on the reflectivity property mentioned above,

∑_{j=0}^{k−1} ∑_{i=1}^{m} (\frac{a_{i,j}}{(x + j)^{i}} + \frac{a_{i,k−1−j}}{(x + k − 1 − j)^{i}} ) = e ∑_{j=0}^{k−1} ∑_{i=1}^{m} (\frac{a_{i,j}}{(−x − k + 1 + j)^{i}} + \frac{a_{i,k−1−j}}{(−x − j)^{i}} )

or

∑_{j=0}^{k−1} ∑_{i=1}^{m} (\frac{a_{i,j} − e(−1)^{i}a_{i,k−1−j}}{(x + j)^{i}} + \frac{a_{i,k−1−j} − e(−1)^{i}a_{i,j}}{(x + k − 1 − j)^{i}} ) = 0.

Therefore,

a_{i,j} − e(−1)^{i}a_{i,k−1−j} = 0

for all i, j (1 ≤ i ≤ m, 0 ≤ j ≤ k − 1). Hence, equation (4) can be rewritten as

F (x) = \frac{1}{\binom{x+k−1}{k}m} = \frac{1}{2} ∑_{j=0}^{k−1} ∑_{i=1}^{m} (\frac{a_{i,j}}{(x + j)^{i}} + e(−1)^{i} \frac{a_{i,j}}{(x + k − 1 − j)^{i}} ) .

Finally,

ζ_{k}(m) = ∑_{x=1}^{∞} F (x)

= ∑_{x=1}^{∞} \frac{1}{2} ∑_{j=0}^{k−1} ∑_{i=1}^{m} (\frac{a_{i,j}}{(x + j)^{i}} + e(−1)^{i} \frac{a_{i,j}}{(x + k − 1 − j)^{i}} )

= \frac{1}{2} ∑_{j=0}^{k−1} ∑_{i=1}^{m} a_{i,j} (ζ(i) − ∑_{l=1}^{j} \frac{1}{l^{i}} + e(−1)^{i}ζ(i) − e(−1)^{i} ∑_{l=1}^{k−1−j} \frac{1}{l^{i}} )

= c_{0} + ∑_{i=1}^{m} c_{i}(ζ(i) + e(−1)^{i}ζ(i)),

for some rational constants c_{i} (0 ≤ i ≤ m). Note that value (ζ(i) + e(−1)^{i}ζ(i)) vanishes if e = 1 and i is odd, or if e = −1 and i is even. □

Presentations of infinite series as a linear combination of odd (even) values of zeta functions play an important role in studying the irrationality problems of zeta functions. See, for example, the proof of Rivoal [6] that the sequence ζ(3), ζ(5), … contains infinitely many irrational values, or result of Zudilin [12] that at least one of four numbers ζ(5), ζ(7), ζ(9), ζ(11) is irrational.

Different kinds of sums of inverses of binomial coefficients were studied in many works, e.g., the sums of other types by Sofo [8], Sprugnoli [9], Sury, Wang and Zhao [10], Yang and Zhao [11].

5.3 Sums of reciprocals of powers of triangular numbers

Recall that

ζ_{2}(m) = ∑_{x=1}^{∞} \frac{2^{m}}{(x(x + 1))^{m}} .

In this subsection we give exact presentation of ζ_{2}(m) as a combination of binomial coefficients and Bernoulli numbers. Namely, we prove the following result.

Theorem 22.

∑_{x=1}^{∞} \frac{1}{(x(x + 1))^{m}} = (−1)^{m−1}\binom{2m − 1}{m} + (−1)^{m} ∑_{i=1}^{⌊m/2⌋} \binom{2m − 2i − 1}{m − 1}(−1)^{i+1} \frac{(2π)^{2i}}{(2i)!} B_{2i}.

To prove this theorem we need the following Lemma 23.

\frac{1}{\binom{x+1}{2}m} = 2^{m} ∑_{i=0}^{m−1} \binom{m + i − 1}{i} ((−1)^{i} \frac{1}{x^{m−i}} + (−1)^{m} \frac{1}{(x + 1)^{m−i}} ) .

Proof. We use induction on m. For m = 1 we have

\frac{1}{\binom{x+1}{2}} = 2 (\frac{1}{x} − \frac{1}{x + 1}) .

Assume that our statement holds for m and let us prove it for m + 1. In our proof we need the following formulas (j is a positive integer):

\frac{1}{x^{j}(x + 1)} = \frac{1}{x^{j}} − \frac{1}{x^{j−1}} + ⋯ + (−1)^{j} \frac{1}{x + 1} and
\frac{1}{x(x + 1)^{j}} = \frac{1}{x} − \frac{1}{x + 1} − ⋯ − \frac{1}{(x + 1)^{j}} ,

which follow from:

1 − (−x)^{j} = (1 + x)(1 + (−x) + ⋯ + (−x)^{j−1}) and
1 − (x + 1)^{j} = −x(1 + (x + 1) + ⋯ + (x + 1)^{j−1}).

We have

\frac{1}{(x(x + 1))^{m+1}} = \frac{1}{(x(x + 1))^{m}} (\frac{1}{x} − \frac{1}{x + 1})

= ∑_{i=0}^{m−1} \binom{m + i − 1}{i} (\frac{(−1)^{i}}{x^{m−i}} + \frac{(−1)^{m}}{(x + 1)^{m−i}} ) (\frac{1}{x} − \frac{1}{x + 1})

= ∑_{i=0}^{m} \binom{m + i}{i} (\frac{(−1)^{i}}{x^{m−i+1}} + \frac{(−1)^{m+1}}{(x + 1)^{m−i+1}} )

(since ∑_{j=0}^{i} \binom{m+j−1}{j} = \binom{m+i}{i} ).

Proof of Theorem 22. By Lemma 23,

∑_{x=1}^{∞} \frac{1}{(x(x + 1))^{m}} = ∑_{x=1}^{∞} ∑_{i=0}^{m−1} \binom{m + i − 1}{i} (\frac{(−1)^{i}}{x^{m−i}} + \frac{(−1)^{m}}{(x + 1)^{m−i}} )

= ∑_{i=0}^{m−1} \binom{m + i − 1}{i} (∑_{x=1}^{∞} \frac{(−1)^{i}}{x^{m−i}} + ∑_{x=1}^{∞} \frac{(−1)^{m}}{(x + 1)^{m−i}} ) .

Thus, the last expression can be written as

∑_{i=0}^{m−1} \binom{m + i − 1}{i} ((−1)^{i}ζ(m − i) + (−1)^{m}(ζ(m − i) − 1))

= (−1)^{m−1} ∑_{i=0}^{m−1} \binom{m + i − 1}{i} + ∑_{i=0,(m−i) even}^{m−1} \binom{m + i − 1}{i}(−1)^{i}2ζ(m − i)

= (−1)^{m−1}\binom{2m − 1}{m} + (−1)^{m}2 ∑_{i=1}^{⌊m/2⌋} \binom{2m − 2i − 1}{m − 1}ζ(2i)

= (−1)^{m−1}\binom{2m − 1}{m} + (−1)^{m} ∑_{i=1}^{⌊m/2⌋} \binom{2m − 2i − 1}{m − 1}(−1)^{i+1} \frac{(2π)^{2i}}{(2i)!} B_{2i}.

6 Faulhaber coefficients and coefficients of the polynomial f_{2,m}(x)

6.1 Duality between F - and \overline{F} -Faulhaber coefficients

Recall that any number in the form \binom{n}{2} = \frac{n(n−1)}{2} is called triangular (\underline{A000217} in [7]). In this section we study analogs of Faulhaber coefficients for power sums of triangular numbers. To stress similarities between Faulhaber coefficients F_{i}(m) and \overline{F}_{i}(m) (see definitions below), we use special notation for formulas like (A1), (B1), (A2), (B2), etc.

We define Faulhaber coefficients [3, 5] as numbers F_{i}(m), such that

∑_{i=0}^{N} i^{2m−1} = \frac{1}{2m} ∑_{i=0}^{m−1} F_{i}(m)(N(N + 1))^{m−i}.  (A1)

These coefficients can be extended for all real numbers x by F_{i}(x). In fact, F_{i}(x) is a polynomial in x. In Sloane’s OEIS [7], F_{i}(m) is referred to the sequences \underline{A093556}, \underline{A093557} and

F̃_{i}(m) = \frac{m + 1 − i}{(2m + 1)(m + 1)}F_{i}(m + 1)  (5)

is referred to the sequences \underline{A093558}, \underline{A093559}.

Knuth [5] has established the following properties of these coefficients,

F_{0}(x) = 1; ∑_{j=0}^{k} \binom{x − j}{2k + 1 − 2j}F_{j}(x) = 0, k > 0.  (A2)

F_{k}(x) = x(x − 1) ⋯ (x − k + 1) × q_{k}(x),  (A3)

where q_{k}(x) is • a polynomial of degree k

• with leading coefficient equal to (2 − 2^{2k})B_{2k}/(2k)!;

• and q_{k}(k + 1) = 0 if k > 0.

Below we show that all zeros of this polynomial are real and distinct.

A recurrence formula due to Jacobi yields:

(2x − 2k)(2x − 2k + 1)F_{k}(x) + (x − k + 1)(x − k)F_{k−1}(x) = 2x(2x − 1)F_{k}(x − 1). (A4)

Gessel and Viennot [3] obtained the following explicit formula:

F_{k}(m) = (−1)^{m−k} ∑_{j} \binom{2m}{m − k − j}\binom{m − k + j}{j}\frac{m − k − j}{m − k + j} B_{m+k+j},  (A5)

for 0 ≤ k < m.

In terms of determinants, this formula can be written as

F_{k}(m) = (−1)^{(m−k)} \frac{1}{(m − 1) ⋯ (m − k)} det |\binom{m − k + i}{2i − 2j + 3}|_{i,j=1,...,k} .  (A6)

The last determinant has a combinatorial interpretation.

Theorem 24 (Gessel, Viennot, Theorem 14, [3]). The number of sequences of positive integer numbers a_{1}, …, a_{3k} satisfying inequalities a_{3i−2} < a_{3i−1} < a_{3i}, a_{3i+1} ≤ a_{3i−1}, a_{3i+2} ≤ a_{3i} and a_{3i} ≤ m − k + i, for all i, is equal to

det |\binom{m − k + i}{2i − 2j + 3}|_{i,j=1,...,k} .

According to Theorem 6, the polynomial f_{2,m}(x) is odd. Therefore we can consider the coefficients \overline{F}_{i}(m) defined by

f_{2,m}(N)2^{m} = ∑_{i=0}^{N−1}(i(i + 1))^{m} = ∑_{i=0}^{m} \overline{F}_{i}(m)N^{2m−2i+1}.  (B1)

The following relations are \overline{F} _{i}^{(m)} analogs of relations (A2)–(A6),

\overline{F}_{0}(m) = 1; ∑_{j=0}^{k} \binom{m + 2k − j}{2k + 1 − 2j}(−1)^{j}\overline{F}_{j}(m + j) = 0.  (B2)

\overline{F}_{i}(m) = \frac{m(m − 1) ⋯ (m − i)}{2m − 2i + 1} × h_{i}(m),  (B3)

where h_{i}(m) is

• a polynomial of degree i • with leading coefficient (−1)^{i−1}(2 − 2^{2i})B_{2i}/(2i)!;

• and h_{i}(−1) = 0 if i > 0.

Proof of these properties will be presented in Theorem 29 below. In fact, Theorem 25 tells us that h_{i}(m) = q_{i}(i − m).

A recurrence formula for \overline{F}_{i}(m) is given by

2(m − i)(2m − 2i + 1)\overline{F}_{i}(m) = 2m(2m − 1)\overline{F}_{i}(m − 1) + m(m − 1)\overline{F}_{i−1}(m − 2). (B4)

Coefficients \overline{F}_{i}(m) are closely related to F_{i}(m).

Theorem 25.

\overline{F}_{i}(m + i) = (−1)^{i−1} \frac{m + i}{m(2m + 1)}F_{i}(−m)  (6)

Another formulation of Theorem 25 is given by

\overline{F}_{i}(m) = (−1)^{i−1} \frac{m}{(m − i)(2m − 2i + 1)}F_{i}(i − m).

Proof. From relations (A4) and (B4), we can see that the sequences \overline{F}_{i}(m + i) and F_{i}(−m) satisfy the same recurrence relations and they have equal initial values F_{0}(x) = \overline{F}_{0}(x) = 1.

Knuth [5] proved that

∑_{i=0}^{N−1} i^{2m} = (N − \frac{1}{2}) ∑_{i=0}^{m} F̃_{i}(m)(N(N − 1))^{m−i},

with relation (5) between the coefficients F̃_{i}(m) and F_{i}(m).

Corollary 26.

\overline{F}_{i}(m + i − 1) = (−1)^{i}F̃_{i}(−m).  (7)

The following is a general formula for \overline{F}_{i}(m)

\overline{F}_{i}(m) = \frac{1}{(2m − 2i + 1)} ∑_{k=0}^{2i} \binom{m}{2i − k}\binom{2m − 2i + k}{k}B_{k}.  (B5)

Let us rewrite this formula in terms of determinants

\overline{F}_{k}(m) = \frac{(−1)^{(k−m+1)}(k − 1)!}{(2m − 2k + 1)(m − 1)!} det |\binom{m + i − 2j + 2}{2i − 2j + 3}|_{i,j=1,...,k} ,  (B6)

which follows from (A6) and Theorem 25.

Using [3, Theorem 16], we obtain one more combinatorial interpretation for the last determinant.

Theorem 27. The number of sequences of positive integers a_{1}, …, a_{3k} such that a_{3i−2} ≥ a_{3i−1} ≥ a_{3i}, a_{3i+1} ≥ a_{3i−1}, a_{3i+2} ≥ a_{3i} and a_{3i−2} ≤ m − i, for all i, is equal to

det |\binom{m + i − 2j + 2}{2i − 2j + 3}|_{i,j=1,...,k} .

Proof. Let λ = (λ_{1}, …, λ_{k}) and μ = (μ_{1}, …, μ_{k}) be two non-increasing sequences of nonnegative integers. Plane partition of shape λ − μ is a filling of the corresponding diagram with integers which are weakly decreased in every row and column. Such a diagram can be obtained from Ferrer diagram for λ by removing the diagram for μ (for details, see [3]) .

By [3, Theorem 16], the number of plane partitions of shape λ − μ whose parts in row i are at most A_{i} and at least B_{i}, where A_{i} ≥ A_{i+1} − 1 and B_{i} ≥ B_{i+1} − 1, is equal to

det |\binom{A_{j} − B_{i} + λ_{i} − μ_{j}}{λ_{i} − μ_{j} + j − i}|_{i,j=1,...,k} .

Taking λ_{i} = k + 3 − i, μ_{j} = k − j, A_{j} = m − j and B_{i} = 1, we obtain the result.

6.2 The polynomial f_{2,m}(x)

Set λ_{m,i} = \overline{F}_{i}(m)/2^{m}.

Theorem 28. The polynomial f_{2,m}(x) = ∑_{i=0}^{m} λ_{m,i}x^{2m−2i+1} has the following properties. (I) It satisfies the equation

f′′_{2,m}(x) = m(2m − 1)f_{2,m−1}(x) + \frac{m(m − 1)}{4}f_{2,m−2}(x),  m ≥ 2,  (8)

f_{0,2}(x) = x, f_{2,1}(x) = \binom{x + 1}{3}.

(II) The following recurrence relation holds for coefficients λ_{m,i},

λ_{m,i} = \frac{m(2m − 1)}{2(m − i)(2m − 2i + 1)}λ_{m−1,i} + \frac{m(m − 1)}{8(m − i)(2m − 2i + 1)}λ_{m−2,i−1},  (9)

where 0 < i < m.

(III) The following general formula holds

λ_{m,i} = \frac{1}{2^{m}(2m − 2i + 1)} ∑_{k=0}^{2i} \binom{m}{2i − k}\binom{2m − 2i + k}{k}B_{k}.  (10)

Proof. (I) Since Δf_{2,m}(x) = \binom{x+1}{2}^{m}, we have

Δf′′_{2,m}(x) = m(2m − 1)\binom{x + 1}{2}^{m−1} + \frac{m(m − 1)}{4}\binom{x + 1}{2}^{m−2},

and

f′′_{2,m}(0) = 0.

Therefore, (8) is true.

(II) (9) is a consequence of (8).

(III) We have

2^{m}f_{2,m}(N) = ∑_{i=0}^{N−1}(i(i + 1))^{m} = ∑_{i=0}^{N−1} ∑_{j=0}^{m} \binom{m}{j}i^{m+j} = ∑_{j=0}^{m} \binom{m}{j} ∑_{i=0}^{N−1} i^{m+j}

= ∑_{j=0}^{m} \frac{1}{m + j + 1}\binom{m}{j} ∑_{k=0}^{m+j} \binom{m + j + 1}{k}B_{k}N^{m+j+1−k}

= ∑_{k=1}^{2m+1} N^{k} (∑_{j=0}^{m} \frac{1}{m + j + 1}\binom{m}{j}\binom{m + j + 1}{k}B_{m+j+1−k}) .

Therefore,

λ_{m,i} = \frac{1}{2^{m}} ∑_{j≥m−2i}^{m} \frac{1}{m + j + 1}\binom{m}{j}\binom{m + j + 1}{2m − 2i + 1}B_{j+2i−m}

= \frac{1}{2^{m}} ∑_{k=0}^{2i} \frac{1}{2m − 2i + k + 1}\binom{m}{m + k − 2i}\binom{2m − 2i + k + 1}{k}B_{k}

= \frac{1}{2^{m}(2m − 2i + 1)} ∑_{k=0}^{2i} \binom{m}{2i − k}\binom{2m − 2i + k}{k}B_{k}.

6.3 The polynomial part of \overline{F}_{i}(m)

Let us consider the function h̃_{i}(m) defined as

h̃_{i}(m) = (−1)^{i}(i + 1)(2m − 2i + 1)\begin{matrix}\overline{F} & i & (m) \\ ( & {m \atop i} & ) \end{matrix} = (−1)^{i}(i + 1) ∑_{k=0}^{2i} \begin{matrix}\binom{m}{2i−k} & \binom{2m−2i+k}{k} \\ ( & {m \atop i} & ) \end{matrix}B_{k}.

In fact, h̃_{i}(m) = h_{i}(m)/(i + 1)!, where h_{i}(m) is defined in relation (B3).

For example, h̃_{0}(m) = 1,

h̃_{1}(m) = \frac{m + 1}{3},

h̃_{2}(m) = \frac{1}{60}(7m − 6)(m + 1),

h̃_{3}(m) = \frac{(m + 1)(31m^{2} − 97m + 60)}{630},

h̃_{4}(m) = \frac{(m + 1)(127m^{3} − 833m^{2} + 1606m − 840)}{5040}.

Analogous to Knuth’s relation (A3), polynomial parts of \overline{F}_{i}(m) are interesting by themselves. Below we study properties of h̃_{i}(x).

Theorem 29. Let i ≥ 0.

(I) The function h̃_{i}(x) is a polynomial of degree i. (II) The following formula holds for h̃_{i}(m)

h̃_{i}(m)  (11)

= (−1)^{i}(i + 1) (∑_{k=0}^{i} \begin{matrix}\binom{m−i}{i−k} & \binom{2m−2i+k}{k} \\ ( & {2i−k \atop i} & ) \end{matrix}B_{k} + ∑_{k=i+1}^{2i} \begin{matrix}\binom{i}{k−i} & \binom{2m−2i+k}{k} \\ ( & {m−2i+k \atop k−i} & ) \end{matrix}B_{k})

= (−1)^{i} \frac{(i + 1)!}{(2i)!} (∑_{k=0}^{i} p_{k}(m)\binom{2i}{k}B_{k} + ∑_{k=i+1}^{2i} q_{k}(m)\binom{2i}{k}B_{k}) .

Here, p_{k}(m), q_{k}(m) are polynomials given by

p_{k}(m) = (m − i) ⋯ (m − 2i + k + 1)(2m − 2i + k) ⋯ (2m − 2i + 1)

and

q_{k}(m) = \frac{(2m − 2i + k) ⋯ (2m − 2i + 1)}{(m − 2i + k) ⋯ (m − i + 1)}
= 2^{k−i}(2m − 2i + 1)(2m − 2i + 3) ⋯
× (2m − 4i + 2k + 1) … (2m − 2i + k).

(If k = 2i, the last term (2m − 2i + k) in the product of q_{k}(m) is cancelled).

(III) The following recurrence relation holds for h̃_{i}(x)

(2i + 1 − 2x)h̃_{i}(x) = \frac{1}{2}(i + 1)h̃_{i−1}(x − 2) − (2x − 1)h̃_{i}(x − 1).  (12)

(IV) The initial value for h̃_{i}(x) is given by:

h̃_{i}(0) = (−1)^{i}(i + 1)B_{2i}.  (13)

(V) If x approaches ∞, then

h̃_{i}(x) ∼ (−1)^{i} \frac{(i + 1)!}{(2i)!}(2 − 2^{2i})B_{2i}x^{i}.  (14)

(VI) If i > 0, then all zeros of the polynomial h̃_{i}(x) are real. Moreover, it has one negative zero x_{0} = −1 and if i > 1, the other i − 1 zeros x_{1}, …, x_{i−1} are positive, distinct and satisfy the following inequalities

0 < x_{1} < 1, 2 < x_{2} < 3, 3 < x_{3} < 4, …, i − 1 < x_{i−1} < i.

Proof. (I) Note that the terms \binom{m}{2i−k} and \binom{2m−2i+k}{k} are polynomials in m of degree 2i − k and k respectively. Hence, \binom{m}{2i−k}\binom{2m−2i+k}{k} is a polynomial of degree 2i and it vanishes at m = 0, 1, …, i − 1 (if i > 0). This means that it is divisible by m(m − 1) ⋯ (m − i + 1) or

\binom{m}{i}. So, \begin{matrix}\binom{m}{2i−k} & \binom{2m−2i+k}{k} \\ ( & {m \atop i} & ) \end{matrix} is a polynomial in m of degree i. Therefore, h̃_{i}(m) is a polynomial in

m of degree i.

(II) To prove (11), we have

h̃_{i}(m) = (−1)^{i}(i + 1) ∑_{k=0}^{2i} \begin{matrix}\binom{m}{2i−k} & \binom{2m−2i+k}{k} \\ ( & {m \atop i} & ) \end{matrix}B_{k}

= (−1)^{i}(i + 1) ∑_{k=0}^{2i} \frac{i!(m − i)!}{(2i − k)!(m − 2i + k)!}\binom{2m − 2i + k}{k}B_{k}

= (−1)^{i}(i + 1) (∑_{k=0}^{i} \begin{matrix}\binom{m−i}{i−k} & \binom{2m−2i+k}{k} \\ ( & {2i−k \atop i} & ) \end{matrix}B_{k} + ∑_{k=i+1}^{2i} \begin{matrix}\binom{i}{k−i} & \binom{2m−2i+k}{k} \\ ( & {m−2i+k \atop k−i} & ) \end{matrix}B_{k})

= (−1)^{i}(i + 1) ∑_{k=0}^{i} \frac{(m − i) ⋯ (m − 2i + k + 1)(2m − 2i + k) ⋯ (2m − 2i + 1)i!}{k!(2i − k)!}B_{k}

+ (−1)^{i}(i + 1) ∑_{k=i+1}^{2i} \frac{i!(2m − 2i + k) ⋯ (2m − 2i + 1)}{k!(2i − k)!(m − 2i + k) ⋯ (m − i + 1)}B_{k}

= (−1)^{i} \frac{(i + 1)!}{(2i)!} (∑_{k=0}^{i} p_{k}(m)\binom{2i}{k}B_{k} + ∑_{k=i+1}^{2i} q_{k}(m)\binom{2i}{k}B_{k}) .

(III) We use (9) for x = m > i, where m is a positive integer. We obtain (12) for positive integers x = m > i. Since h̃_{i}(x) is a polynomial, recurrence relation (12) must hold for all real numbers x.

(IV) A substitution m = 0 in (11) gives us

h̃_{i}(0) = (−1)^{i}(i + 1) (∑_{k=0}^{i} \begin{matrix}\binom{−i}{i−k} & \binom{−2i+k}{k} \\ ( & {2i−k \atop i} & ) \end{matrix}B_{k} + ∑_{k=i+1}^{2i} \begin{matrix}\binom{i}{k−i} & \binom{−2i+k}{k} \\ ( & {−2i+k \atop k−i} & ) \end{matrix}B_{k})

= (−1)^{i}(i + 1) ∑_{k=0}^{2i} \frac{1}{2}\binom{2i}{k}B_{k} = (−1)^{i}(i + 1)B_{2i}.

Thus, (13) is proved.

(V) Let us calculate the leading coefficient A of h̃_{i}(m). By (11), we have

A = (−1)^{i} \frac{(i + 1)!}{(2i)!} ∑_{k=0}^{2i} 2^{k}\binom{2i}{k}B_{k}.

Let B_{n}(x) be the Bernoulli polynomial,

B_{n}(x) = ∑_{k=0}^{n} \binom{n}{k}B_{k}x^{n−k}.

It is well known that B_{n}(1/2) = (2^{1−n} − 1)B_{n}. Therefore,

A = (−1)^{i} \frac{(i + 1)!}{(2i)!}2^{2i} ∑_{k=0}^{2i}(1/2)^{2i−k}\binom{2i}{k}B_{k}

= (−1)^{i} \frac{(i + 1)!}{(2i)!}2^{2i}B_{2i}(1/2)

= (−1)^{i} \frac{(i + 1)!}{(2i)!}2^{2i}(2^{1−2i} − 1)B_{2i} = (−1)^{i} \frac{(i + 1)!}{(2i)!}(2 − 2^{2i})B_{2i},

which yields (14).

(VI) We have

h̃_{i}(−1) = (−1)^{i} \frac{(i + 1)}{\binom{−1}{i}} ∑_{k=0}^{2i} \binom{−1}{2i − k}\binom{−2 − 2i + k}{k}B_{k}

= (i + 1) ∑_{k=0}^{2i} \binom{2i + 1}{k}B_{k} = 0.

The part of the statement (VI) that relates to positive roots is evident for i = 2. Suppose that i ≥ 3.

Let sgn(x) = −1, if x < 0; sgn(x) = 0, if x = 0; and sgn(x) = 1, if x > 0.

Putting m = 1 in (12), we have

(2i − 1)h̃_{i}(1) = −h̃_{i}(0).

Equation (13) gives us

h̃_{i}(0) = (−1)^{i}(i + 1)B_{2i},  (15)

h̃_{i}(1) = (−1)^{i+1} \frac{i + 1}{2i − 1}B_{2i}.  (16)

Therefore,

sgn(h̃(0)) = − sgn(h̃(1)).

Hence, there exists a real zero x_{1} ∈ (0, 1) of h̃_{i}(x). Putting m = 2 in (12), by (15) and (16), we have

h̃_{i}(2) = \frac{1}{2i − 3} (\frac{1}{2}(−1)^{i−1}iB_{2i−2} + 3(−1)^{i} \frac{i + 1}{2i − 1}B_{2i}) .

By (3), for any positive integer i,

sgn(B_{2i}) = (−1)^{i+1}.

So,

sgn(h̃_{i}(2)) = sgn(h̃_{i}(1)).

Therefore, relation (12) for m = 3 gives

h̃_{i}(3) = \frac{1}{2i − 5} ((−1)^{i} \frac{11}{2} \frac{i}{2i − 3}B_{2i−2} + 3(−1)^{i+1} \frac{i + 1}{2i − 1}B_{2i}) .

Hence,

sgn(h̃(3)) = − sgn(h̃(2)).

Induction on i and on k shows that for any k ∈ [2, i]

sgn(h̃_{i}(k)) = (−1)^{i+k} sgn(B_{2i}).

As we discussed above, this relation is also true for k = 2, 3.

By inductive hypothesis,

sgn(h̃_{i}(k − 1)) = − sgn(h̃_{i−1}(k − 2)).

Recurrence relation (12) yields

sgn(h̃_{i}(k)) = sgn (\frac{1}{2i − 5} (\frac{1}{2}h̃_{i−1}(k − 2) − (2k − 1)h̃_{i}(k − 1)))
= sgn(h̃_{i−1}(k − 2) − h̃_{i}(k − 1))
= sgn((−1)^{i+k−3}B_{2i−2} − (−1)^{i+k−1}B_{2i})
= (−1)^{i+k} sgn(B_{2i}).

It remains to note that

sgn(h̃(2)) = − sgn(h̃(3)) = ⋯ = (−1)^{i−1} sgn(h̃(i − 1)) = (−1)^{i} sgn(h̃(i)).

7 Acknowledgments

We are grateful to the anonymous referee for careful reading the text and essential remarks.

References

[1] A. S. Dzhumadil’daev, Worpitzky identity for multipermutations, Mat. Zametki 90 (2011), 464–466.

[2] Johann Faulhaber, Academia Algebræ, Darinnen die miraculosische Inventiones zu den höchsten Cossen weiters continuirt und profitiert werden, Augsburg, bey Johann Ulrich Schönigs, 1631.

[3] I. M. Gessel and X. G. Viennot, Determinants, paths, and plane partitions, preprint, 1989.

[4] C. G. J. Jacobi, De usu legitimo formulae summatoriae Maclaurinianae, J. reine Angew. Math. 12 (1834), 263–272.

[5] D. Knuth, Johann Faulhaber and sums of powers, Math. Comp. 61 (1993), 277–294.

[6] T. Rivoal, La fonction zêta de Riemann prend une infinité de valeurs irrationnelles aux entiers impairs, C. R. Math. Acad. Sci. Paris 331 (2000), 267–270.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[8] A. Sofo, General properties involving reciprocals of binomial coefficients, J. Integer Seq. 9 (2006), Article 06.4.5.

[9] R. Sprugnoli, Sums of reciprocals of the central binomial coefficients, Integers 6 (2006), #A27.

[10] B. Sury, T. Wang, and F. Z. Zhao, Identities involving reciprocals of binomial coefficients, J. Integer Seq. 7 (2004), Article 04.2.8.

[11] J. H. Yang and F. Z. Zhao, Sums involving inverses of binomial coefficients, J. Integer Seq. 9 (2006), Article 06.4.2.

[12] W. Zudilin, One of the numbers ζ(5), ζ(7), ζ(9), ζ(11) is irrational, Uspekhi Mat. Nauk (Russian Math. Surveys) 56 (2001), 774–776.

2010 Mathematics Subject Classification: Primary 11B65; Secondary 11B68, 05A10. Keywords: binomial coefficient, Bernoulli number, Faulhaber’s theorem.

(Concerned with sequences \underline{A000217}, \underline{A008292}, \underline{A093556}, \underline{A093557}, \underline{A093558}, \underline{A093559}.)

Received May 12 2012; revised versions received October 7 2012; January 4 2013. Published in Journal of Integer Sequences, January 5 2013.

Return to Journal of Integer Sequences home page.