Congruences for a Class of Alternating Lacunary Sums of Binomial Coefficients

Karl Dilcher Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia B3H 3J5 Canada

                    dilcher@mathstat.dal.ca

Abstract

An 1876 theorem of Hermite, later extended by Bachmann, gives congruences modulo primes for lacunary sums over the rows of Pascal’s triangle. This paper gives an analogous result for alternating sums over a certain class of rows. The proof makes use of properties of certain linear recurrences.

1 Introduction

Given the importance of binomial coefficients and combinatorial sums in many areas of mathematics, it is not surprising that divisibility properties and congruences of these combinatorial objects have been extensively studied. For instance, numerous older results can be found in Dickson’s History [2, Ch. IX], while a more modern treatment of the subject is given by Granville [4]. One such result is the following congruence due to Hermite [6] and, in the general case, Bachmann [1, p. 46].

Theorem 1 (Hermite and Bachmann). Let p be a prime and k a positive integer. Then

∑_{0<j(p−1)<k} \binom{k}{j(p − 1)} ≡ 0 (mod p).  (1)

Bachmann [1, p. 53] and before him Hermite [6] used this congruence to derive recurrence relations for the integer parts of Bernoulli numbers.

It is the purpose of this paper to derive an alternating sum analog to a special case of (1). This also has consequences in the theory of Bernoulli numbers and polynomials. In fact, a congruence for the alternating sum in the special case where k is a multiple of p − 1, given below as Corollary 1, is instrumental in a forthcoming study of possible multiple zeros of Bernoulli polynomials [3].

While the congruence (1) is not difficult to prove, the following main result of this paper requires considerably more effort.

Theorem 2. Let p be an odd prime and q a positive integer. Then

∑_{j=0}^{⌊q/2⌋} \binom{q(p − 1)}{2j(p − 1)} ≡ \begin{cases}1 (mod p), & if q odd; \\ 2 (mod p), & if q even, p + 1 ∤ q; \\ \frac{3}{2} (mod p), & if p + 1 | q. \end{cases}  (2)

In order to derive the desired congruence for an alternating sum, we first note that from (1) with k = q(p − 1) we immediately get

∑_{j=0}^{q} \binom{q(p − 1)}{j(p − 1)} ≡ 2 (mod p).  (3)

Then we use the obvious identity

∑_{j=0}^{q}(−1)^{j}\binom{q(p − 1)}{j(p − 1)} = − ∑_{j=0}^{q} \binom{q(p − 1)}{j(p − 1)} + 2 ∑_{j=0}^{⌊ \frac{q}{2} ⌋} \binom{q(p − 1)}{2j(p − 1)},

and (2) and (3) immediately give the following

Corollary 3. Let p be an odd prime and q a positive integer. Then

∑_{j=0}^{q}(−1)^{j}\binom{q(p − 1)}{j(p − 1)} ≡ \begin{cases}0 (mod p), & if q odd; \\ 2 (mod p), & if q even, p + 1 ∤ q; \\ 1 (mod p), & if p + 1 | q. \end{cases}  (4)

When q is odd, it follows by symmetry that this alternating sum vanishes; this also implies the first case in (2); the case where q is even is more difficult. The congruences (1), (2), and (4) have obvious interpretations in terms of lacunary sums of elements in certain rows of Pascal’s triangle.

In order to prove Theorem 2, we first derive a number of lemmas in Section 2, followed by the proof of the theorem in Section 3.

2 Auxiliary Results

We begin by stating the following classical divisibility and congruence results for binomial coefficients; see also [4].

Lemma 4. (a) (Kummer [8]) The exact power of the prime p which divides \binom{n}{m} is given by the number of “carries” when m and n − m are added in base p.

(b) (Lucas [9]) For all primes p and nonnegative integers n, k, a, b with 0 ≤ a, b < p we have

\binom{np + a}{kp + b} ≡ \binom{n}{k}\binom{a}{b} (mod p).  (5)

With these results we prove the following

Lemma 5. Let p be an odd prime and q, j integers with 2 ≤ q ≤ 2p and 1 ≤ j ≤ q − 1. Then

\binom{q(p − 1)}{j(p − 1)} ≡ \begin{cases}0 (mod p), & if q ≠ p + 1; \\ \binom{p−1}{j−1}^{2} (mod p), & if q = p + 1. \end{cases}  (6)

Proof. First, let 2 ≤ q ≤ p. Then we can write in base p,

(q − j)(p − 1) = (q − j − 1)p + (p − (q − j)), j(p − 1) = (j − 1)p + (p − j),

and we see that upon adding these two numbers we have one carry in base p, and we are done by Lemma 1(a).

When q ≥ p + 2, counting the carries would be more difficult, and we use instead Lucas’ result (5) in its iterated form, i.e., the result applied also to \binom{n}{k}. We write q = p + 1 + s with 1 ≤ s ≤ p − 1. Then clearly

q(p − 1) = p^{2} + (s − 1)p + (p − s − 1).  (7)

When 1 ≤ j ≤ p, we write j(p − 1) = (j − 1)p + (p − j), and with (5) and (7) we get

\binom{q(p − 1)}{j(p − 1)} ≡ \binom{1}{0}\binom{s − 1}{j − 1}\binom{p − s − 1}{p − j} ≡ 0 (mod p),

since either the second binomial coefficient on the right vanishes (when j > s), or the third one vanishes (when j ≤ s). Next, when j = p + 1, we have j(p − 1) = (p − 1)p + (p − 1), and

\binom{q(p − 1)}{(p + 1)(p − 1)} ≡ \binom{1}{0}\binom{s − 1}{p − 1}\binom{p − s − 1}{p − 1} ≡ 0 (mod p)

for similar reasons as above. Thirdly, when p + 2 ≤ j ≤ q − 1, we write j = p + 1 + t, 1 ≤ t < s. Then in base p we have j(p − 1) = p^{2} + (t − 1)p + (p − t − 1), and thus

\binom{q(p − 1)}{j(p − 1)} ≡ \binom{1}{1}\binom{s − 1}{t − 1}\binom{p − s − 1}{p − t − 1} ≡ 0 (mod p)

since the last binomial coefficient on the right vanishes. This proves (6) for q ≠ p + 1.

Finally, when q = p+1, we write q(p−1) = (p−1)p+(p−1) and j(p−1) = (j−1)p+(p−j) so that, again by (5),

\binom{(p + 1)(p − 1)}{j(p − 1)} ≡ \binom{p − 1}{j − 1}\binom{p − 1}{p − j} = \binom{p − 1}{j − 1}^{2} (mod p),

and this completes the proof of the lemma.

The next lemma is the central ingredient in the proof of Theorem 2. The proof uses a variant of a standard method.

Lemma 6. Let p be an odd prime and ζ a primitive (2p − 2)th root of unity. If we define

S_{p}(q) := ∑_{k=1}^{2p−2} (1 + ζ^{k})^{(p−1)q}  (8)

for q = 1, 2, …, then

S_{p}(q) = (2p − 2) ∑_{j=0}^{⌊q/2⌋} \binom{q(p − 1)}{2j(p − 1)}.  (9)

Proof. We use the well-known fact that

∑_{k=1}^{2p−2} ζ^{mk} = \begin{cases}0, & if 2p − 2 ∤ m; \\ 2p − 2, & if 2p − 2 | m. \end{cases}  (10)

Now, using a binomial expansion, we get with (8),

S_{p}(q) = ∑_{k=1}^{2p−2} ∑_{m=0}^{q(p−1)} \binom{q(p − 1)}{m} (ζ^{k})^{m}

= ∑_{m=0}^{q(p−1)} \binom{q(p − 1)}{m} ∑_{k=1}^{2p−2} ζ^{mk}.

The result now follows from (10).

By the theory of linear recurrence relations with constant coefficients we know from the right-hand side of (8) that for fixed p the sequence {S_{p}(q)}, q = 1, 2, …, is a linear recurrence sequence of order at most 2p − 2, and that the characteristic polynomial of this sequence has (1 + ζ^{k})^{p−1}, k = 1, 2, …, 2p − 2, as its roots. This motivates the following lemma.

Lemma 7. Let p be an odd prime and f_{p}(x) the unique monic polynomial that has the numbers (1 + ζ^{k})^{p−1}, k = 1, 2, …, 2p − 2, as its roots. Then

f_{p}(x) ≡ x ∑_{n=0}^{2p−3} a_{n}x^{2p−3−n} (mod p),  (11)

where for 0 ≤ n ≤ p − 2 we have

a_{n} ≡ \begin{cases}(m + 1)^{2}, (mod p) & if n = 2m; \\ (m + 1)(m + 2), (mod p) & if n = 2m + 1, \end{cases}  (12)

and for p − 1 ≤ n ≤ 2p − 3,

a_{n} ≡ −a_{2p−3−n} (mod p).  (13)

Remark. The expression in (12) can also be written more concisely as

a_{n} ≡ ⌊\frac{n+2}{2}⌋ ⌊\frac{n+3}{2}⌋ (mod p).

The right-hand side is the shifted sequence \underline{A002620} in [10]. Proof of Lemma 4. Using the well-known fact that (1 + x)^{p} ≡ 1 + x^{p} (mod p), we have

(1 + ζ^{j})^{p−1} = \frac{(1 + ζ^{j})^{p}}{1 + ζ^{j}} ≡ \frac{1 + ζ^{jp}}{1 + ζ^{j}} = \frac{1 + (ζ^{p−1})^{j}ζ^{j}}{1 + ζ^{j}} (mod p)

for i ≠ p − 1. Then, with ζ^{p−1} = −1, we have

(1 + ζ^{j})^{p−1} ≡ \begin{cases}1 (mod p), & if j even, j ≠ p − 1; \\ 0 (mod p), & if j = p − 1; \\ \frac{1−ζ^{j}}{1+ζ^{j}} (mod p), & if j odd. \end{cases}  (14)

Hence

f_{p}(x) ≡ x(x − 1)^{p−2} ∑_{j=0}^{p−2} (x − \frac{1 − ζ^{2j+1}}{1 + ζ^{2j+1}} ) (mod p).  (15)

First, using the expansion

\binom{p − 2}{k} = \frac{(p − 2)(p − 3) ⋯ (p − 2 − k + 1)}{1 · 2 ⋯ k} ≡ (−1)^{k}(k + 1) (mod p),  (16)

which can also be found in [2, p. 272], we have

(x − 1)^{p−2} = ∑_{k=0}^{p−2} \binom{p − 2}{k}(−1)^{k}x^{p−2−k} ≡ ∑_{k=0}^{p−2}(k + 1)x^{p−2−k} (mod p).  (17)

Next, if we set

x_{j} := \frac{1 − ζ^{2j+1}}{1 + ζ^{2j+1}}  (18)

and solve for ζ^{2j+1}, we get

ζ^{2j+1} = \frac{1 − x_{j}}{1 + x_{j}} ,

and by raising this to the (p − 1)th power, we see that the x_{j}, j = 0, 1, …, p − 2, are all the roots of the polynomial equation

(1 − x)^{p−1} = −(1 + x)^{p−1},

since ζ is a primitive (2p − 2)th root of unity. But since

∑_{j=0}^{\frac{p−1}{2}} \binom{p − 1}{2j}x^{2j} = \frac{(1 + x)^{p−1} + (1 − x)^{p−1}}{2} ,  (19)

we see that the expressions in (18) are exactly the zeros of the polynomials on the left of (19), and thus

∑_{j=0}^{p−2} (x − \frac{1 − ζ^{2j+1}}{1 + ζ^{2j+1}} ) = ∑_{j=0}^{\frac{p−1}{2}} \binom{p − 1}{2j}x^{2j} ≡ ∑_{j=0}^{\frac{p−1}{2}} x^{2j} (mod p),  (20)

where we have used the congruence \binom{p−1}{k} ≡ (−1)^{k} (mod p), which can be obtained as in (16), or see [2, p. 272]. If we define the sequence {δ_{j}} by δ_{j} = 1 when j is even and δ_{j} = 0 when j is odd, then the product of the polynomials in (17) and (20) becomes

∑_{n=0}^{2p−3} (∑_{k=0}^{n}(k + 1)δ_{n−k}) x^{2p−3−k} = ∑_{n=0}^{2p−3} a_{n}x^{2p−3−n},

where the inner sum is not usually taken over the whole range. In fact, it is easy to see that

a_{n} = ∑_{k=0}^{n}(k + 1)δ_{n−k} for 0 ≤ n ≤ p − 2,  (21)

and

a_{n} = ∑_{k=n−p+1}^{p−2}(k + 1)δ_{n−k} for p − 1 ≤ n ≤ 2p − 3.  (22)

Now, for n ≤ p − 2 we get from (21),

a_{2m} = ∑_{k=0}^{m}(2k + 1) = (m + 1)^{2},

a_{2m+1} = ∑_{k=1}^{m+1} 2k = (m + 1)(m + 2),

which is just (12). In (22) we shift the order of summation, to obtain

a_{n} = ∑_{k=0}^{2p−3−n}(k + n − p + 2)δ_{p−1−k} ≡ ∑_{k=0}^{2p−3−n}(k + n + 2)δ_{k} (mod p)

since p − 1 − k ≡ k (mod 2). Finally we reverse the order of summation, so that

a_{n} ≡ ∑_{k=0}^{2p−3−n}(2p − 3 − n − k + n + 2)δ_{(2p−3−n)−k}

≡ − ∑_{k=0}^{2p−3−n}(k + 1)δ_{(2p−3−n)−k} (mod p).

This, with (21), accounts for (13), which completes the proof of the lemma.

We are now ready to prove our main result.

3 Proof of Theorem 2

In view of Lemma 3 it suffices to determine the S_{p}(q), q = 1, 2, … We first find the initial values (mod p) of this sequence. By the first part of Lemma 2 we immediately get the first two parts of (2) for q ≤ 2p. By the second part of (6) we have for q = p + 1,

2 ∑_{j=0}^{⌊q/2⌋} \binom{q(p − 1)}{2j(p − 1)} ≡ 4 + 2 ∑_{j=1}^{\frac{p−1}{2}} \binom{p − 1}{2j − 1}^{2}  (23)

= 4 + \binom{2p − 2}{p − 1} − (−1)^{\frac{p−1}{2}} \binom{p − 1}{\frac{p−1}{2}} (mod p),

where we have used a well-known explicit formula; see, e.g., [5, Eq. (3.74)]. For the first binomial coefficient on the right we have, by (5),

\binom{2p − 2}{p − 1} = \binom{1 · p + (p − 2)}{0 · p + (p − 1)} ≡ \binom{1}{0}\binom{p − 2}{p − 1} = 0 (mod p),

and as a special case of a well-known theorem of Morley (see, e.g., [4] or [7, p. 105]) we have

(−1)^{\frac{p−1}{2}} \binom{p − 1}{\frac{p−1}{2}} ≡ 4^{p−1} ≡ 1 (mod p).

Hence with (23) we get the third part of (2) for q = p + 1. The identity (9) now immediately gives

S_{p}(q) ≡ \begin{cases}−2 (mod p), & if q odd; \\ −4 (mod p), & if q even, p + 1 ∤ q; \\ −3 (mod p), & if p + 1 | q; \end{cases}  (24)

for q ≤ 2p. It remains to show that (24) holds for all integers q ≥ 1.

We are done if we can show that the sequence {S_{p}(q)}_{q≥1}, as given in (24), satisfies (for all q) the recurrence relation (mod p) whose characteristic polynomial is given by (11); in other words, we need to show that

a_{0}S_{p}(n) + a_{1}S_{p}(n − 1) + … + a_{2p−3}S_{p}(n − 2p + 3) ≡ 0 (mod p)  (25)

for all n ≥ 2p−2, with the a_{j} as given in Lemma 4. We may obviously consider the sequence {−S_{p}(q)}, and since by (13) the coefficients a_{0}, a_{1}, …, a_{2p−3} add up to 0 (mod p), we may subtract a fixed constant from all terms. Hence for a fixed prime p ≥ 3 we are done if we can show that

a_{0}u_{n} + a_{1}u_{n−1} + … + a_{2p−3}u_{n−2p+3} ≡ 0 (mod p)  (26)

for all n ≥ 2p − 2, where

u_{q} = −S_{p}(q) − 3 = \begin{cases}−1, & if q odd; \\ 1, & if q even, p + 1 ∤ q; \\ 0, & if p + 1 | q. \end{cases}

This means that {u_{q}}_{q≥1} is the alternating sequence (−1)^{q}, with 1 subtracted whenever p + 1 | q. This is the motivation for computing the alternating sum of all the a_{j}, which by (13) is

2 ∑_{n=0}^{p−2}(−1)^{n}a_{n} = 2 ∑_{m=0}^{\frac{p−3}{2}}(a_{2m} − a_{2m+1}) = 2 ∑_{m=0}^{\frac{p−3}{2}}((m + 1)^{2} − (m + 1)(m + 2))

= −2 ∑_{m=1}^{\frac{p−1}{2}} m = −\frac{(p − 1)(p + 1)}{4},

so that

∑_{n=0}^{2p−3}(−1)^{n}a_{n} ≡ \frac{1}{4} (mod p).  (27)

Now, if n is between k(p + 1) (for some k) and k(p + 1) + p − 4, then in the finite sequence of indices n − 2p + 3, n − 2p + 4, …, n − 1, n, there are exactly two multiples of p + 1.

First, if n = k(p + 1) + j is even, with 0 ≤ j ≤ p − 4, then we have to subtract a_{j} + a_{p+1+j} from (27) since u_{n} and u_{n−p−1} are 0 instead of 1. Since n is even, j is also even, say j = 2m, and so by (12) we have a_{j} ≡ (m + 1)^{2} (mod p), while by (13) and (12),

a_{p+1+j} ≡ −a_{p−4−j} ≡ − (\frac{p − 5 − 2m}{2} + 1) (\frac{p − 5 − 2m}{2} + 2)
≡ −((m + 1) + \frac{1}{2})((m + 1) − \frac{1}{2})
= −(m + 1)^{2} + \frac{1}{4} ≡ −a_{j} + \frac{1}{4} (mod p),

so that by (27) we have

∑_{n=0}^{2p−3}(−1)^{n}a_{n} − a_{j} − a_{p+1+j} ≡ 0 (mod p).  (28)

Second, if n is odd, we have to add a_{j} + a_{p+1+j} to (27) since u_{n} and u_{n−p−1} are 0 instead of −1. Since n is odd, so is j, say j = 2m + 1, and so by (12) we have a_{j} ≡ (m + 1)(m + 2) (mod p), while by (13) and (12),

a_{p+1+j} ≡ −a_{p−4−j} ≡ − (\frac{p − 5 − 2m}{2} + 1)^{2} ≡ −(m + \frac{3}{2})^{2} (mod p),

so that

a_{j} + a_{p+1+j} ≡ −\frac{1}{4} (mod p),

and thus with (27) we have

∑_{n=0}^{2p−3}(−1)^{n}a_{n} + a_{j} + a_{p+1+j} ≡ 0 (mod p).

This, together with (28), means that (26) holds for n = k(p + 1) + j, 0 ≤ j ≤ p − 4.

It remains to consider the case p − 3 ≤ j ≤ p; in this case there is only one multiple of p + 1 among the indices n − 2p + 3, …, n − 1, n, and we have to add or subtract a_{j}, p − 3 ≤ j ≤ p, to, resp. from (27). Due to the ranges for which (12) and (13) are valid, all four cases need to be considered separately, namely

a_{p−3} ≡ (\frac{p − 3}{2} + 1)^{2} ≡ \frac{1}{4} (mod p),
a_{p−2} ≡ (\frac{p − 3}{2} + 1) (\frac{p − 3}{2} + 2) ≡ −\frac{1}{4} (mod p),
a_{p−1} ≡ −a_{p−2} ≡ \frac{1}{4} (mod p),
a_{p} ≡ −a_{p−3} ≡ −\frac{1}{4} (mod p).

Now with (27) we obtain

∑_{n=0}^{2p−3}(−1)^{n}a_{n} ± a_{j} ≡ 0 (mod p).

where the sign is chosen according to the parity of j, just as in the previous case.

Altogether, we have shown that the recurrence relation (26) is always satisfied, and this completes the proof.

References

[1] P. Bachmann, Niedere Zahlentheorie. Zweiter Teil. B. G. Teubner, Leipzig, 1910. Reprinted as two volumes in one, Chelsea, 1968.

[2] L. E. Dickson, History of the Theory of Numbers, Vol. 1, Chelsea, 1919.

[3] K. Dilcher, On multiple zeros of Bernoulli polynomials, preprint, 2007.

[4] A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers. Organic Mathematics (Burnaby, BC, 1995), 253–276, CMS Conf. Proc., 20, Amer. Math. Soc., Providence, RI, 1997.

[5] H. W. Gould, Combinatorial Identities, revised edition, Gould Publications, Morgantown, W.Va., 1972.

[6] Ch. Hermite, Extrait d’une lettre à M. Borchardt, J. Reine Angew. Math. 81 (1876), 93–95.

[7] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, fifth ed., Oxford University Press, 1979.

[8] E. E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93–146.

[9] E. Lucas, Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques, suivant un module premier, Bull. Soc. Math. France 6 (1878), 49–54.

[10] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

    cally at http://www.research.att.com/∼njas/sequences/.

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

Keywords: Binomial sums, binomial coefficients, congruences.

(Concerned with sequences \underline{A002620} and \underline{A007318}.)

Received September 22 2007; revised version received October 4 2007. Published in Journal of Integer Sequences, October 5 2007.

Return to Journal of Integer Sequences home page.