ON THE ORDER OF STIRLING NUMBERS AND

ALTERNATING BINOMIAL COEFFICIENT SUMS

Ira M. Gessel^{∗}

Department of Mathematics, Brandeis University, Waltham, MA 02454

and Tamás Lengyel

Occidental College, 1600 Campus Road, Los Angeles, CA 90041

June 2000

1. INTRODUCTION

We prove that the order of divisibility by prime p of k! S(a (p − 1) p^{q}, k) does not depend on a and q if q is sufficiently large and k/p is not an odd integer. Here S(n, k) denotes the Stirling number of the second kind; i.e., the number of partitions of a set of n objects into k nonempty subsets. The proof is based on divisibility results for p-sected alternating binomial coefficient sums. A fairly general criterion is also given to obtain divisibility properties of recurrent sequences when the coefficients follow some divisibility patterns.

The motivation of the paper is to generalize the identity [8]

ν_{2}(k! S(n, k)) = k − 1, 1 ≤ k ≤ n,  (1)

where S(n, k) denotes the Stirling number of the second kind, and n = a 2^{q}, a is odd, and q is sufficiently large (for example, q ≥ k − 2 suffices). Here ν_{p}(m) denotes the order of divisibility by prime p of m, i.e., the greatest integer e such that p^{e} divides m. It is worth noting the remarkable fact that the order of divisibility by 2 does not depend on a and q if q is sufficiently large. We will clarify later what value is large enough.

Our objective in this paper is to analyze ν_{p}(k! S(n, k)) for an arbitrary prime p. It turns out that identity (1) can be generalized to calculate the exact value of ν_{p}(k! S(n, k)) if n = a (p − 1) p^{q} and k is divisible by p − 1. The main result of this paper is Theorem 1: If n = a (p − 1) p^{q}, 1 ≤ k ≤ n, a and q are positive integers such that (a, p) = 1, q is sufficiently large, and k/p is not an odd integer, then

ν_{p}(k! S(n, k)) = ⌊\frac{k − 1}{p − 1}⌋ + τ_{p}(k),

where τ_{p}(k) is a nonnegative integer. Moreover, if k is a multiple of p − 1 then τ_{p}(k) = 0.

Here ⌊x⌋ denotes the greatest integer function. Note that the order of divisibility by p of k! S(a (p − 1) p^{q}, k) does not depend on a and q if q is sufficiently large. For instance, we may choose q such that q > \frac{k}{p−1} − 2 in this case. Numerical evidence suggests that the condition on the magnitude of q may be relaxed and it appears that n ≥ k suffices in many cases (cf. [8]).

∗partially supported by NSF grant DMS-9622456

The case excluded by Theorem 1, in which k/p is an odd integer, behaves somewhat differently: Theorem 2: For any odd prime p, if k/p is an odd integer then ν_{p}(k! S(a (p − 1) p^{q}, k)) > q.

In Section 2 we prove a fundamental lemma: If n = a(p − 1)p^{q} then

(−1)^{k+1}k! S(n, k) ≡ G_{p}(k) (mod p^{q+1}),  (2)

where

G_{p}(k) = ∑_{p|i} \binom{k}{i}(−1)^{i}.

All of our divisibility results for the Stirling numbers are consequences of divisibility results for the alternating binomial coefficient sums G_{p}(k), which are of independent interest. Theorem 2 is an immediate consequence of (2), since if k/p is an odd integer, the corresponding binomial coefficient sum is 0.

To prove Theorem 1, we prove the analogous divisibility result for G_{p}(k). The proof is presented in Section 2, and it combines number-theoretical, combinatorial and analytical arguments. By an application of Euler’s theorem, we prove (2). We then apply p-section of the binomial expansion of (1 − x)^{k} to express G_{p}(k) as a sum of p − 1 terms involving roots of unity. We take a closer look at this sum from different perspectives in Sections 3 and 4 and give a comprehensive study of the special cases p = 3 and 5. We choose two different approaches in these sections: we illustrate the use of roots of unity in the case in which p = 3, and for p = 5 we use known results relating G_{5}(k) to Fibonacci and Lucas numbers.

We outline a generating function based method to analyze the sum in terms of a recurrent sequence in Section 2. A fairly general lemma (Lemma 7) is also given in order to provide the framework for proving divisibility properties. The reader may find it a helpful tool in obtaining divisibility properties of recurrent sequences when the coefficients follow some divisibility patterns (e.g., [1]). The lemma complements previous results that can be found, for example, in [11] and [13]. Theorem 1 follows by an application of Lemma 7. A similar approach yields Theorem 3: For any odd prime p and any integer t,

∑_{i≡t (mod p)} \binom{k}{i}(−1)^{i} ≡ \{ \begin{matrix}(−1)^{\frac{k}{p−1} −1}p^{\frac{k}{p−1} −1} & (mod p^{\frac{k}{p−1}} ), if k is divisible by p − 1, \\ 0 & (mod p^{⌊^{\frac{k}{p−1}}⌋}), otherwise. \end{matrix}

Fleck [4] and Kapferer [7] proved the second part of Theorem 3, and Lundell [10] obtained the first part (Theorem 1.1 (ii)). Lundell has only indicated that the proof is based on a tedious induction on ⌊\frac{k}{p−1}⌋. The case t = 0, k = p(p − 1) of Theorem 3 was proposed as an American Mathematical Monthly problem by Evans [3].

The proofs of Lemma 7 and Theorem 3 are given in Section 5 in which an application of Theorem 3 is also presented to prove its generalization: Theorem 4: Let p be an odd prime and let m be an integer with 0 ≤ m ≤ min(k, p) such that r = \frac{k−m}{p−1} is an integer. We set r ≡ r′ (mod p) with 1 ≤ r′ ≤ p. If r′ ≥ m then for any integer t,

∑_{i≡t (mod p)} \binom{k}{i}(−1)^{i}i^{m} ≡ (−1)^{m+ \frac{k−m}{p−1} −1}\binom{k}{m}m! p^{\frac{k−m}{p−1} −1} (mod p^{\frac{k−m}{p−1} +ν_{p}(\binom{k}{m}m!)}).

For example, it follows that ∑_{i≡t (mod 17)} \binom{135}{i}(−1)^{i}i^{7} ≡ \binom{135}{7}7! 17^{7} (mod 17^{8}), independently of t. Here we have m = 7 and r′ = r = 8.

Theorem 4 is a generalization of Theorem 1.7 of [10]. Note that the conditions of Theorem 4 are always satisfied for m = 0 and 1 provided p − 1 | k − m. The theorem can be generalized to the case in which p = 2 and m = 0 or 1, also (see also [8]), e.g.,

∑_{2|i} \binom{k}{i} = ∑_{2 |̸ i} \binom{k}{i} = 2^{k−1}.

Some conjectures on τ_{p}(k) are discussed at the end of the paper.

2. TOOLS AND THE GENERAL CASE

Lemma 5: If n = a(p − 1)p^{q} then

(−1)^{k+1}k! S(n, k) ≡ ∑_{p|i} \binom{k}{i}(−1)^{i} (mod p^{q+1}).  (3)

Proof: By a well-known identity for the Stirling numbers [2, p. 204], we have

k! S(n, k) = ∑_{i=0}^{k} \binom{k}{i}i^{n}(−1)^{k−i} ≡ ∑_{p |̸ i} \binom{k}{i}i^{n}(−1)^{k−i} (mod p^{n}).

For n = a (p − 1) p^{q} and (i, p) = 1, we have

i^{n} ≡ 1 (mod p^{q+1})

by Euler’s theorem. Notice that n ≥ q + 1. By the binomial theorem, we obtain

(1 − 1)^{k} = ∑_{p|i} \binom{k}{i}(−1)^{i} + ∑_{p |̸ i} \binom{k}{i}(−1)^{i};

therefore we have

\begin{aligned}k! S(n, k) ≡ ∑_{p |̸ i} \binom{k}{i}(−1)^{k−i} & = (−1)^{k} ∑_{p |̸ i} \binom{k}{i}(−1)^{i} \\ & = (−1)^{k+1} ∑_{p|i} \binom{k}{i}(−1)^{i} (mod p^{q+1}). \end{aligned}

Lemma 6: For any odd prime p, if k is an odd multiple of p then

∑_{p|i} \binom{k}{i}(−1)^{i} = 0.

Proof: The terms \binom{k}{i}(−1)^{i} and \binom{k}{k−i}(−1)^{k−i} cancel in (3).

Theorem 2 is an immediate consequence of Lemmas 5 and 6. We note that by multisection identities ([12, p. 131] or [2, p. 84]),

∑_{m|i} \binom{k}{i}(−1)^{i} = \frac{1}{m} ∑_{t=1}^{m−1}(1 − ω^{t})^{k},  (4)

where ω = exp(2πi/m) is a primitive mth root of unity. To illustrate the use of this identity, we note that identity (1) follows immediately if we set m = p = 2: identities (3) and (4) with ω = −1, imply that

k! S(n, k) ≡ (−1)^{k+1}2^{k−1} (mod 2^{q+1})

if q > k − 2. The ways of improving this lower bound on q have been discussed in [8]. In the general case, we set

G_{m}(k) = ∑_{m|i} \binom{k}{i}(−1)^{i}.  (5)

For example, for any prime p, we have G_{p}(k) = 1 for 0 ≤ k < p, and G_{p}(p) = 0. By identity (3), we get that

k! S(a (p − 1) p^{q}, k) ≡ (−1)^{k+1}G_{p}(k) (mod p^{q+1})  (6)

holds for all q > 0.

Now we are going to determine the generating function of G_{p}(k) in identity (8) and deduce recurrence (9). An application of Lemma 7 to this recurrence will imply the required divisibility properties. For any odd m, we obtain

\begin{aligned}∑_{k=0}^{∞} [∑_{m|i}(−1)^{i}\binom{k}{i}] x^{k} & = ∑_{m|i}(−1)^{i} \frac{x^{i}}{(1 − x)^{i+1}} \\ & = ∑_{j=0}^{∞}(−1)^{mj} \frac{x^{mj}}{(1 − x)^{mj+1}} \\ & = \frac{1}{1 − x} (1 − \frac{(−x)^{m}}{(1 − x)^{m}} )^{−1} \\ & = \frac{(1 − x)^{m−1}}{(1 − x)^{m} + x^{m}} = 1 + x\frac{(1 − x)^{m−1} − x^{m−1}}{(1 − x)^{m} + x^{m}} . \end{aligned}  (7)

We note that an alternative derivation of identity (7) follows by binomial inversion [5].

From now on p denotes an odd prime. In some cases the discussion can be extended to p = 2, as will be pointed out.

We set m = p and subtract 1 from both sides of (7), to yield

∑_{k=1}^{∞} G_{p}(k)x^{k} = x\frac{(1 − x)^{p−1} − x^{p−1}}{(1 − x)^{p} + x^{p}} .  (8)

We adopt the usual notation [x^{k}] f(x) to denote the coefficient of x^{k} in the formal power series f(x). If we multiply both sides of (8) by the denominator of the right-hand side and equate coefficients, we get a useful recurrence that helps us in deriving divisibility properties. Note that the right side is a polynomial of degree p − 1. For k ≥ p, we obtain that the coefficient of x^{k} is zero; i.e.,

[x^{k}] ((1 − x)^{p} + x^{p}) ∑_{i=1}^{∞} G_{p}(i)x^{i} = 0.

It follows that

∑_{i=0}^{p−1}(−1)^{i}\binom{p}{i}G_{p}(k − i) = 0,

i.e.;

G_{p}(k) = − ∑_{i=1}^{p−1}(−1)^{i}\binom{p}{i}G_{p}(k − i).  (9)

Remark: Note that for p = 2, identity (8) has a slightly different form as it becomes

∑_{k=1}^{∞} G_{2}(k)x^{k} = \frac{x}{1 − 2x},

and we can easily deduce that G_{2}(k) = 2^{k−1} which agrees with ν_{2}(k! S(n, k)) = k − 1.

The calculation of G_{p}(k) is more complicated for p > 2. However, we can find a lower bound on ν_{p}(G_{p}(k)) and effectively compute G_{p}(k)(mod p^{ν_{p}(G_{p}(k))+1}) if p − 1 | k by making some observations about identity (9). We shall need the following general result: Lemma 7: Let p be an arbitrary prime. Assume that the integral sequence a_{k} satisfies the recurrence

a_{k} = ∑_{i=1}^{d} b_{i}a_{k−i}, k ≥ d + 1,

and that for some nonnegative integer m, ν_{p}(a_{d}) = m ≥ 0 and the initial values a_{i}, i = 1, 2, …, d − 1, are all divisible by p^{m}. Let ν_{p}(b_{d}) = r ≥ 1 and suppose that the coefficients b_{i} (i = 1, 2, …, d − 1) are all divisible by p^{r}. We write a_{d} = αp^{m} and b_{d} = βp^{r}, and set f(k) = f_{p}(k, m, r) = m + ⌊\frac{k−1}{d}⌋ r. Then ν_{p}(a_{k}) ≥ f(k), and equality holds if d | k. Moreover, for any integer t ≥ 1, we have

a_{td} ≡ αβ^{t−1}p^{m+(t−1)r} (mod p^{m+tr}).

According to the lemma, there is a transparent relation between the lower bound f(k) on ν_{p}(a_{k}) and the parameters ν_{p}(a_{d}), ν_{p}(b_{d}), and d provided ν(a_{i}) ≥ m and ν_{p}(b_{i}) ≥ r for i = 1, 2, …, d − 1.

We prove Lemma 7 in Section 5. With its help, we can now prove Theorem 1.

Proof of Theorem 1: By identity (5), we have a_{i} = G_{p}(i) = 1, for i = 1, 2, …, p−1, and by identity (9), b_{i} = (−1)^{i+1}\binom{p}{i} for i = 1, 2, …, p − 1; therefore, ν_{p}(a_{i}) = 0 and ν_{p}(b_{i}) = 1. We apply Lemma 7 with d = p − 1, m = 0, r = 1, α = 1, β = −1, and s = 2, and get

G_{p}(k) = a_{k} ≡ \{ \begin{matrix}(−1)^{\frac{k}{p−1} −1}p^{\frac{k}{p−1} −1} & (mod p^{\frac{k}{p−1}} ), if k is divisible by p − 1, \\ 0 & (mod p^{⌊^{\frac{k}{p−1}}⌋}), otherwise. \end{matrix}  (10)

It follows that ν_{p}(a_{k}) ≥ \frac{k}{p−1} −1, and equality holds if and only if p−1 | k. We define τ_{p}(k) by τ_{p}(k) = ν_{p}(a_{k})−⌊\frac{k−1}{p−1}⌋. By identities (6) and (10), it follows that for all q > ν_{p}(a_{k})−1, ν_{p}(k! S(n, k)) = ν_{p}(a_{k}), which concludes the proof of Theorem 1.

In the next two sections, we study the cases p = 3 and p = 5 in detail.

3. AN APPLICATION, p = 3

We set m = p = 3 and ω^{3} = 1. By identities (3) and (4), we have

∑_{3|i} \binom{k}{i}(−1)^{i} = \frac{1}{3}((1 − ω)^{k} + (1 − ω^{2})^{k}) = \frac{1}{3}(1 − ω)^{k}(1 + (1 + ω)^{k}).  (11)

Note that 1+ω = −ω^{2}, and (1−ω)^{2} = 1−2ω+ω^{2} = −3ω. Therefore identity (11) implies

∑_{3|i} \binom{k}{i}(−1)^{i} = \frac{1}{3}(1 − ω)^{k}(1 + (−ω^{2})^{k}) = \frac{1}{3}(−3ω)^{k/2}(1 + (−ω^{2})^{k}).  (12)

For 6 | k we get \frac{1}{3}(−3ω)^{k/2}2 = (−1)^{k/2}2 · 3^{k/2−1}, yielding ν_{3}(k! S(n, k)) = k/2 − 1 for q > k/2 − 2.

For k even and 3 |̸ k, by identity (12) we have (−1)^{k/2}3^{k/2−1}ω^{k/2}(1 + ω^{2k}) = (−1)^{k/2}3^{k/2−1}(ω^{k/2} + ω^{−k/2}) = (−1)^{k/2+1}3^{k/2−1}, since ω^{k/2} + ω^{−k/2} = ω + ω^{−1} = −1 in this case.

We are left with cases in which k is odd. For k odd and 3 |̸ k we have two cases. If k ≡ 1 (mod 6), say k = 6l + 1 for some integer l ≥ 0, then by identity (11) we obtain \frac{1}{3}(1 − ω)^{6l}(1 − ω)(1 + (−ω^{2})^{6l+1}) = \frac{1}{3}(−3ω)^{3l}(1 − ω)(1 − ω^{2}) = (−3)^{3l} = (−3)^{\frac{k−1}{2}} . If k ≡ 5 (mod 6), say k = 6l + 5 for some integer l ≥ 0, then by identity (11) we obtain \frac{1}{3}(1 − ω)^{6l}(1 − ω)^{5}(1 + (−ω^{2})^{6l+5}) = \frac{1}{3}(−3ω)^{3l}(1 − ω)^{5}(1 − ω) = \frac{1}{3}(−3)^{3l}(−3ω)^{3} = (−1)^{\frac{k+1}{2}} 3^{\frac{k−1}{2}} .

In summary, we get Theorem 8: For q > ⌊\frac{k−1}{2}⌋ − 1, k > 0, and k ≢ 3 (mod 6), we have

ν_{3}(k! S(2a 3^{q}, k)) = ⌊\frac{k − 1}{2}⌋ .

Recall that if k/3 is an odd integer, then ν_{3}(k! S(n, k)) > q by Theorem 2.

4. AN APPLICATION, p = 5

For p = 5, we can use the fact that G_{5}(k) can be expressed explicitly in terms of Fibonacci or Lucas numbers, with the formula depending on k modulo 20, as shown by Howard and Witt [6]. (The Fibonacci numbers F_{n} are given by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2. The Lucas numbers L_{n} satisfy the same recurrence, but with the initial conditions L_{0} = 2 and L_{1} = 1.)

The power of 5 dividing a Fibonacci or Lucas number is determined by the following result [9]:

Lemma 9: For all n ≥ 0 we have ν_{5}(F_{n}) = ν_{5}(n). On the other hand, L_{n} is not divisible by 5 for any n.

Theorem 10: If k ≡ 5 (mod 10) then G_{5}(k) = 0. If k ≢ 5 (mod 10) then

ν_{5}(G_{5}(k)) = ⌊\frac{k − 1}{4}⌋ + τ_{5}(k),

where

τ_{5}(k) = \{ \begin{matrix}ν_{5}(k + 1), & if k ≡ 9 (mod 20) \\ ν_{5}(k), & if k ≡ 10 (mod 20) \\ ν_{5}(k + 2), & if k ≡ 18 (mod 20) \\ 0, & otherwise. \end{matrix}  (13)

Proof: From a result of Howard and Witt [6, Theorem 3.2], we find that the value of 5^{−⌊(k−1)/4⌋}G_{5}(k) is given by the following table:

k mod 20  0  1  2  3  4
5^{−⌊(k−1)/4⌋}G_{5}(k) 2L_{k/2} F_{(k+1)/2} F_{k/2+1} L_{(k−1)/2} L_{k/2−1}
k mod 20  5  6  7  8  9
5^{−⌊(k−1)/4⌋}G_{5}(k)  0  −F_{k/2−1} −L_{(k−1)/2} −L_{k/2+1} −F_{(k+1)/2}
k mod 20  10  11  12  13  14
5^{−⌊(k−1)/4⌋}G_{5}(k) −2F_{k/2} −L_{(k+1)/2} −L_{k/2+1} −F_{(k−1)/2} −F_{k/2−1}
k mod 20  15  16  17  18  19
5^{−⌊(k−1)/4⌋}G_{5}(k)  0  L_{k/2−1} F_{(k−1)/2} F_{k/2+1} L_{(k+1)/2}

The result then follows easily from Lemma 9.

We can now easily derive our main result on the divisibility of Stirling numbers by powers of 5. Theorem 11: If n is divisible by 4 · 5^{q}, where q is sufficiently large, and k ≢ 5 (mod 10), then

ν_{5}(k! S(n, k)) = ν_{5}(G_{5}(k)) = ⌊\frac{k − 1}{4}⌋ + τ_{5}(k),

where τ_{5}(k) is given by (13).

Proof: Apply Lemma 5 to Theorem 10.

Note that in Theorem 11 any q exceeding ν_{5}(k! S(n, k)) − 1 will suffice; for instance, we can select the lower bound ⌊\frac{k−1}{4}⌋ + τ_{5}(k) − 1.

Our proof of Theorem 10 does not generalize to other primes, so we mention another approach that in principle does generalize, though it is not easy to apply it to primes larger than 5.

The basic idea is to p-sect the generating functions ∑_{k} G_{p}(k)x^{k}. If A(x) = N(x)/D(x), where N(x) and D(x) are polynomials, then we can determine all of the p-sections of A(x) by multiplying the numerator and denominator of A(x) by D(ωx)D(ω^{2}x) ⋯ D(ω^{p−1}x), where ω is a primitive pth root of unity: since D(x)D(ωx) ⋯ D(ω^{p−1}x) is invariant under substituting ωx for x, it must be a polynomial in x^{p}. For example, we find in this way that

∑_{k=1}^{∞} G_{3}(k)x^{k} = x\frac{(1 − x)^{2} − x^{2}}{(1 − x)^{3} + x^{3}} = \frac{x + x^{2} − 3x^{4} − 9x^{5} − 18x^{6}}{1 + 27x^{6}}  (14)

and

∑_{k=1}^{∞} G_{5}(k)x^{k} = x\frac{(1 − x)^{4} − x^{4}}{(1 − x)^{5} + x^{5}} = \frac{N_{5}(x)}{1 + 5^{4}x^{10} + 5^{5}x^{20}} ,  (15)

where

\begin{aligned}N_{5}(x) & = x + x^{2} + x^{3} + x^{4} − 5x^{6} − 20x^{7} − 55x^{8} − 125x^{9} − 250x^{10} + 175x^{11} \\ & − 100x^{12} − 375x^{13} − 375x^{14} + 500x^{16} + 625x^{17} − 1250x^{19} − 2500x^{20}. \end{aligned} (16)

Of course, once we have found these formulas, by whatever method, they may be immediately verified.

We note that in both of these generating functions the denominator is actually a polynomial in x^{2p} rather than just in x^{p}, and it is not difficult to show that this is true in general.

From (14) we can immediately derive a formula for G_{3}(k). With somewhat more difficulty one can use (15) and (16) to determine the exact power of 5 dividing G_{5}(k) and thereby give a different proof of Theorem 10.

5. THE PROOFS OF LEMMA 7, THEOREM 3, AND THEOREM 4 We present the proofs of some lemmas and theorems that were stated in Section 2.

Proof of Lemma 7: We prove that the following two assertions hold, by induction on k:

(i) ν_{p}(a_{k}) ≥ f(k) (ii) If k = td, where t is a positive integer, then a_{k} ≡ αβ^{t−1}p^{m+(t−1)r} (mod p^{m+tr}). Note that (ii) implies that ν_{p}(a_{k}) = f(k).

If 1 ≤ k ≤ d, then these assertions are consequences of the initial conditions. Now suppose that (i) and (ii) hold for a_{k−d}, …, a_{k−1}. Then the induction hypothesis implies that b_{i}a_{k−i} is divisible by p^{r+f(k−i)} for i = 1, 2, …, d. We have r+f(k−i) ≥ r+f(k−d) = f(k), so b_{i}a_{k−i} is divisible by p^{f(k)}, and thus so is a_{k} = b_{1}a_{k−1} + ⋯ + b_{d}a_{k−d}. This proves (i).

For (ii), suppose that k = td. By the induction hypothesis we have

a_{(t−1)d} ≡ αβ^{t−2}p^{m+(t−2)r} (mod p^{m+(t−1)r})

and

ν_{p}(a_{td−i}) ≥ m + ⌊\frac{td − i − 1}{d}⌋ r = m + (t − 1)r, for 1 ≤ i < d.

Thus

b_{d}a_{(t−1)d} ≡ βp^{r} · αβ^{t−2}p^{m+(t−2)r} = αβ^{t−1}p^{m+(t−1)r} (mod p^{m+tr})

and

ν_{p}(b_{i}a_{td−i}) ≥ m + tr, for 1 ≤ i < d.

Then (ii) follows from the recurrence for a_{k}.

We note that the lemma extends the study of situations discussed in [11] and [13] by relaxing the condition that the coefficient b_{d} be relatively prime to the modulus.

We can further generalize identity (10) and obtain the

Proof of Theorem 3: Analogously to the definition of (5), we set, for 0 ≤ t ≤ m−1,

G_{m}(k, t) = ∑_{i≡t (mod m)} \binom{k}{i}(−1)^{i}.

In a manner similar to the derivation of identity (7), for every odd m, we obtain that

∑_{k=0}^{∞} [ ∑_{i≡t (mod m)}(−1)^{i}\binom{k}{i}] x^{k} = \frac{(−x)^{t}(1 − x)^{m−t−1}}{(1 − x)^{m} + x^{m}} .

Note that the degree of the numerator is m − 1. It is fairly easy to modify identities (8) and (9) for G_{m}(k, t). An application of Lemma 7 to G_{p}(k, t) yields Theorem 3. We note that here α = \binom{p−1}{t}(−1)^{t}; hence α ≡ 1 (mod p). The congruence follows from the two identities, \binom{p}{t} ≡ 0 (mod p), 1 ≤ t ≤ p − 1, and \binom{p}{t} = \binom{p−1}{t−1} + \binom{p−1}{t}. (We note that for every prime p and positive integer n, \binom{p^{n}−1}{t} ≡ (−1)^{t} (mod p) also holds.)

The interested reader may try another application of Lemma 7 to prove the following identity (cf. [1])

ν_{2}( ∑_{k=0}^{n−1} \binom{2n − 1}{2k}3^{k}) = n − 1, n = 1, 2, ….

Finally, we note that it would be interesting to find an upper bound on ν_{p}(a_{k}) − f(k) as a function of k. The case p = 5 and k ≡ 9, 10, or 18 (mod 20) shows that the difference can be as big as C log k with some positive constant C.

We conclude this section with the

Proof of Theorem 4: Theorem 3 deals with the case in which m = 0, thus we may assume that m ≥ 1. Using the identities i^{m} = ∑_{l=0}^{m} S(m, l)\binom{i}{l}l! and \binom{k}{i}\binom{i}{l} = \binom{k}{l}\binom{k−l}{i−l} for l ≤ i ≤ k, we have

∑_{i≡t (mod p)} \binom{k}{i}(−1)^{i}i^{m} = ∑_{i≡t (mod p)} \binom{k}{i}(−1)^{i} ∑_{l=0}^{m} S(m, l)\binom{i}{l}l!

= ∑_{l=0}^{m} S(m, l)\binom{k}{l}l! ∑_{i≡t (mod p)} \binom{k − l}{i − l}(−1)^{i}

= ∑_{l=0}^{m}(−1)^{l}S(m, l)\binom{k}{l}l! ∑_{i≡t−l (mod p)} \binom{k − l}{i}(−1)^{i}.

(17)

Observe that Theorem 3 applies to the last sum.

We shall show that under the conditions of Theorem 4, the term with l = m has the smallest exponent of p on the right side of (17). If l = 0 then S(m, l) = 0 in identity (17) so we need only consider the terms in which l ≥ 1. Let χ_{y}(x) denote the indicator function of divisibility by y; i.e., χ_{y}(x) = 1 if and only if y | x. We shall show that

ν_{p} (\binom{k}{l}l! p^{⌊ \frac{k−l}{p−1} ⌋−χ_{p−1}(k−l)}) = ν_{p}(k!) − ν_{p}((k − l)!) + ⌊\frac{k − l}{p − 1}⌋ − χ_{p−1}(k − l), 1 ≤ l ≤ m,

assumes its unique minimum at l = m; this fact, together with Theorem 3, implies Theorem 4.

By a well-known formula, we have

ν_{p}((k − l)!) = ⌊\frac{k − l}{p} ⌋ + ⌊\frac{k − l}{p^{2}} ⌋ + · · · .

The hypotheses of Theorem 4 imply that k−m = r(p−1) ≡ −r′ (mod p), where 1 ≤ r′ ≤ p and m ≤ r′. It follows that ⌊\frac{k−m+i}{p}⌋ is constant for i = 0, 1, …, r′−1; i.e., ⌊\frac{k−l}{p}⌋ is constant for l = m, m − 1, …, m − r′ + 1. Since r′ ≥ m, this implies that ⌊\frac{k−l}{p}⌋ is constant for 1 ≤ l ≤ m. Similarly, ⌊\frac{k−l}{p^{i}}⌋ is constant for 1 ≤ l ≤ m. Therefore, ν_{p}((k − l)!) is constant for 1 ≤ l ≤ m.

Next we show that

⌊\frac{k − l}{p − 1}⌋ − χ_{p−1}(k − l) > ⌊\frac{k − m}{p − 1}⌋ − χ_{p−1}(k − m), 1 ≤ l < m.  (18)

Since p − 1 divides k − m, k − l is not divisible by p − 1 for l = m − 1, m − 2, …, m − p + 2, and since m ≤ p, this implies all cases of (18) except m = p, l = 1. In this case we have

⌊\frac{k − 1}{p − 1}⌋ − χ_{p−1}(k − 1) = 1 + ⌊\frac{k − p}{p − 1}⌋ − χ_{p−1}(k − p),

and thus (18) holds in this case also. The proof is now complete.

We note that the generating function of the sum on the left hand side of (17) can be derived by binomial inversion [5] in terms of Eulerian polynomials.

6. CONJECTURES

Empirical evidence suggests that formulas for τ_{p}(k) exist based on the residue of k modulo p(p − 1). The following conjectures have been proved only in the cases p = 3 and p = 5.

Conjecture 1:

(a) If k is divisible by 2p but not by p(p − 1) then τ_{p}(k) = ν_{p}(k).

(b) If k + 1 is divisible by 2p but not by p(p − 1) then τ_{p}(k) = ν_{p}(k + 1).

Conjecture 2:

For each odd prime p, there is a set A_{p} ⊆ {1, 2, …, p(p−1)−1} such that if k ≢ 0 or −1 (mod 2p) and k is not an odd multiple of p, then τ_{p}(k) > 0 if and only if k is congruent modulo p(p − 1) to an element of A_{p}.

It usually seems to be true that under the conditions of Conjecture 2, for each i ∈ A_{p}, there exists some integer u_{p,i} such that if k ≡ i (mod p(p − 1)) then τ_{p}(k) ≡ ν_{p}(k + u_{p,i}).

For example, Theorem 7 asserts that the conjectures hold for p = 3, with A_{3} = ∅, and Theorem 8 asserts that the conjectures hold for p = 5 with A_{5} = {18} and u_{5,18} = 2. Empirical evidence suggests that A_{7} = {16}, with u_{7,16} = 75. Here are the empirical values of A_{p} for primes p from 11 to 23.

\begin{aligned}A_{11} & = \{14, 18, 73, 81, 93\} \\ A_{13} & = \{82, 126, 148\} \\ A_{17} & = \{37, 39, 62, 121, 179, 230, 234\} \\ A_{19} & = \{85, 117, 119, 156, 196, 201, 203, 244, 279, 295, 299, 316, 320, 337\} \\ A_{23} & = \{72, 128, 130, 145, 148, 170, 171, 188, 201, 210, 211, 232, 233, 234, 317, 325, 378, 466\} \end{aligned}

REFERENCES

1. D. M. Bloom. Solution to Problem 428. College Math. Journal 22 (1991): 257–259.

2. L. Comtet. Advanced Combinatorics. Dordrecht: D. Reidel, 1974.

ON THE ORDER OF STIRLING NUMBERS 13 3. R. Evans. “A congruence for a sum of binomial coefficients.” Problem E2685. Amer.

Math. Monthly 86 (1979): 130–131. Solution by H. F. Mattson, Jr.

4. A. Fleck. Sitzungs. Berlin Math. Gesell. 13 (1913–14): 2–6.

5. P. Haukkanen. “Some binomial inversions in terms of ordinary generating functions.” Publ. Math. Debrecen 47 (1995): 181–191.

6. F. T. Howard and R. Witt. “Lacunary sums of binomial coefficients.” Applications of Fibonacci Numbers, Vol 7: 185–195. Kluwer Academic Publishers, 1998.

7. H. Kapferer. “Über gewisse Summen von Binomialkoeffizienten.” Archiv der Mathematik und Physik 23 (1915): 117–124.

8. T. Lengyel. “On the divisibility by 2 of the Stirling numbers of the second kind.” The Fibonacci Quarterly 32 (1994): 194–201.

9. T. Lengyel. “The order of the Fibonacci and Lucas numbers”. The Fibonacci Quarterly 33 (1995): 234–239.

10. A. Lundell. “A divisibility property for Stirling numbers.” J. Number Theory 10 (1978): 35–54.

11. N. S. Mendelsohn. “Congruence relationships for integral recurrences.” Can. Math. Bull. 5 (1962): 281–284.

12. J. Riordan. An Introduction to Combinatorial Analysis. New York: Wiley, 1958.

13. D. W. Robinson. “A note on linear recurrent sequences modulo m.” Amer. Math. Monthly 73 (1966): 619–621.

AMS Classification Numbers: 11B73, 11B37, 11B50