Séminaire Lotharingien de Combinatoire 63 (2010), Article B63g

NEW HARMONIC NUMBER IDENTITIES WITH APPLICATIONS

Roberto Tauraso

Dipartimento di Matematica Università di Roma “Tor Vergata”, Italy

                 e-mail: tauraso@mat.uniroma2.it
           WWW: http://www.mat.uniroma2.it/∼tauraso

Abstract. We determine the explicit formulas for the sum of products of homogeneous multiple harmonic sums ∑_{k=1}^{n} ∏_{j=1}^{r} H_{k}({1}^{λ_{j}}) when ∑_{j=1}^{r} λ_{j} ≤ 5. We apply these identities to the study of two congruences modulo a power of a prime.

1. Introduction

Let s = (s_{1}, s_{2}, …, s_{d}) be a vector whose entries are positive integers, and define the multiple harmonic sum (MHS for short) for n ≥ 0 by

H_{n}(s) = ∑_{1≤k_{1}<k_{2}<···<k_{d}≤n} \frac{1}{k_{1}^{s_{1}}k_{2}^{s_{2}} ⋯ k_{d}^{s_{d}}} .

We call d and |s| = ∑_{i=1}^{d} s_{i} its depth and its weight, respectively. This kind of sums have a long history, see for example [4], [12], and the references therein.

In this note we present an algorithmic procedure to determine a closed formula for

∑_{k=1}^{n} ∏_{j=1}^{m} H_{k}(s_{j})

involving products of MHS evaluated at n and of total weight less or equal to ∑_{j=1}^{n} |s_{j}|.

(i) The first step is to expand recursively any product H_{n}(s)H_{n}(t) as a non-negative integral combination of MHS of weight |s| + |t|:

H_{n}(s)H_{n}(t) = ∑_{r∈s t} H_{n}(r),

where s t is the so-called stuffle product (or quasi-shuffle product). If we consider the vectors s = (s_{1}, s′) and t = (t_{1}, t′) as words formed by concatenating their components then the stuffle product is recursively defined by

s ∅ = ∅ s = s, s t = s_{1}(s′ t) + t_{1}(s t′) + (s_{1} + t_{1})(s′ t′).

So, for example,

H_{n}(1)H_{n}(2, 3) = H_{n}(1, 2, 3) + H_{n}(2, 1, 3) + H_{n}(2, 3, 1) + H_{n}(2, 1 + 3) + H_{n}(1 + 2, 3).

2000 Mathematics Subject Classification. Primary 11A07 11B65; Secondary 05A10 05A19.

(ii) The second step is to sum over k any MHS by using recursively the following rule:

∑_{k=1}^{n} H_{k}(s) = ∑_{k=1}^{n} ∑_{j=1}^{k} \frac{H_{j−1}(s′)}{j^{s_{d}}} = ∑_{j=1}^{n} \frac{H_{j−1}(s′)}{j^{s_{d}}} ∑_{k=j}^{n} 1 = ∑_{j=1}^{n} \frac{H_{j−1}(s′)}{j^{s_{d}}}(n + 1 − j)

= (n + 1)H_{n}(s) − \{ \begin{matrix}H_{n}(s′, s_{d} − 1) & if s_{d} > 1 \\ ∑_{k=1}^{n} H_{k}(s′) − H_{n}(s′) & if s_{d} = 1 \end{matrix}

where s = (s′, s_{d}). It is easy to see that the MHS involved in the final formula have weight less than or equal to |s|.

(iii) The last step is to simplify the formula by collecting terms by using the stuffle product relations. This can be done in various ways and the choices depend on the application of the identity.

This procedure will be employed in the next section, and it will generate a number of identities. We give two applications of these identities (we hope that many more will come out in the future). The first is about the sum

∑_{k=0}^{n}(−1)^{ak}\binom{n}{k}^{a},

which seems to have a closed form only for very few values of the parameter a ∈ ℤ, namely for −1 ≤ a ≤ 3. In [2], Cai studied a related congruence by showing that for any a ∈ ℤ and any prime p ≥ 5

∑_{k=0}^{p−1}(−1)^{ak}\binom{p − 1}{k}^{a} ≡ \binom{ap − 2}{p − 1} (mod p^{4}).

Here we present the following extension (see also [5] and [3] for similar results):

Theorem 1.1. Let p > 5 be a prime. For any a ∈ ℤ, we have

∑_{k=0}^{p−1}(−1)^{ak}\binom{p − 1}{k}^{a} ≡ \frac{(a − 1)p}{ap − 1} (1 + \frac{a(a + 1)(3a − 2)}{6}p^{3}X_{p}) (mod p^{6}),

where X_{p} = \frac{B_{p−3}}{p−3} − \frac{B_{2p−4}}{4p−8} and B_{n} denotes the n-th Bernoulli number.

Moreover, by using the previous theorem for a = −2 we get the following corollary.

Corollary 1.2. For any prime p > 5, we have

∑_{k=1}^{p−1} \frac{1}{k}\binom{2k}{k} ≡ −\frac{16}{3}p^{2}X_{p} (mod p^{4}).

This improves the congruence modulo p^{3} contained in [9].

2. MHS: identities

By following the procedure introduced in the previous section, we find an explicit formula for any sum of products of homogeneous MHS like H_{k}({1}^{d}) up to total weight 5 ({1}^{d} means that the number 1 is repeated d times):

∑_{k=1}^{n} H_{k}(1) = (n + 1)H_{n}(1) − n ,  (1)

∑_{k=1}^{n} H_{k}({1}^{2}) = (n + 1)H_{n}({1}^{2}) − nH_{n}(1) + n ,  (2)

∑_{k=1}^{n} H_{k}^{2}(1) = (n + 1)H_{n}^{2}(1) − (2n + 1)H_{n}(1) + 2n ,  (3)

∑_{k=1}^{n} H_{k}(\{1\}^{3}) = (n + 1)H_{n}(\{1\}^{3}) + n (H_{n}(1) − \frac{1}{2}H_{n}^{2}(1)) + \frac{n}{2}H_{n}(2) − n ,  (4)

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

+ \frac{n + 1}{2}H_{n}(2) − 3n ,  (5)
∑_{k=1}^{n} H_{k}^{3}(1) = (n + 1)H_{n}^{3}(1) + (6n + 3) (H_{n}(1) − \frac{1}{2}H_{n}^{2}(1)) + \frac{1}{2}H_{n}(2) − 6n. (6)

It is interesting to note that the formulas for ∑_{k=1}^{n} H_{k}^{r}(1) when r = 1, 2, 3 appear as Entry 8 on page 94 in [1]. To illustrate the procedure, we show how to obtain (5).

By (i), we have

H_{k}(1)H_{k}({1}^{2}) = 3H_{k}({1}^{3}) + H_{k}(2, 1) + H_{k}(1, 2).

Moreover, by (ii), we obtain

∑_{k=1}^{n} H_{k}({1}^{3}) = (n + 1)H_{n}({1}^{3}) − nH_{n}({1}^{2}) + nH_{n}(1) − n ,

∑_{k=1}^{n} H_{k}(2, 1) = (n + 1)H_{n}(2, 1) − nH_{n}(2) + H_{n}(1) ,

∑_{k=1}^{n} H_{k}(1, 2) = (n + 1)H_{n}(1, 2) − H_{n}({1}^{2}).

Finally, since by (i), we have

H_{n}(1)H_{n}({1}^{2}) = 3H_{n}({1}^{3}) + H_{n}(2, 1) + H_{n}(1, 2) and 2H_{n}({1}^{2}) = H_{n}^{2}(1) − H_{n}(2),

by applying (iii), we easily get (5).

The formulas for the total weight being 4 and 5 are contained in Tables 1 and 2, respectively: the sum ∑_{k=1}^{n} f_{k} −(n+1)f_{n}, where f_{n} is an entry in the first row, is equal to the sum of the entries of the first column, each multiplied by the linear polynomial an + b contained in the intersection of the chosen row and column.

4 ROBERTO TAURASO

Table 1

∑_{k=1}^{n} f_{k} − (n + 1)f_{n} H_{n}({1}^{4}) H_{n}^{2}({1}^{2}) H_{n}(1)H_{n}({1}^{3}) H_{n}^{2}(1)H_{n}({1}^{2}) H_{n}^{4}(1)
∑_{k=1}^{3} \frac{(−1)^{k−1}}{k!} H_{n}^{k}(1)  −n  −6n − 2  −4n − 1  −12n − 5  −24n − 12
\frac{1}{2}H_{n}(2)  −n  −2n − 2  −2n − 1  −2n − 3  −4
\frac{1}{3}H_{n}(3)  −n  1  −n − 1  1  3
\frac{1}{2}H_{n}(1)H_{n}(2)  n  2n  2n + 1  2n + 1  0
H_{n}(1, 2)  0  1  0  1  2
n  1  6  4  12  24

Table 2

∑_{k=1}^{n} f_{k} − (n + 1)f_{n} H_{n}({1}^{5}) H_{n}(1)H_{n}({1}^{4}) H_{n}(1, 1)H_{n}({1}^{3}) H_{n}^{2}(1)H_{n}({1}^{3})
∑_{k=1}^{4} \frac{(−1)^{k−1}}{k!} H_{n}^{k}(1)  n  5n + 1  10n + 3  20n + 7
\frac{1}{2}H_{n}(2)  n  3n + 1  4n + 3  6n + 5
\frac{1}{3}H_{n}(3)  n  2n + 1  n  2n + 1
\frac{1}{2}H_{n}(1)H_{n}(2)  −n  −3n − 1  −4n − 1  −6n − 3
H_{n}(1, 2)  0  0  −1  −1
\frac{1}{4}H_{n}(4)  n  n + 1  −1  −1
\frac{1}{8}H_{n}^{2}(2)  −n  −(n + 1)  −(2n − 1)  1
\frac{1}{4}H_{n}^{2}(1)H_{n}(2)  n  3n + 1  4n + 1  6n + 3
\frac{1}{3}H_{n}(1)H_{n}(3)  −n  −2n − 1  −n  −2n − 1
H_{n}(1, 3)  0  0  0  0
H_{n}(1, 1, 2)  0  0  1  1
n  −1  −5  −10  −20

\begin{matrix}∑_{k=1}^{n} f_{k} − (n + 1)f_{n} & H_{n}(1)H_{n}^{2}(\{1\}^{2}) & H_{n}^{3}(1)H_{n}(\{1\}^{2}) & H_{n}^{5}(1) \\ ∑_{k=1}^{4} \frac{(−1)^{k−1}}{k!} H_{n}^{k}(1) & 30n + 12 & 60n + 27 & 120n + 60 \\ \frac{1}{2}H_{n}(2) & 6n + 8 & 6n + 13 & 20 \\ \frac{1}{3}H_{n}(3) & −3 & −6 & −15 \\ \frac{1}{2}H_{n}(1)H_{n}(2) & −6n − 2 & −6n − 3 & 0 \\ H_{n}(1, 2) & −3 & −5 & −10 \\ \frac{1}{4}H_{n}(4) & −2 & −3 & −4 \\ \frac{1}{8}H_{n}^{2}(2) & −2n + 4 & 9 & 20 \\ \frac{1}{4}H_{n}^{2}(1)H_{n}(2) & 6n + 2 & 6n + 3 & 0 \\ \frac{1}{3}H_{n}(1)H_{n}(3) & 0 & 0 & 0 \\ H_{n}(1, 3) & 1 & 2 & 5 \\ H_{n}(\{1\}^{2}, 2) & 3 & 5 & 10 \\ n & −30 & −60 & −120 \end{matrix}

3. MHS: congruences

Among the various known results about MHS modulo powers of a prime, the following ones will be crucial for us: for any prime p > 5, we have

H_{p−1}(1) ≡ 2p^{2}X_{p}  (mod p^{4}) ,
H_{p−1}(2) ≡ −4pX_{p}  (mod p^{3}) ,
H_{p−1}(3) ≡ 0  (mod p^{2}) ,
H_{p−1}(1, 2) ≡ −6X_{p}  (mod p^{2}) ,
H_{p−1}(4) ≡ H_{p−1}({1}^{2}, 2) ≡ H_{p−1}(1, 3) ≡ 0 (mod p),

where X_{p} = \frac{B_{p−3}}{p−3} − \frac{B_{2p−4}}{4p−8} (see [7] for the MHS of depth 1, see [12] and [4] for all the MHS of depth > 1 with the exception of H_{p−1}(1, 2) modulo p^{2} which has been established in [10]).

Note that every homogeneous MHS can be expressed in terms of MHS of depth 1. More precisely (see Theorem 2.3 in [4]): given a positive integer d, then for any unordered partition λ = {λ_{1}, λ_{2}, …, λ_{r}} of d there is some integer c_{λ} such that

d!H_{n}({1}^{d}) = ∑_{λ∈P (d)} c_{λ} ∏_{i=1}^{r} H_{n}(λ_{i}).

For example:

2H_{n}({1}^{2}) = H_{n}^{2}(1) − H_{n}(2) ,
6H_{n}({1}^{3}) = H_{n}^{3}(1) − 3H_{n}(1)H_{n}(2) + 2H_{n}(3) ,
24H_{n}({1}^{4}) = H_{n}^{4}(1) − 6H_{n}^{2}(1)H_{n}(2) + 8H_{n}(1)H_{n}(3) + 3H_{n}^{2}(2) − 6H_{n}(4).

Hence, for any prime p > 5, we have

H_{p−1}({1}^{2}) ≡ 2pX_{p} (mod p^{3}) ,
H_{p−1}({1}^{3}) ≡ 0  (mod p^{2}) ,
H_{p−1}({1}^{4}) ≡ 0  (mod p).

Therefore, by Equations (1)–(6), Tables 1 and 2, it follows that, for any prime p > 5, we have:

Table 3

∑_{k=1}^{p−1} H_{k}(1) ≡ −(p − 1) + 2p^{3}X_{p}  (mod p^{5})
∑_{k=1}^{p−1} H_{k}({1}^{2}) ≡ (p − 1) + (4 − 2p)p^{2}X_{p}  (mod p^{4})
∑_{k=1}^{p−1} H_{k}^{2}(1) ≡ 2(p − 1) + (2 − 4p)p^{2}X_{p}  (mod p^{4})
∑_{k=1}^{p−1} H_{k}({1}^{3}) ≡ −(p − 1) + (2 − 4p)pX_{p}  (mod p^{3})
∑_{k=1}^{p−1} H_{k}(1)H_{k}({1}^{2}) ≡ −3(p − 1) + (−6p)pX_{p}  (mod p^{3})
∑_{k=1}^{p−1} H_{k}^{3}(1) ≡ −6(p − 1) + (−2 − 6p)pX_{p}  (mod p^{3})
∑_{k=1}^{p−1} H_{k}({1}^{4}) ≡ (p − 1) + (−2p)X_{p}  (mod p^{2})
∑_{k=1}^{p−1} H_{k}^{2}({1}^{2}) ≡ 6(p − 1) + (−6)X_{p}  (mod p^{2})
∑_{k=1}^{p−1} H_{k}(1)H_{k}({1}^{3}) ≡ 4(p − 1) + (−2p)X_{p}  (mod p^{2})
∑_{k=1}^{p−1} H_{k}^{2}(1)H_{k}({1}^{2}) ≡ 12(p − 1) + (−6 + 2p)X_{p} (mod p^{2})
∑_{k=1}^{p−1} H_{k}^{4}(1) ≡ 24(p − 1) + (−12 + 8p)X_{p}  (mod p^{2})
∑_{k=1}^{p−1} H_{k}({1}^{5}) ≡ 1  (mod p)
∑_{k=1}^{p−1} H_{k}(1)H_{k}({1}^{4}) ≡ 5  (mod p)
∑_{k=1}^{p−1} H_{k}({1}^{2})H_{k}({1}^{3}) ≡ 10 + 6X_{p}  (mod p)
∑_{k=1}^{p−1} H_{k}^{2}(1)H_{k}({1}^{3}) ≡ 20 + 6X_{p}  (mod p)
∑_{k=1}^{p−1} H_{k}(1)H_{k}^{2}({1}^{2}) ≡ 30 + 18X_{p}  (mod p)
∑_{k=1}^{p−1} H_{k}^{3}(1)H_{k}({1}^{2}) ≡ 60 + 30X_{p}  (mod p)
∑_{k=1}^{p−1} H_{k}^{5}(1) ≡ 120 + 60X_{p}  (mod p)

Note that ∑_{k=1}^{p−1} H_{k}^{r}(1) (mod p^{4−r}) for r = 1, 2, 3 have been established by Z. W. Sun in [8].

4. Proof of Theorem 1.1 and Corollary 1.2

Proof of Theorem 1.1. Assume that p > 5 is a prime, then for k = 1, …, p − 1 we have that

(−1)^{k}\binom{p − 1}{k} = ∏_{j=1}^{k} (1 − \frac{p}{j}) ≡ 1 + ∑_{j=1}^{5}(−p)^{j}H_{k}(\{1\}^{j}) (mod p^{6}).

Hence we have

(−1)^{ak}\binom{p − 1}{k}^{a} ≡ 1+∑_{j=1}^{5}(−p)^{j} ∑_{r=1}^{j} \binom{a}{r} ∑_{λ∈P(j,r)} \binom{j}{λ_{1}, …, λ_{r}} ∏_{i=1}^{r} H_{k}(\{1\}^{λ_{i}}) (mod p^{6}),

where P(j, r) is the set of the integer partitions λ of j into r parts.

By summing over k, we find

∑_{k=0}^{p−1}(−1)^{ak}\binom{p − 1}{k}^{a} = p+∑_{j=1}^{5}(−p)^{j} ∑_{r=1}^{j} \binom{a}{r} ∑_{λ∈P(j,r)} \binom{j}{λ_{1}, …, λ_{r}} ∑_{k=1}^{p−1} ∏_{i=1}^{r} H_{k}(\{1\}^{λ_{i}}) (mod p^{6}).

Finally, by Table 3, we can compute

(−p)^{j} ∑_{k=1}^{p−1} ∏_{i=1}^{r} H_{k}({1}^{λ_{i}}) (mod p^{6})

for any partition λ ∈ P(j, r), and we get easily the result. □

Proof of Corollary 1.2. In [6] Staver proved that for any integer n ≥ 1

∑_{k=1}^{n} \frac{1}{k}\binom{2k}{k} = \binom{2n}{n}\frac{2n + 1}{3n^{2}} ∑_{k=0}^{n−1} \binom{n − 1}{k}^{−2}.

Letting n = p, by Theorem 1.1 for a = −2 we have

∑_{k=1}^{p−1} \frac{1}{k}\binom{2k}{k} = \frac{1}{p}\binom{2p}{p} (\frac{2p + 1}{3p} ∑_{k=0}^{p−1} \binom{p − 1}{k}^{−2} − 1)

≡ \frac{2}{p}\binom{2p − 1}{p − 1} ((1 − \frac{8}{3}p^{3}X_{p}) − 1) ≡ −\frac{16}{3}p^{2}X_{p} (mod p^{4}),

where in the last step we used the fact that \binom{2p−1}{p−1} ≡ 1 (mod p^{3}) by Wolstenholme’s theorem. □

References

[1] B. C. Berndt, Ramanujan’s Notebooks Part I, Springer-Verlag, New York, 1998.

[2] T. X. Cai, On the residues of binomial coefficients and their products modulo prime powers, Acta Math. Sin. (Engl. Ser.) 18 (2002), 277–288.

[3] M. Chamberland and K. Dilcher, Divisibility properties of a class of binomial sums, J. Number Theory 120 (2006), 349–371.

[4] M. Hoffman, Quasi-symmetric functions and mod p multiple harmonic sums, preprint arχiv:0401319 [math.NT] (2007)

[5] H. Pan, On a generalization of Carlitz’s congruence, Int. J. Mod. Math. 4 (2009), 87–93.

[6] T. B. Staver, Om summasjon av potenser av binomialkoeffisienten, Norsk Mat. Tidsskrift 29 (1947), 97–103.

[7] Z. H. Sun, Congruences concerning Bernoulli numbers and Bernoulli polynomials, Discrete Appl. Math. 105 (2000), 193–223.

[8] Z. W. Sun, Arithmetic theory of harmonic numbers, preprint arχiv:0911.4433 [math.NT] (2009).

[9] Z. W. Sun and R. Tauraso, New congruences for central binomial coefficients, Adv. in Appl. Math. 45 (2010), 125–148.

[10] R. Tauraso, More congruences for central binomial coefficients, to appear in J. Number Theory.

[11] R. Tauraso and J. Zhao, Congruences of alternating multiple harmonic sums, to appear in J. Combin. Number Theory.

8 ROBERTO TAURASO

[12] J. Zhao, Wolstenholme type theorem for multiple harmonic sums, Int. J. Number Theory 4 (2008), 73–106.