On some properties of the series ∑_{k=0}^{∞} k^{n}x^{k} and the Stirling numbers of the second kind

Tamás Lengyel

Mathematics Department, Occidental College, 1600 Campus Road, Los Angeles, CA 90041, USA

Dedicated to Paul Erdős on His Eightieth Birthday

Received Revised

Abstract

Lengyel, T., On some properties of the series ∑_{k=0}^{∞} k^{n}x^{k} and the Stirling numbers of the second kind We partially characterize the rational numbers x and integers n ≥ 0 for which the sum ∑_{k=0}^{∞} k^{n}x^{k} assumes integers. We prove that if ∑_{k=0}^{∞} k^{n}x^{k} is an integer for x = 1 − a/b with a, b > 0 integers and gcd(a, b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n, k). More specifically, we obtain ν_{a}((n − k)! S(n, n − k)) ≥ ν_{a}(n!) − k + 1 for all integers k, 2 ≤ k ≤ n, and a ≥ 3, provided a is odd or divisible by 4, where ν_{a}(m) denotes the exponent of the highest power of a which divides m, for m and a > 1 integers. New identities are also derived for the Stirling numbers, e.g., we show that ∑_{k=0}^{2n} k! S(2n, k)( − \frac{1}{2})^{k} = 0, for all integers n ≥ 1.

1. Introduction It is known [2] that the sum ∑_{k=0}^{∞} k^{n}/2^{k} is integer for every n ≥ 0 integer. For n ≤ 16, there is an easy way

to calculate its value ([2], [9], and [13]) by taking the nearest integer to n!( ln 2)^{−n−1}. This observation gives rise to the question on what rational number x and integer n ≥ 0 the sum ∑_{k=0}^{∞} k^{n}x^{k} assumes an integer and whether there is a simple way to calculate its value.

We set f(x, n) = ∑_{k=0}^{∞} k^{n}x^{k} for n ≥ 1, and f(x, 0) = 1/(1 − x) for n = 0. Note that the series converges if |x| < 1. The function f has some fascinating properties. The study of these properties is motivated by the observation that f(x, n) assumes integers at many different values of x and n. For instance, as we noted, f(1/2, n) is always an integer. In fact, it is equal to 2 ∑_{k=1}^{n} k! S(n, k).

Clearly, f(x, 0) is an integer if and only if x = 1 − 1/m where m is an arbitrary positive integer. From now on we assume that n ≥ 1. By Comtet ([2], p. 245), for every positive integer n we obtain that

(1)  f(x, n) = \frac{A_{n}(x)}{(1 − x)^{n+1}} ,

where A_{n}(x) = ∑_{k=1}^{n} A(n, k) x^{k} is called the Eulerian polynomial and A(n, k) stands for the Eulerian number. Equation (1) implies that f(x, n) is rational if x is rational. By simple algebra, identity (1) yields that f(1−1/m, n) is an integer multiple of m for every n. In most cases we substitute 1 − a/b for x, with positive integers a and b, in studying f(x, n). From now on any rational number x will be meant in the lowest terms, i.e., if x = 1 − a/b then we assume that gcd(a, b) = 1.

2 T. Lengyel

We express f(x, n) in terms of a sum involving Stirling numbers. It turns out that the divisibility properties of S(n, k) play an important role in analyzing f(x, n). In Section 2 we give a lower bound on the highest power of a ≥ 3 which divides (n − k)! S(n, n − k), for small values of k provided a is odd or divisible by 4. In Sections 3 and 4 we prove conditions for f(x, n) to be an integer (Theorems 5, 6, 8, and 14). For example, we show that f(1−a/b, n) cannot be an integer unless a ≤ 2. Sufficient conditions are also given confirming that there are always solutions if n is even. Section 4 is devoted to the study of function f, and some new identities for the Stirling numbers are derived (Corollary 10–13). For instance, we prove that ∑_{k=0}^{2n} k! S(2n, k)( − \frac{1}{2})^{k} = 0, for all integers n ≥ 1. In Section 5 we propose conjectures on f(x, n) and briefly discuss some asymptotics for f(x, n) which help in calculating its value for a particular set of rational values x and integers n.

2. Basic tools We define the integer-valued function ν_{a}(r) for all positive integers r and a > 1 by ν_{a}(r) = q, where a^{q}|r, and

a^{q+1}|/ r. Clearly, ν_{a}(r) ≤ ν_{p}(r), for every prime factor p of a. Let p be a prime and d_{p}(k) be the sum of the digits in the p-ary representation of k. By Legendre’s lemma [2], ν_{p}(n!) = \frac{n−d_{p}(n)}{p−1} ≤ n − 1, therefore n + 1 − ν_{a}(n!) ≥ 2, for every pair of positive integers n and a ≥ 2. Note that ν_{2}(n!) = n − d_{2}(n).

We rewrite identity (1) in the equivalent form ([2], p. 244)

(2)  f(x, n) = x ∑_{k=1}^{n} k! S(n, k)(x − 1)^{n−k}/(1 − x)^{n+1} = x ∑_{k=1}^{n} k! S(n, k)(−1)^{n−k}(1 − x)^{−k−1}.

The divisibility properties of S(n, k) have been studied in [12], [3], [10], [1], and [8]. Davis [3], Lundell [10], and Clarke [1] obtained their results by studying the divisibility properties of the closely related partial Stirling numbers. Methods have been proposed for computing ν_{p}((n−k)! S(n, n−k)) though most of them are calculation-intensive and depend on the particular values of the parameters p, n, and k. For our purposes a fairly general lower bound on the multiplicities of the divisors of S(n, k) will suffice.

In this section we give a lower bound on ν_{a}((n − k)! S(n, n − k)) and prove Lemma 1 which will be essential in proving Theorem 9.

Lemma 1. For every n ≥ 1 the identity f(x, n) = (−1)^{n+1}f(1/x, n) holds for the formal power series f(x, n) and f(1/x, n).

Proof. We note that A(n, k) counts the number of permutations of [n] with k − 1 rises, k = 1, 2, …, n. By identity (1) and using the symmetry A(n, k) = A(n, n − k + 1) the statement follows.

Note that f(1/x, n) is a formal power series and it is convergent for ∀x : |x| > 1. We shall need the following

Theorem 2. For every prime p ≥ 3 and integer k: 1 ≤ k ≤ n,

ν_{p}(S(n, n − k)) ≥ \frac{d_{p}(n − k) − d_{p}(n) − k · (p − 2)}{p − 1} + 1.

More precisely, we prove

Theorem 3. For all integers k: 1 ≤ k ≤ n, and odd a ≥ 3,

(3)  ν_{a}((n − k)! S(n, n − k)) ≥ ν_{a}(n!) − k + 1.

On some properties of the series ∑_{k=0}^{∞} k^{n}x^{k} and the Stirling numbers of the second kind 3

For a ≥ 3 with ν_{2}(a) ≥ 2, the inequality (3) holds for k: 2 ≤ k ≤ n. On the other hand, for k = 1 we have

ν_{a}((n − 1)! S(n, n − 1)) = ν_{a}(n!(n − 1)/2) ≥ ν_{a}(n!) − 1.

Remark 4. Note that Theorem 2 is a special case of Theorem 3. Of course, ν_{a}((n − k)! S(n, n − k)) ≥ ν_{a}((n − k)!) is a trivial lower bound on ν_{a}((n − k)! S(n, n − k)). In the applications of inequality (3) we want ν_{a}(n!) − k + 1 ≥ ν_{a}((n − k)!). Thus we might restrict the range of k to small values. In fact, Theorem 2 vacuously holds if k > \frac{p−1}{p−2}⌊log_{p} n⌋ + 2, and the same applies to Theorem 3 with the smallest prime divisor p ≥ 3 of a.

We apply Theorem 3 to prove Theorem 6.

Proof of Theorem 3. We shall use the notion of the associated Stirling numbers of the second kind. The associated Stirling number of the second kind, S_{r}(n, k), is the number of partitions of an n-element set, into k blocks, all of cardinality at least r. Clearly, S_{r}(n, k) is an integer and S(n, k) = S_{1}(n, k). We use the following identity ([11] and [5]) which gives a simple relation between ordinary and associated Stirling numbers.

If 1 ≤ k ≤ n/2 then

(4)  S(n, n − k) = ∑_{j=0}^{k} \binom{n}{2k − j}S_{2}(2k − j, k − j).

For 0 ≤ n − 2k + j ≤ n − k, the selection of n − 2k + j one-element blocks can be done in \binom{n}{2k−j} ways and the remaining 2k − j elements must be partitioned into k − j blocks, with at least 2 elements in each block. Hence identity (4) follows. By expanding this identity and noting that S_{2}(n, k) is always an integer, we derive that, for 0 ≤ j ≤ k,

(5)  ν_{p}((n − k)! S(n, n − k)) ≥ min_{0≤j≤k} ν_{p}((n − k)! \binom{n}{k + j}).

We give a lower bound on the right-hand side of inequality (5). Observe that (n−k)! \binom{n}{k+j} = (n−k)!\frac{n!}{(k+j)! (n−k−j)!} = \frac{(n−k)!}{(n−k−j)!} \frac{(2k)!}{(k+j)!} \frac{n!}{(2k)!} is a multiple of \frac{n!}{(2k)!}. We have

(6)  ν_{p}((n − k)! S(n, n − k)) ≥ ν_{p}(n!) − ν_{p}((2k)!).

By Legendre’s lemma [2], for every prime p ≥ 3, ν_{p}((2k)!) = \frac{2k−d_{p}(2k)}{p−1} ≤ \frac{2k−2}{p−1} = \frac{2}{p−1}(k − 1) ≤ k − 1 since 2k is even. We have just proved inequality

(7)  ν_{p}((n − k)! S(n, n − k)) ≥ ν_{p}(n!) − k + 1

for every prime p ≥ 3. (The case k > n/2 follows easily as we will see it later.)

If a ≥ 3 has no prime factor greater than 2 then it is a power of 2, say a = 2^{m}, m ≥ 2. For k, 1 ≤ k ≤ 3, the proof of the theorem is straightforward by expanding S(n, n − k). Otherwise we observe that

(8)  ⌈\frac{ν_{2}((2k)!)}{m}⌉ ≤ ⌈\frac{ν_{2}((2k)!)}{2}⌉ = ⌈\frac{2k − d_{2}(2k)}{2}⌉ ≤ k − 1,

except for k = 2^{l}, l = 1, 2, … in which case we get ⌈\frac{ν_{2}((2k)!)}{m}⌉ ≤ k. We recall, however, that we ignored the factor \frac{(n−k)!}{(n−k−j)!} \frac{(2k)!}{(k+j)!} in the process of deducing inequality (6). This factor is divisible by 8 if k ≥ 4. For, we notice that either j = k yields that \frac{(n−k)!}{(n−k−j)!} is a multiply of 8 or j < k yields the same thing for \frac{(2k)!}{(k+j)!} = 2k \frac{(2k−1)!}{(k+j)!}. By the above observations and inequality (6), we now derive

ν_{2^{m}}((n − k)! S(n, n − k)) = ⌊\frac{ν_{2}((n − k)! S(n, n − k))}{m}⌋ ≥ ⌊\frac{ν_{2}(n!) − ν_{2}((2k)!) + 3}{m}⌋ ≥

≥ ⌊\frac{ν_{2}(n!)}{m}⌋ − ⌈\frac{ν_{2}((2k)!) − 3}{m}⌉ ≥ ⌊\frac{ν_{2}(n!)}{m}⌋ − ⌈\frac{ν_{2}((2k)!) − 3}{2}⌉ =

= ⌊\frac{ν_{2}(n!)}{m}⌋ − ⌈\frac{ν_{2}((2k)!) − 1}{2}⌉ + 1 ≥ ⌊\frac{ν_{2}(n!)}{m}⌋ − (k − 1) + 1 = ν_{2^{m}}(n!) − k + 2,

for 4 ≤ k ≤ n/2 and a = 2^{m}, m ≥ 2.

On the other hand, if a ≥ 3 is odd then

ν_{a}((n − k)! S(n, n − k)) = min_{{p: p|a \atop m=νp(a)}}⌊\frac{ν_{p}((n − k)! S(n, n − k))}{m}⌋ ≥ min_{{p: p|a \atop m=νp(a)}}⌊\frac{ν_{p}(n!) − ν_{p}((2k)!)}{m}⌋ ≥

≥ min_{{p: p|a \atop m=νp(a)}}(⌊\frac{ν_{p}(n!)}{m}⌋ − ⌈\frac{ν_{p}((2k)!)}{m}⌉) ≥

≥ min_{{p: p|a \atop m=νp(a)}}⌊\frac{ν_{p}(n!)}{m}⌋ − k + 1 = ν_{a}(n!) − k + 1,

by inequalities (6), (7), and (8). Similarly, if a is divisible by 4 then we derive ν_{a}((n−k)! S(n, n−k)) ≥ ν_{a}(n!)−k+1, by taking the minimum for all odd prime divisors of a and p = 2 with m = ν_{2}(a), and applying the previous paragraph.

If k ≥ n/2 then ν_{a}((n−k)!) ≥ 0 ≥ ν_{a}(n!)−ν_{a}((2k)!) holds, and ν_{a}(m) ≤ ν_{p}(m) implies ν_{a}((2k)!) ≤ ν_{p}((2k)!) ≤ k − 1 and inequality (3). (Note that by Remark 4 this case can be ignored.)

We note that the case in which a = p = 2 has been studied in [8]. We proved Theorem A. ([8], Theorem 1) Let c ≥ 0 be an odd integer. There exists a function f(k) ≤ k −2 such that for all positive integers k and n ≥ f(k), we have ν_{2}(k! S(c · 2^{n}, k)) = k − 1, or equivalently, ν_{2}(S(c · 2^{n}, k)) = d_{2}(k) − 1.

We also proposed

Conjecture B. For all k and 1 ≤ k ≤ 2^{n}, ν_{2}(S(2^{n}, k)) = d_{2}(k) − 1.

3. Results We give conditions on a, b, and n which will guarantee that f(1 − a/b, n) is an integer. To illustrate the

discussion we start with the case of a = 2, and substitute x = 1 − a/b = 1 − 2/(2l + 1) into identity (2). We rewrite f(1 − 2/(2l + 1), n), n ≥ 1, using identity (2) and the binomial expansion of (2l + 1)^{k}. The change of the order of summations yields

(9)  \begin{aligned}f(1 − \frac{2}{2l + 1}, n) & = (l − 1/2) ∑_{k=1}^{n} k! S(n, k)(−1)^{n−k}(\frac{2l + 1}{2})^{k} \\ & = (−1)^{n} (l − 1/2) ∑_{k=1}^{n} k! S(n, k)(−1/2)^{k} ∑_{j=0}^{k} \binom{k}{j}(2l)^{j} \\ & = (−1)^{n} (l − 1/2) ∑_{j=0}^{n}(2l)^{j} ∑_{k=j}^{n} \binom{k}{j}k! S(n, k)(−1/2)^{k}. \end{aligned}

On some properties of the series ∑_{k=0}^{∞} k^{n}x^{k} and the Stirling numbers of the second kind 5

Examples. We consider the cases of n = 3, 6, 7, and 13. The analysis is fairly simple for n = 3 and 7, and we obtain

f(1 − \frac{2}{2l + 1}, 3) = \frac{1}{8} − 2l^{2} + 6l^{4},

and

f(1 − \frac{2}{2l + 1}, 7) = \frac{17}{16} − 62l^{2} + 756l^{4} − 3360l^{6} + 5040l^{8}.

These expansions show that the function f cannot be an integer at 1 − 2/(2l + 1).

For n = 6 we get

f(1 − \frac{2}{2l + 1}, 6) = \frac{−17l}{4} + 77l^{3} − 420l^{5} + 720l^{7}

which implies the necessary and sufficient condition for f(1 − 2/(2l + 1), 6) to be an integer. The condition is that l must be a multiple of 4, i.e., x = 1 − 2/(8m + 1).

The case of n = 13 results in

f(1 − \frac{2}{2l + 1}, 13) = − \frac{5461}{4} + \frac{929569l^{2}}{4} + Cl^{4},

with some integer multiplier C; hence 4 f(1 − 2/(2l + 1), 13) ≡ 3 + l^{2} (mod 4). It follows that f(1 − 2/b, 13) is an integer if and only if b = 4m + 3 with some integer m ≥ 0.

The first two examples are special cases of the following

Theorem 5. For s ≥ 0, f(1 − 2/b, 2^{s} − 1) cannot be an integer.

We also prove that only the case of a = 2 should be considered.

Theorem 6. For n ≥ 0, f(1 − a/b, n) cannot be an integer if a > 2.

Recall that a/b is meant in lowest terms. Observe that the case of s = 0 in Theorem 5 and that of n = 0 in Theorem 6 are trivial since we have set f(x, 0) = 1/(1 − x). These two theorems lead to necessary conditions for f(x, n) to be an integer as they are summarized in

Corollary 7. The value of the function f(x, n) can be an integer only if

(a) 1 − x = \frac{1}{b}, or

(b) 1 − x = \frac{2}{b} in lowest terms, and n + 1 is not a power of 2.

On the other hand, a sufficient condition is given by

Theorem 8. The function f(x, n) assumes integers for 1 − x = \frac{2}{4m+1}, m ≥ 1 and n ≥ 2 if n is a power of 2 provided that Conjecture B is true.

Proof of Theorem 8. In identity (9), we expand the sum by the index j. As we will see in Theorem 9, if n is even then the term with j = 0 vanishes. For j ≥ 2, every term is an integer regardless of the parity of l by Conjecture B. If l is even then the remaining term with j = 1 becomes an integer, too.

We note that the above mentioned examples show that f(1 − \frac{2}{8m+1}, 6) and f(1 − \frac{2}{4m+3}, 13) are integers for any integer m ≥ 1. Before presenting the proof of Theorems 5 and 6 we sketch the main idea. By identity (2) we get

(10)  f(1 − a/b, n) = \frac{b − a}{b} ∑_{k=1}^{n} k! S(n, k)(−1)^{n−k}(\frac{b}{a})^{k+1}.

We assume that f(1−a/b, n) is an integer, and analyze its divisibility by r, a properly selected divisor of a. We can discard the factor \frac{b−a}{b} on the right-hand side, for, both b − a and b are relatively prime to a. In both cases we will see that the exponent of r in the last or last two terms on the right-hand side of (10) is negative and less than that in any other term. This fact will prevent f(1 − a/b, n) from being an integer. The proofs follow by contradiction.

Now we can complete the two proofs.

Proof of Theorem 5. We set r = a = 2 and n = 2^{s} − 1. For the exponents of 2 in the terms on the right hand side of (10) we have ν_{2}(k! S(n, k)/2^{k+1}) = (k − d_{2}(k)) + ν_{2}(S(n, k)) − (k + 1) = −1 − d_{2}(k) + ν_{2}(S(n, k)) ≥ −1 − s, 1 ≤ k ≤ 2^{s} − 1. Notice that the exponent of 2 in the last term with k = n is less than that in any other term. For it is negative, the sum cannot be an integer.

Proof of Theorem 6. By inequality (7), if 0 ≤ k ≤ n − 1 and r ≥ 3 is a prime divisor of a, then ν_{r}(k! S(n, k)) ≥ ν_{r}(n!)−(n−k)+1. We set l = ν_{r}(a). It follows that ν_{r}(k! S(n, k)/a^{k+1}) > ν_{r}(n!)−(n−k)−l(k+1) ≥ ν_{r}(n!) − l(n + 1), i.e., ν_{r}(k! S(n, k)/a^{k+1}) as a function of k, 1 ≤ k ≤ n, attains its unique minimum at k = n. The minimum is negative; therefore, the sum in identity (10) cannot be an integer.

If a = 2^{m}, m ≥ 2, then we set r = a and l = ν_{r}(a) = 1. By Theorem 3, if 0 ≤ k ≤ n − 2 then ν_{r}(k! S(n, k)) ≥ ν_{r}(n!) − (n − k) + 1. In this case, we obtain ν_{r}(k! S(n, k)/a^{k+1}) > ν_{r}(n!) − (n − k) − (k + 1) ≥ ν_{r}(n!) − (n + 1). The exponent of the term with k = n − 1 can be as little as that of the last term which is ν_{r}(n!) − (n + 1). However, we can conclude the proof by noticing that the exponent of the sum of the last two terms in (10) is ν_{r}(n!) − (n + 1). In fact, we have

−(n − 1)! S(n, n − 1) \frac{b^{n}}{a^{n}} + n! S(n, n)\frac{b^{n+1}}{a^{n+1}} = \frac{n!}{a^{n+1}} b^{n}( − a \frac{n − 1}{2} + b),

and the last two factors are non-zero integers and relatively prime to a.

4. Identities for Stirling numbers We have seen in the examples that f(1 − 2/(2l + 1), 3), f(1 − 2/(2l + 1), 7), and f(1 − 2/(2l + 1), 13) are even

functions of l, while f(1 − 2/(2l + 1), 6) is odd. These observations are generalized in

Theorem 9. For every integer n ≥ 0, f(1−2/(2l + 1), n) is a polynomial in l; in particular, f(1−2/(2l + 1), n) is an even (resp. odd) function when n is odd (resp. even).

Proof of Theorem 9. Clearly, f(1 − 2/(2l + 1), n) is a polynomial in l. Observe that if x = 1 − 2/(2l + 1) then 1/x = 1 − 2/((−2l) + 1). Lemma 1 implies that f(1 − 2/(2l + 1), 2n) = −f(1 − 2/((−2l) + 1), 2n), i.e., f(1 − 2/(2l + 1), 2n) is an odd function of l, and similarly, the relation f(1 − 2/(2l + 1), 2n + 1) = f(1 − 2/((−2l) + 1), 2n + 1) implies that f(1 − 2/(2l + 1), 2n + 1) is an even function of l.

We set a(n, j) = (−1)^{n} ∑_{k=j}^{n} \binom{k}{j}k! S(n, k)(−1/2)^{k}. Clearly, a(n, n) = n!/2^{n}, and a(n, j) = 0 if j > n. We will see that a(2n, 0) = 0 (n ≥ 1) and some other identities for a(n, j) in Corollaries 10-13.

On some properties of the series ∑_{k=0}^{∞} k^{n}x^{k} and the Stirling numbers of the second kind 7

After rearranging the terms in (9) according to the powers of l, we get the representation of f(1 − \frac{2}{2l+1}, n) as a polynomial in l, i.e.,

(11)  \begin{aligned}f(1 − \frac{2}{2l + 1}, n) & = (l − \frac{1}{2}) ∑_{j=0}^{n}(2l)^{j}a(n, j) = ∑_{j=0}^{n} 2^{j}l^{j+1}a(n, j) − ∑_{j=0}^{n} 2^{j−1}l^{j}a(n, j) \\ & = −\frac{a(n, 0)}{2} + \{ ∑_{j=1}^{n} 2^{j−1}l^{j}(a(n, j − 1) − a(n, j))\} + n! l^{n+1}. \end{aligned}

By Theorem 9, we obtain the following two corollaries for the coefficient of l^{j}.

Corollary 10. a(2n, 0) = ∑_{k=0}^{2n} k! S(2n, k)(− \frac{1}{2})^{k} = 0, n = 1, 2, ….

Corollary 11. For every n = 1, 2, … and m = 0, 1, 2, …

(12)  ∑_{k=2m+1}^{2n} \binom{k}{2m + 1}k! S(2n, k)(−1/2)^{k} = ∑_{k=2m+2}^{2n} \binom{k}{2m + 2}k! S(2n, k)(−1/2)^{k},

i.e., a(2n, 2m + 1) = a(2n, 2m + 2), and

(13)  ∑_{k=2m}^{2n−1} \binom{k}{2m}k! S(2n − 1, k)(−1/2)^{k} = ∑_{k=2m+1}^{2n−1} \binom{k}{2m + 1}k! S(2n − 1, k)(−1/2)^{k},

i.e., a(2n − 1, 2m) = a(2n − 1, 2m + 1).

There is a direct derivation of Corollary 10 as it was pointed out by Knuth [6]. It turns out that a(n, 0) is equal to (2 − 2^{n+2})B_{n+1}/(n + 1), where B_{n} denotes the nth Bernoulli number, proving Corollary 10. Note that a(n, 0) is closely related to the nth tangent number [4], and determining the exact denominator of a(n, 0) is the content of Exercise 6.24 in [4]. For the exponential generating function of 2^{n}a(n, j) one can deduce the remarkable formula ([6])

∑_{n=0}^{∞} 2^{n}a(n, j)z^{n}/n! = (tanh z)^{j} + (tanh z)^{j+1}.

The summation over j of these generating functions yields

(1 + tanh z) + (tanh z + tanh^{2} z) + ⋯ = −1 + 2/(1 − tanh z) = e^{2z},

confirming

Corollary 12. For every n ≥ 0, ∑_{j=0}^{n} a(n, j) = 1.

We note that a(n, j) can be determined by taking the coefficients of n^{−s} in the Dirichlet series of the function ∑_{k=j}^{∞} \binom{k}{j}(ζ(s) − 1)^{k}y^{k} at y = −1/2, where ζ(s) denotes the Riemann zeta-function. Yet another proof of Corollary 10 follows by an application of Lambert series and Dirichlet products.

By Corollary 10 and the basic recurrence for the Stirling numbers we get

Corollary 13. a(2n + 1, 0) = −a(2n, 1)/2, if n ≥ 1, and a(2n + 2, 1) = a(2n + 1, 1) − a(2n + 1, 2), if n ≥ 0.

In order to figure out whether f(1 − 2/(2l + 1), n) is an integer or not, it is enough to check whether

(14)  (l − \frac{1}{2}) ∑_{j=0}^{⌊log_{2}(n+1)⌋}(2l)^{j}a(n, j)

is an integer. In fact, there exists a j_{0} = j_{0}(k) such that, for every j ≥ j_{0}, the term \frac{(2l)^{j}}{2} \frac{\binom{k}{j}k!S(n,k)}{2^{k}} in the expansion of \frac{1}{2}(2l)^{j}a(n, j) is an integer. We get

(15)  ν_{2}(\frac{(2l)^{j}}{2} \frac{\binom{k}{j}k!S(n, k)}{2^{k}}) = jν_{2}(l) + j − 1 − d_{2}(k) + ν_{2}(\binom{k}{j}S(n, k)).

The order is at least jν_{2}(l) + j − 1 − d_{2}(k). In particular, for every l, jν_{2}(l) + j − 1 − d_{2}(k) ≥ j − 1 − d_{2}(k); therefore, any j_{0} will suffice provided j_{0} − 1 ≥ ⌊log_{2}(k + 1)⌋. If j ≥ ⌊log_{2}(n + 1)⌋ + 1 then the corresponding terms contribute integers only to the sum. In fact, Corollary 10 and identity (15) lead us to a more general condition on l. We choose l such that ν_{2}(l) ≥ d_{2}(k) and get

Theorem 14. For all n even, there exists an integer q_{0} = q_{0}(n) such that f(x, n) is integer if x = 1 − \frac{2}{2^{q}m+1} provided q ≥ q_{0}. The function q_{0}(n) can be chosen to be ⌊log_{2}(n + 1)⌋ + 1.

5. Conjectures and asymptotic evaluation It seems rather difficult to completely characterize all solutions (b, n) for which f(1 − 2/b, n) is an integer. We

propose two conjectures

CONJECTURE C. For n odd, f(x, n) is an integer if x = 1 − \frac{1}{m} with m ≥ 1, or n ≡ 13 (mod 64) and x = 1 − 2/(4m + 3) with m ≥ 0.

We checked all integer solutions for x = 1 − \frac{2}{b} where b ≤ 100 and n ≤ 300. For n odd we found only two more sets of integer solutions, more specifically, f(1 − \frac{2}{8m+5}, 61) and f(1 − \frac{2}{16m+9}, 253) are integers.

Assume that m ≥ 1. Numerical evidence suggests

CONJECTURE D. For n even, f(x, n) is integer if one of the following eight conditions is satisfied:

(i) x = 1 − \frac{1}{m},
(ii) n ≡ 0 (mod 4) and n ≢ 28 (mod 32) and x = 1 − \frac{2}{2m+1},
(iii) n ≡ 2 (mod 16) and  x = 1 − \frac{2}{4m+1},
(iv) n ≡ 6 (mod 16) and  x = 1 − \frac{2}{8m+1},
(v) n ≡ 10 (mod 16) and  x = 1 − \frac{2}{4m+1},
(vi) n ≡ 14 (mod 32) and  x = 1 − \frac{2}{16m+1}.
(vii) n ≡ 30 (mod 64) and  x = 1 − \frac{2}{32m+1}.
(viii) n ≡ 62 (mod 128) and  x = 1 − \frac{2}{64m+1}.

For n ≡ 28 (mod 32) and n ≠ 252, f(1 − \frac{2}{4m+1}, n), while for n = 252, f(1 − \frac{2}{8m+1}, n) are integers.

Note that case (v) can be extended for n = 122, and f(1 − \frac{2}{2m+1}, 122) assumes integers. We found no other solution for b ≤ 100 and n ≤ 300 where n is even.

On some properties of the series ∑_{k=0}^{∞} k^{n}x^{k} and the Stirling numbers of the second kind 9

We could not find any odd 3 ≤ b ≤ 100 which would make f(1 − 2/b, 126) or f(1 − 2/b, 254) an integer. By Theorem 14, however, f(1 − \frac{2}{2^{7}m+1}, 126) and f(1 − \frac{2}{2^{8}m+1}, 254) are integers for m ≥ 1.

Notice the periodic structure of the integer solutions. A possible explanation might follow from the periodic nature of the sequence {S(n, k) (mod 2^{d_{2}(k)})}_{n≥0} (cf. Kwong [7]).

We conclude this discussion with a remark on the asymptotic evaluation of f(x, n). It is well known [2] that the exponential generating function of f(x, n) has the form

∑_{n=0}^{∞} f(x, n)\frac{t^{n}}{n!} = \frac{1}{1 − xe^{t}} .

By standard techniques (e.g., [13], Theorem 5.2.1) for obtaining asymptotics of the coefficients in the Laurent expansion of a meromorphic function we obtain

Theorem 15. For 0 < x < 1, f(x, n) ∼ \frac{n!}{(− ln x)^{n+1}} , as n → ∞.

For instance, f(x, n) = n! \{\frac{1}{(− ln x)^{n+1}} + O(C^{n+1})\}, for every C > \frac{1}{2π} ≈ 0.159 positive number as n → ∞. Actually, it is true that

|f(x, n) − n! \frac{1}{(− ln x)^{n+1}} | ≤ \frac{Kn!}{|1 − x|}C^{n+1},

with arbitrary K > 1. This relation helps in calculating f(x, n) for small n and sufficiently large 1 − x provided f(x, n) is an integer. For instance, if 1 ≤ l ≤ 25 and n ≤ 15 then f(1−2/(2l+1), n) can be easily computed this way. In fact, the approximation is so good in this case that f(x, n) is equal to the closest integer to n!(− ln x)^{−n−1}. We leave the details of the proof to the reader. Note that the asymptotic treatment offers no help in testing whether a particular value f(x, n) is integer or not.

Acknowledgment

The author would like to thank Professors Donald E. Knuth and Y. H. Harris Kwong for their helpful comments and suggestions. We also thank the referee for valuable remarks and suggesting simplifications of the proofs of Theorems 5, 6, and 8.

Added in proof. Conjecture B has been proven recently. The proof will appear in the Proceedings of the Second International Conference on Difference Equations and Applications, 1995.

References

[1] Clarke, F., Hensel’s lemma and the divisibility by primes of Stirling-like numbers, J. Number Theory 52(1995), 69–84.

[2] Comtet, L., Advanced Combinatorics, D. Reidel, Dordrecht, 1974

[3] Davis, D. M., Divisibility by 2 of Stirling-like numbers, Proceedings of the American Mathematical Society 110(1990), 597–600.

10 T. Lengyel

[4] Graham, R. L., Knuth, D. E., and Patashnik, O., Concrete Mathematics, Addison-Wesley, Reading, MA, 1989.

[5] Howard, F. T., Congruences for the Stirling numbers and associated Stirling numbers, Acta Arithmetica 55(1990), 29-41.

[6] Knuth, D. E., private communication, 1993

[7] Kwong, Y. H., Periodicities of a class of infinite integer sequences modulo M, J. Number Theory 31(1989), 64–79.

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

[9] Lovász, L., Combinatorial Problems and Exercises, North Holland, New York and Akadémiai Kiadó, Budapest, 1979

[10] Lundell, A. T., A divisibility property for Stirling numbers II, preprint, 1990

[11] Riordan, J., An Introduction to Combinatorial Analysis, Wiley, New York, 1958

[12] Sved, M., Divisibility–with visibility, Math. Intelligencer 10(1988), 56–64.

[13] Wilf, H. S., generatingfunctionology, Academic Press, Boston, 1990