Congruences of Multiple Sums Involving Sequences Invariant Under the Binomial

Transform

Sandro Mattarei Dipartimento di Matematica

Università di Trento via Sommarive, 14 38100 Trento, Italy

mattarei@science.unitn.it

Roberto Tauraso Dipartimento di Matematica

Università di Roma “Tor Vergata”

via della Ricerca Scientifica

00133 Roma, Italy

tauraso@mat.uniroma2.it

Abstract

We prove several congruences modulo a power of a prime, such as

∑_{0<k_{1}<···<k_{n}<p} (\frac{p − k_{n}}{3})\frac{(−1)^{k_{n}}}{k_{1} ⋯ k_{n}} ≡ \begin{cases}−\frac{2^{n+1} + 2}{6^{n+1}} p B_{p−n−1} (1/3) (mod p^{2}), & if n is odd, \\ −\frac{2^{n+1} + 4}{n6^{n}} B_{p−n} (1/3) (mod p), & if n is even, \end{cases}

where n is a positive integer and p is a prime such that p > max(n + 1, 3).

1 Introduction

The classical binomial inversion formula states that the linear transformation of sequences

T (\{a_{n}\}) = \{∑_{k=0}^{n} \binom{n}{k}(−1)^{k}a_{k}\}

is an involution, which means that T ∘ T is the identity map. Thus, T can only have two eigenvalues: 1 and −1. Denote by S_{+} and S_{−} the eigenspaces corresponding to the eigenvalue 1 and to the eigenvalue −1. These eigenspaces contain many well-known sequences, among which are

\{2, 1, 1, 1, …\}, \{2^{−n}\}, \{L_{n}\}, \{(−1)^{n}B_{n}\}, \{1/(n + 1)\}, \{\binom{2n}{n}4^{−n}\} ∈ S_{+},

\{0, 1, 1, 1, …\}, \{2^{n} − (−1)^{n}\}, \{F_{n}\}, \{(−1)^{n}(\frac{n}{3})\} ∈ S_{−}.

Here {F_{n}}, {L_{n}}, {B_{n}} denote the Fibonacci, Lucas and Bernoulli numbers. For a more detailed analysis of the properties of S_{+} and S_{−} we refer the reader to the papers of Sun [3] and Wang [6]. From now on we will use the subscript k rather than the more traditional n, which takes another meaning here.

In this note we present several congruences of multiple harmonic sums with coefficients involving these invariant sequences. Our main result is the following.

Theorem 1.1. Let n be a positive integer, and let p be a prime such that p > n+1. Suppose that either n is odd and {a_{k}} ∈ S_{−}, or n is even and {a_{k}} ∈ S_{+}. Then

∑_{0<k_{1}<···<k_{n}<p} \frac{a_{p−k_{n}} − a_{0}/2}{k_{1} ⋯ k_{n}} ≡ \frac{p(n + 1)}{2} ∑_{0<k_{1}<···<k_{n+1}<p} \frac{a_{p−k_{n+1}} − a_{0}/2}{k_{1} ⋯ k_{n+1}} (mod p^{3}).

The term a_{0}/2 in the congruence is immaterial when n is odd, because all sequences in S_{−} satisfy a_{0} = 0. Note that in the extremal case n = p−2, whence n is odd, the congruence is actually an equality, because a_{1} = a_{2} for {a_{k}} ∈ S_{−} and

∑_{0<k_{1}<···<k_{p−2}<p} \frac{a_{p−k_{p−2}}}{k_{1} ⋯ k_{p−2}} = \frac{a_{1}}{(p − 1)!} ∑_{0<k<p} k = \frac{p(p − 1)}{2} · \frac{a_{1}}{(p − 1)!}.

The following result is an immediate application of Theorem 1.1 and, in case n is even, the simple fact that ∑_{0<k_{1}<···<k_{n}<p} 1/(k_{1} ⋯ k_{n}) ≡ 0 (mod p) for p > n + 1.

Corollary 1.2. Let n be a positive integer, and let p be a prime such that p > n+1. Suppose that {a_{k}} ∈ S_{−} if n is odd, and that {a_{k}} ∈ S_{+} if n is even. Then

∑_{0<k_{1}<···<k_{n}<p} \frac{a_{k_{1}}}{k_{1} ⋯ k_{n}} ≡ − ∑_{0<k_{1}<···<k_{n}<p} \frac{a_{p−k_{n}}}{k_{1} ⋯ k_{n}} ≡ 0 (mod p).

The first congruence in Corollary 1.2 is obtained by applying the simultaneous substitution k_{i} ↦ p − k_{n+1−i} to the summation indices, and so our real contribution is the second congruence. That congruence was proved by Zhao and Sun [7] for the special case of the sequence \{a_{k}\} = \{(−1)^{k}(\frac{k}{3})\} ∈ S_{−} and, in a different but essentially equivalent form, of the sequence \{a_{k}\} = \{(−1)^{k} ((\frac{k+1}{3}) − (\frac{k−1}{3}))\} ∈ S_{+}. The method used by Zhao and Sun [7] can easily be adapted to deduce the validity of Corollary 1.2 for all sequences in S_{±} which satisfy a second-order linear recurrence, but our proof does not need this restriction.

In Section 3 we prove a polynomial congruence, stated in Lemma 3.2, which reduces the evaluation modulo p of multiple harmonic sums (with coefficients, such as those involved in the above results) to certain single sums. We show that another polynomial congruence, which is the crucial result of Zhao and Sun [7], can be easily deduced from ours. However, our congruence is more versatile, and we exploit it in the final section together with Theorem 1.1 to prove the congruences involving Bernoulli numbers stated in the abstract, and another matching pair of congruences with the parity of n reversed. These congruences both refine (modulo p^{2}) and complement (covering the case where n has the opposite parity) the congruences proved by Zhao and Sun [7].

In the final Section 4, after determining all sequences in S_{±} which are (eventually) periodic, we use Theorem 1.1 and the tools developed in Section 3 to prove the pair of congruences stated in the abstract, and a naturally matching pair of congruences.

2 Proof of Theorem 1.1

For the reader’s benefit we recall some general information on the binomial transform. Of course this can also be found in various sources, including papers of Prodinger, Sun and Wang [2, 3, 6]. If A(x) = ∑_{k≥0} a_{k}x^{k} is the ordinary generating function of the sequence {a_{k}}, then it is easy to see that its binomial transform T ({a_{k}}) has generating sequence \frac{1}{1−x}A (\frac{x}{x−1}), and so \{a_{k}\} ∈ S_{±} if and only if

\frac{1}{1 − x}A (\frac{x}{x − 1}) = ±A(x).  (2.1)

After applying the substitution x = 2y/(y −1) this condition takes the more symmetric form

\frac{1}{1 − y} A (\frac{−2y}{1 − y} ) = ±\frac{1}{1 + y} A (\frac{2y}{1 + y} ) .

The left-hand side of this equation is the generating function of an associated sequence {b_{k}}=T ({2^{k}a_{k}}), the binomial transform of {2^{k}a_{k}}. We conclude that {a_{k}} ∈ S_{±} occurs exactly when that generating sequence is an even or an odd function, respectively. Equivalently, {a_{k}} ∈ S_{±} occurs if and only if all odd-numbered terms b_{2k+1}, respectively all even-numbered terms b_{2k}, of the associated sequence, vanish. This statement is an equivalent formulation of a result of Sun [3, Corollary 3.3], but the above proof avoids use of exponential generating functions, which was made by Sun [3] after a suggestion of Prodinger [2].

After these preliminaries, our starting point is the following identity.

Lemma 2.1. If {a_{k}} ∈ S_{±}, then for m, n ≥ 0 we have

∑_{k=0}^{n} [\binom{(m − 1)n + k − 1}{k} ± (−1)^{n−k}\binom{mn}{k}] a_{n−k} = 0,

where the sign is taken accordingly.

Proof. The result can be obtained by taking f_{k} = \binom{(m−1)n+k−1}{k}/\binom{n}{k} in the more general identity

∑_{k=0}^{n} \binom{n}{k} [f_{k} ± (−1)^{n−k} ∑_{i=0}^{k} \binom{k}{i}f_{i}] a_{n−k} = 0,

which holds for an arbitrary sequence {f_{k}} ∈ S_{±}, with sign in accordance, and was proved by Sun [3, Theorem 4.1] by means of exponential generating functions (see also the paper of Wang [6]). To make this paper self-contained we give a direct proof. Denote by [x^{k}]f(x) the coefficient of x^{k} in the Laurent series f(x). Because

\binom{(m − 1)n + k − 1}{k} = [x^{k}]\frac{1}{(1 − x)^{(m−1)n}} = [x^{−1}]\frac{1}{x^{n+1}(1 − x)^{(m−1)n}} · x^{n−k}

and

(−1)^{n−k}\binom{mn}{k} = [x^{k}]\frac{(−1)^{n−k}}{(1 − x)^{mn−k+1}} = [x^{−1}]\frac{1}{x^{n+1}(1 − x)^{(m−1)n+1}} · (\frac{x}{x − 1})^{n−k} ,

the left-hand side of the desired identity equals

[x^{−1}]\frac{1}{x^{n+1}(1 − x)^{(m−1)n}} · [A(x) ± \frac{1}{1 − x}A (\frac{x}{x − 1})] ,

where A(x) = ∑_{k≥0} a_{k}x^{k} is the generating function of the sequence {a_{k}}. The conclusion now follows from Equation (2.1).

We define the multiple harmonic sums of order n as

H_{r}^{(n)} = ∑_{0<k_{1}<k_{2}<···<k_{n}≤r} \frac{1}{k_{1}k_{2} ⋯ k_{n}} ,

for 0 < n ≤ r. Interpreting the summation as ranging over the subsets of {1, …, r} of cardinality n, it is natural and convenient to extend the definition to include order zero by setting H_{r}^{(0)} = 1 for r ≥ 0, and to stipulate that the sum vanishes unless 0 ≤ n ≤ r. All congruences modulo powers of p in this paper should be read in the ring of p-adic integers, thus admitting denominators prime to p.

Proof of Theorem 1.1. Assume first that n is odd and {a_{k}} ∈ S_{−}, where the proof is slightly simpler. Because a_{0} = 0 and p is odd, according to Lemma 2.1 we have

∑_{k=1}^{p−1} [\binom{(m − 1)p + k − 1}{k} − (−1)^{k}\binom{mp}{k}] a_{p−k} = 0.

By expanding the binomial coefficients for 0 < k < p we find

\binom{(m − 1)p + k − 1}{k} = \frac{(m − 1)p}{k} ∏_{i=1}^{k−1} (1 + \frac{(m − 1)p}{i}) = \frac{1}{k} ∑_{j≥1}((m − 1)p)^{j}H_{k−1}^{(j−1)},

and

\binom{mp}{k} = \frac{mp}{k}(−1)^{k−1} ∏_{i=1}^{k−1} (1 − \frac{mp}{i}) = \frac{(−1)^{k}}{k} ∑_{j≥1}(−mp)^{j}H_{k−1}^{(j−1)}.

Consequently, the numbers S_{j} = ∑_{k=1}^{p−1} H_{k−1}^{(j−1)}a_{p−k}/k satisfy

∑_{j≥1}((m − 1)^{j} − (−m)^{j}) p^{j}S_{j} = 0

for all nonnegative integers m. Note that S_{j} = 0 unless 1 ≤ j ≤ p. Setting f(x) = ∑_{j=1}^{p} p^{j}S_{j}(−x)^{j}, the above relations show that the polynomial f(1 − x) − f(x) vanishes for infinitely many values of x, and hence is the zero polynomial. After a translation, it follows that f(1/2 − x) − f(1/2 + x) is the zero polynomial. This means that the polynomial f(1/2 − x) is invariant under the substitution x ↦ −x, hence it is an even polynomial, and so the coefficents of odd powers of x vanish. By expanding

f (1/2 − x) = ∑_{j≥1} p^{j}S_{j} ∑_{n} \binom{j}{n}(1/2)^{j−n}(−x)^{n} = ∑_{n} (∑_{j≥n} 2^{n−j}p^{j}S_{j}\binom{j}{n}) (−x)^{n},

for each odd n we obtain the congruence

p^{n}S_{n} − \frac{1}{2}p^{n+1}(n + 1)S_{n+1} + \frac{1}{4}p^{n+2}\binom{n + 2}{2}S_{n+2} ≡ 0 (mod p^{n+3}).

It follows, in particular, that S_{n} ≡ 0 (mod p) for each odd n, and hence S_{n+2} ≡ 0 (mod p) as well. Using this and the original congruence we conclude that 2S_{n} ≡ p(n+1)S_{n+1} (mod p^{3}), which is the desired conclusion.

Now consider the case where n is even and {a_{k}} ∈ S_{+}. Here Lemma 2.1 yields

∑_{k=1}^{p−1} [\binom{(m − 1)p + k − 1}{k} + (−1)^{k}\binom{mp}{k}] a_{p−k} = −2a_{p} + \frac{1}{m}\binom{mp}{p}a_{0}.

Expanding the binomial coefficients as in the first part of the proof we see that the numbers S_{j} = ∑_{k=1}^{p−1} H_{k−1}^{(j−1)}a_{p−k}/k satisfy

∑_{j≥1}((m − 1)^{j} + (−m)^{j}) p^{j}S_{j} = −2a_{p} + \frac{1}{m}\binom{mp}{p}a_{0}

for all nonnegative integers m. Now consider the polynomial

g(x) = f(x) + a_{p} − \frac{a_{0}}{2} \binom{xp − 1}{p − 1} = ∑_{j=1}^{p} p^{j}S_{j}(−x)^{j} + a_{p} − \frac{a_{0}}{2} \binom{xp − 1}{p − 1}.

Note that \binom{xp−1}{p−1} = \binom{xp}{p}/x is a polynomial of degree p − 1, and is invariant under the substitution x ↦ 1 − x. Therefore, the relations found imply that g(x) + g(1 − x) vanishes for infinitely many values of x. Hence g(x) + g(1 − x) is the zero polynomial, and hence so is g(1/2 + x) + g(1/2 − x). This means that the polynomial g(x + 1/2) is an odd polynomial, and so the coefficents of even powers of x vanish. Arguing as in the proof of part (i), for each even n > 0 we obtain the congruence

p^{n}S_{n} − \frac{1}{2}p^{n+1}(n + 1)S_{n+1} + \frac{1}{4}p^{n+2}\binom{n + 2}{2}S_{n+2} ≡ [x^{n}] \frac{a_{0}}{2} \binom{(x + 1/2)p − 1}{p − 1} (mod p^{n+3}).

Because the right-hand side of this congruence depends only on the initial term a_{0} of our sequence, we can compute it by considering the special sequence a_{k} = (a_{0}/2)·{2, 1, 1, 1, …} ∈ S_{+}. In this case we have S_{n} = (a_{0}/2)H_{p−1}^{(n)}, which is easily seen to vanish modulo p as soon as p > n + 1, for example by setting x = 1 in Lemma 3.2 of the next section. We conclude that

S_{n} − \frac{1}{2}p(n + 1)S_{n+1} ≡ \frac{a_{0}}{2} H_{p−1}^{(n)} − \frac{a_{0}}{4} p(n + 1)H_{p−1}^{(n+1)} (mod p^{3}),

for an arbitrary sequence {a_{k}} ∈ S_{+}.

3 Some polynomial congruences

The main result of this section is Lemma 3.2, which shows that certain sums involving higher order harmonic numbers are equivalent modulo p to other sums which are easier to handle. We first need a preliminary result.

Lemma 3.1. For a positive integer m, the identity

∑_{0≤k<m} \binom{y}{k}(−x)^{k} = 1 + ∑_{n>0}(−y)^{n} ∑_{0<k<m} H_{k−1}^{(n−1)} \frac{x^{k}}{k}

holds in the polynomial ring ℚ[x, y] in two indeterminates.

Proof. For k > 0, by expanding

\binom{y}{k} = \frac{y}{k} \binom{y − 1}{k − 1} = \frac{(−1)^{k−1}y}{k} ∏_{0<i<k} (1 − \frac{y}{i} )

we see that the coefficient of y^{n} in the polynomial without constant term \binom{y}{k} equals

\frac{(−1)^{k+n}}{k} ∑_{0<i_{1}<···<i_{n−1}<k} \frac{1}{i_{1} ⋯ i_{n−1}} = \frac{(−1)^{k+n}}{k} H_{k−1}^{(n−1)},

properly interpreted to equal (−1)^{k−1}/k when n = 1 (because the sum has a unique term, which is an empty product), and to vanish when n > k (because the sum is empty). The desired conclusion follows.

Lemma 3.2. Let n be a positive integer and let p be a prime with p > n + 1. Then we have the polynomial congruence

∑_{k=1}^{p−1} H_{k−1}^{(n−1)} \frac{x^{k}}{k} ≡ (−1)^{n−1} ∑_{k=1}^{p−1} \frac{(1 − x)^{k}}{k^{n}} (mod p).  (3.1)

The case n = 1 of Lemma 3.2 is well known and due to the fact that in this case the lefthand side is congruent modulo p to the polynomial (1 − x^{p} − (1 − x)^{p})/p, which is invariant under the substitution x ↦ 1 − x. The general case can be proved by induction starting from this special case or, more directly and perhaps more insightfully, as follows.

Proof. The left-hand side of the identity of Lemma 3.1 may be viewed as a polynomial in the indeterminate y over the field of rational functions ℚ(x) (the field of quotients of ℚ[x]). Because of the binomial expansion, it takes the same values as the function y ↦ (1 − x)^{y} when evaluated for y = 0, …, m−1. Furthermore, having degree less than m it is completely determined by those values, for example through Lagrange’s interpolation formula.

Over a field E of characteristic p, and with m = p, Lagrange’s interpolation formula takes a particularly nice shape: for any polynomial f(y) ∈ E[y] of degree less than p we have

f(y) = f(0)(1 − y^{p−1}) − ∑_{n=1}^{p−1} y^{n} ∑_{k∈𝔽_{p}^{∗}} f(k)k^{−n}.

In this special case the use of Lagrange’s interpolation formula can be replaced by direct verification: geometric summation shows that the polynomial ∑_{n=1}^{p−1}(y/k)^{n} takes the value −1 for y = k, and vanishes on the remaining elements of 𝔽_{p}.

By taking as f the left-hand side of the identity of Lemma 3.1, with m = p, viewed over the field E = 𝔽_{p}(x), we obtain

∑_{k=0}^{p−1} \binom{y}{k}(−x)^{k} = 1 − y^{p−1} − ∑_{n=1}^{p−1} y^{n} ∑_{k=1}^{p−1}(1 − x)^{k}/k^{n}

in the polynomial ring E[y]. The conclusion now follows from Lemma 3.1 by equating the coefficient of y^{n} in both sides of this identity, and rewriting the result as a congruence modulo p in the polynomial ring (ℚ(x))[y].

The polynomial at the right-hand side of congruence (3.1) has some obvious roots in the prime field 𝔽_{p} for all primes p > n + 1, namely, 0 and 1, and also 2 when n is even. This last fact occurs because the value modulo p of that polynomial at x = 2 is multiplied by (−1)^{n−1} when replacing the summation variable k with p − k. By evaluating congruence (3.1) on x = 1 we recover the basic fact that H_{p−1}^{(n)} ≡ 0 (mod p) for 0 < n < p − 1. Evaluation for x = 2 yields

∑_{0<k_{1}<···<k_{n}<p} \frac{2^{k_{n}}}{k_{1} ⋯ k_{n}} ≡ 0 (mod p)  (3.2)

for even n with 0 < n < p − 1. Equation (1.1) of Sun [5], which reads ∑_{0<k<p} H_{k}/(k2^{k}) ≡ 0 (mod p), follows from the special case n = 2 of our Equation (3.2) via the simple manipulation

∑_{0<j≤k<p} \frac{1}{jk2^{k}} = ∑_{0<j<p} \frac{1}{j} ∑_{0<k<p} \frac{1}{k2^{k}} − ∑_{0<k<j<p} \frac{1}{jk2^{k}} ≡ ∑_{0<j<k<p} \frac{1}{(p − j)(p − k)2^{p−k}} (mod p).

We can use Lemma 3.2 to give a direct, rather than inductive proof, of the following crucial result of Zhao and Sun [7, Theorem 1.2].

Corollary 3.3 (Zhao and Sun [7]). Let n be a positive integer and let p be a prime with p > n + 1. Then we have the polynomial congruence

∑_{0<k_{1}<···<k_{n}<p} \frac{(1 − x)^{k_{1}}}{k_{1} ⋯ k_{n}} ≡ (−1)^{n−1} ∑_{0<k_{1}<···<k_{n}<p} \frac{x^{k_{1}}}{k_{1} ⋯ k_{n}} (mod p).

Proof. After applying the simultaneous substitution k_{i} ↦ p − k_{n+1−i} to the summation variables, we invoke Lemma 3.2 with x^{−1} in place of x and obtain

∑_{0<k_{1}<···<k_{n}<p} \frac{x^{k_{1}}}{k_{1} ⋯ k_{n}} = ∑_{0<k_{1}<···<k_{n}<p} \frac{x^{p−k_{n}}}{(p − k_{1}) ⋯ (p − k_{n})}

≡ (−1)^{n}x^{p} ∑_{0<k_{1}<···<k_{n}<p} \frac{x^{−k_{n}}}{k_{1} ⋯ k_{n}}

≡ −x^{p} ∑_{k=1}^{p−1} \frac{(1 − x^{−1})^{k}}{k^{n}}

≡ − ∑_{k=1}^{p−1} \frac{(x − 1)^{k}x^{p−k}}{k^{n}} (mod p).

If we apply the substitution x ↦ 1 − x to this last polynomial we obtain

∑_{k=1}^{p−1} \frac{x^{k}(x − 1)^{p−k}}{k^{n}} = ∑_{k=1}^{p−1} \frac{x^{p−k}(x − 1)^{k}}{(p − k)^{n}} ≡ (−1)^{n} ∑_{k=1}^{p−1} \frac{(x − 1)^{k}x^{p−k}}{k^{n}} (mod p),

which equals (−1)^{n−1} times the original polynomial.

4 Sums with periodic coefficient sequences

In this final section we prove the pair of congruences stated in the abstract, and a naturally matching pair of congruences. They concern multiple sums such as those in Theorem 1.1 and Corollary 1.2, for special sequences {a_{k}} of coefficients, which are periodic of period six. The special significance of those sequences lies in the fact that, up to addition of multiples of the nearly constant sequences {(1 ± 1), 1, 1, 1, …} ∈ S_{±}, they are the only (eventually) periodic sequences in S_{±}. To prove this fact we start with some more general considerations on sequences in S_{±} with a rational generating function.

Several sequences {a_{k}} ∈ S_{±} of interest satisfy a linear recurrence. It is well known that a sequence {a_{k}} satisfies a linear recurrence exactly when its generating function A(x) = ∑_{k≥0} a_{k}x^{k} is a rational function. If {a_{k}} is any sequence with rational generating function A(x), then the generating function \frac{1}{1−x}A (\frac{x}{x−1}) of its binomial transform T (\{a_{k}\}) has a zero of multiplicity s (or a pole of multiplicity −s when s is negative) at ξ ∈ ℂ \ {1} if and only if A(x) has a zero of the same multiplicity s at ξ/(ξ − 1) = (1 − ξ^{−1})^{−1}. The case ξ = 1 is special, because the generating function of T ({a_{k}}) has a zero of multiplicity s at 1 if and only if A(x) has a zero of multiplicity s + 1 at ∞. Recall that the multiplicity of ∞ as a zero of a rational function is the difference of the degrees of its denominator and numerator. Because of Equation (2.1), it follows that if {a_{k}} ∈ S_{±} satisfies a linear recurrence, then the multiplicity of ξ ∈ ℂ \ {1} as a zero of its generating function A(x) equals the multiplicity of (1 − ξ^{−1})^{−1}, and the multiplicity of 1 is one less than the multiplicity of ∞.

Now consider a sequence {a_{k}} ∈ S_{±} which is eventually periodic, which means that it satisfies, from some point on, a linear recurrence a_{k+d} = a_{k} for some positive integer d. Then its generating function A(x) has the form f(x)/(1 − x^{d}), where f(x) is a polynomial, which has degree less than d exactly when the sequence is periodic from the start. Hence A(x) has only simple poles, and at complex roots of unity. However, the only roots of unity ξ such that ξ/(ξ − 1) is also a root of unity are the two primitive sixth roots of unity, which are the roots of the polynomial 1 − x + x^{2}. The discussion in the previous paragraph shows that the poles of A(x) can only occur at 1 and at the primitive sixth roots of unity. In particular, the sequence {a_{k}} can only have period 1 or 6. That discussion also shows that f(x) has degree at most d, with equality if and only if 1 is a pole of A(x). In terms of the sequence {a_{k}}, this means that if it is eventually periodic then either it is periodic from the start, or from its second term a_{1}. In connection with our work, note that the first term a_{0} of the sequence enters our Theorem 1.1 only in one case, and is immaterial in Corollary 1.2.

We can now determine all sequences {a_{k}} ∈ S_{±} which are eventually periodic. In fact, if such a sequence is not periodic from the start, it becomes so after adding to it a suitable multiple of the sequence {(1 ± 1), 1, 1, 1, …} ∈ S_{±}, with the effect of removing the pole at 1 from its generating function A(x). Therefore, it suffices to consider a fully periodic sequence {a_{k}}. Because the only poles of A(x) are simple, and at the primitive sixth roots of unity, we have A(x) = ((a_{1} − a_{0})x + a_{0})/(1 − x + x^{2}). Hence {a_{k}} has period exactly six, and a simple calculation shows that A(x) is a scalar multiple of

\frac{−x}{1 − x + x^{2}} = ∑_{k=0}^{∞}(−1)^{k}(\frac{k}{3})x^{k} = −x − x^{2} + x^{4} + x^{5} + ⋯

or

\frac{2 − x}{1 − x + x^{2}} = ∑_{k=0}^{∞}(−1)^{k} ((\frac{k + 1}{3}) − (\frac{k − 1}{3})) x^{k} = 2 + x − x^{2} − 2x^{3} − x^{4} + x^{5} + ⋯,

according as {a_{k}} belongs to S_{−} or S_{+}.

Now that we have shown the special significance of these sequences, we proceed to prove the pair of congruences stated in the abstract, and a matching pair of congruences.

Theorem 4.1. Let n be a positive integer and let p be a prime with p > max(n + 1, 3). Consider the sequence in S_{−} given by u_{k} = (−1)^{k}(\frac{k}{3}), and the sequence in S_{+} given by v_{k} = (−1)^{k} ((\frac{k+1}{3}) − (\frac{k−1}{3})). Let B_{m}(x) denote the Bernoulli polynomials. Then

∑_{0<k_{1}<···<k_{n}<p} \frac{u_{p−k_{n}}}{k_{1} ⋯ k_{n}} ≡ \begin{cases}\frac{2^{n} + 1}{3 · 6^{n}} p B_{p−n−1} (1/3) (mod p^{2}), & if n is odd, \\ \frac{2^{n+1} + 4}{n6^{n}} B_{p−n} (1/3) (mod p), & if n is even, \end{cases}

and

∑_{0<k_{1}<···<k_{n}<p} \frac{v_{p−k_{n}}}{k_{1} ⋯ k_{n}} ≡ \begin{cases}(\frac{(2^{n} − 1)(3^{n} − 1)}{2 · 6^{n}} − \frac{1}{n + 1}) p B_{p−n−1} (mod p^{2}), & if n is even, \\ \frac{(2^{n−1} − 1)(3^{n−1} − 1)}{n6^{n−1}} B_{p−n} (mod p), & if n is odd. \end{cases}

Proof. We first prove the former pair of congruences, starting with the case where n is even. Let ω be a complex primitive cubic root of unity, and note that (\frac{k}{3}) = (ω^{k}−ω^{−k})/(ω−ω^{−1}) for all k. Interpreting congruences modulo p in the ring ℤ[ω] of Eisenstein integers, Lemma 3.2 yields

∑_{k=1}^{p−1} H_{k−1}^{(n−1)} \frac{u_{p−k}}{k} = \frac{1}{ω − ω^{−1}} ((−ω)^{p} ∑_{k=1}^{p−1} H_{k−1}^{(n−1)} \frac{(−ω)^{−k}}{k} − (−ω)^{−p} ∑_{k=1}^{p−1} H_{k−1}^{(n−1)} \frac{(−ω)^{k}}{k} )

≡ \frac{(−1)^{n−1}}{ω − ω^{−1}} ((−ω)^{p} ∑_{k=1}^{p−1} \frac{(−ω)^{k}}{k^{n}} − (−ω)^{−p} ∑_{k=1}^{p−1} \frac{(−ω)^{−k}}{k^{n}} ) (mod p)

= − ∑_{k=1}^{p−1} \frac{u_{p+k}}{k^{n}} ,

where we have used the fact that 1 − (−ω)^{−1} = −ω, in the second passage. The coefficient −u_{p+k} of 1/k^{n} in the last formula takes the values 0, 1, 1, 0, −1, −1 according as p + k ≡ 0, 1, 2, 3, 4, 5 (mod 6). According to Sun [4, Lemma 2.1] combined with Fermat’s little theorem we have

∑_{\begin{matrix}0<k<p \\ k≡r (mod 6) \end{matrix}} \frac{1}{k^{n}} ≡ \frac{1}{n6^{n}} (B_{p−n} (\{\frac{r}{6}\}) − B_{p−n} (\{\frac{r − p}{6}\})) (mod p),

for any integer r, under our hypothesis that p > max(n + 1, 3). Here {t} = t − [t] denotes the fractional part of the real number t. All the values of the Bernoulli polynomials involved in this formula can be obtained from just one of them, using the fact that the Bernoulli polynomials satisfy the reflection property and the multiplication formula

B_{m}(1 − x) = (−1)^{m}B_{m}(x), and B_{m}(ax) = a^{m−1} ∑_{k=0}^{a−1} B_{m} (x + k/a) ,

for m, a > 0, see Ireland and Rosen [1, p. 248]. Thus, taking into account that p − n is odd we find

B_{p−n} (0) = B_{p−n} (1/2) = 0, B_{p−n} (2/3) = −B_{p−n} (1/3) ,
B_{p−n} (1/6) = −B_{p−n} (5/6) = (2^{n−(p−1)} + 1) B_{p−n} (1/3) .

Carrying out separate calculations according as p ≡ ±1 (mod 6), in both cases we obtain

− ∑_{k=1}^{p−1} \frac{u_{p−k}}{k^{n}} ≡ \frac{2^{n+1} + 4}{n6^{n}} B_{p−n} (1/3) (mod p),

which proves the case of our first pair of congruences where n is even. When n is odd, the congruence which we have just proved holds with n + 1 in place of n. Combining this with Theorem 1.1 we obtain

∑_{k=1}^{p−1} H_{k−1}^{(n−1)} \frac{u_{p−k}}{k} ≡ \frac{p(n + 1)}{2} ∑_{k=1}^{p−1} H_{k−1}^{(n)} \frac{u_{p−k}}{k} (mod p^{3})

≡ \frac{2^{n+1} + 2}{6^{n+1}} pB_{p−n−1} (1/3) (mod p^{2}),

which proves the other case of the first pair of congruences.

We deal with the second pair of congruences in an entirely similar manner, using the fact that (\frac{k+1}{3}) − (\frac{k−1}{3}) = ω^{k} + ω^{−k} for all k. Here −v_{p+k} takes the values −2, −1, 1, 2, 1, −1 according as p + k ≡ 0, 1, 2, 3, 4, 5 (mod 6). When n is odd, whence p − n is even, the values of the Bernoulli polynomial B_{p−n}(x) involved are

B_{p−n} (1/2) = (2^{n−(p−1)} − 1) B_{p−n}, B_{p−n} (1/3) = B_{p−n} (2/3) = \frac{3^{n−(p−1)} − 1}{2}B_{p−n},

B_{p−n} (1/6) = B_{p−n} (5/6) = \frac{6^{n−(p−1)} − 3^{n−(p−1)} − 2^{n−(p−1)} + 1}{2}B_{p−n},

all expressed in terms of the Bernoulli numbers B_{n} = B_{n}(0). Thus, when n is odd we find

∑_{k=1}^{p−1} H_{k−1}^{(n−1)} \frac{v_{p−k}}{k} ≡ − ∑_{k=1}^{p−1} \frac{v_{p+k}}{k^{n}} ≡ \frac{(2^{n−1} − 1)(3^{n−1} − 1)}{n6^{n−1}} B_{p−n} (mod p).

When n is even, this congruence holds with n + 1 in place of n. According to Zhou and Cai [8, Remark at p. 1332], for p > j + 2 we have

H_{p−1}^{(j)} ≡ \begin{cases}0 (mod p^{2}), & if j is odd, \\ −\frac{p}{j + 1} B_{p−j−1} (mod p^{2}), & if j is even. \end{cases}

In combination with Theorem 1.1, noting that v_{0} = 2, this yields

∑_{k=1}^{p−1} H_{k−1}^{(n−1)} \frac{v_{p−k}}{k} ≡ \frac{p(n + 1)}{2} ∑_{k=1}^{p−1} H_{k−1}^{(n)} \frac{v_{p−k}}{k} + H_{p−1}^{(n)} − \frac{p(n + 1)}{2}H_{p−1}^{(n+1)} (mod p^{3})

≡ \frac{p}{2} \frac{(2^{n} − 1)(3^{n} − 1)}{6^{n}} B_{p−n−1} − \frac{p}{n + 1} B_{p−n−1} (mod p^{2}),

as desired.

References

[1] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1990.

[2] H. Prodinger, Some information about the binomial transform, Fibonacci Quart. 32 (1994), 412–415.

[3] Z. H. Sun, Invariant sequences under binomial transformation, Fibonacci Quart. 39 (2001), 324–333.

[4] Z. H. Sun, Congruences involving Bernoulli polynomials, Discrete Math. 308 (2008), 71–112.

[5] Z. W. Sun, Arithmetic of harmonic numbers, preprint arXiv:math.NT/0911.4433v4.

[6] Y. Wang, Self-inverse sequences related to a binomial inverse pair, Fibonacci Quart. 43 (2005), 46–52.

[7] L. L. Zhao, Z. W. Sun, Some curious congruences modulo primes, J. Number Theory 130 (2010), 930–935.

[8] X. Zhou and T. Cai, A generalization of a curious congruence on harmonic sums, Proc. Amer. Math. Soc. 135 (2007), 1329–1333.

2000 Mathematics Subject Classification: Primary 11A07; Secondary 11B65, 05A10, 05A19. Keywords: binomial transform, multiple sum, congruence, Bernoulli polynomial.

Received November 5 2009; revised version received April 16 2010. Published in Journal of Integer Sequences, April 16 2010.

Return to Journal of Integer Sequences home page.