p-adic Properties of Lengyel’s Numbers

D. Barsky 7 rue La Condamine 75017 Paris France

                barsky.daniel@orange.fr

J.-P. Bézivin 1, Allée Edouard Quincey 94200, Ivry-sur-Seine France

                 jp.bezivin@orange.fr

Abstract

Lengyel introduced a sequence of numbers Z_{n}, defined combinatorially, that satisfy a recurrence where the coefficients are Stirling numbers of the second kind. He proved some 2-adic properties of these numbers. In this paper, we give another recurrence for the sequence Z_{n}, where the coefficients are Stirling numbers of the first kind. Using this formula, we give another proof of Lengyel’s lower bound on the 2-adic valuation of the Z_{n}. We also resolve some conjectures of Lengyel about the sequence Z_{n}.

We also define

(a) A new sequence Y_{n} analogous to Z_{n}, exchanging the role of Stirling numbers of the first and second kind. We study its 2-adic properties.

(b) Another sequence similar to Lengyel’s sequence, and we study its p-adic properties for p ≥ 3.

1 Introduction and notation

In the text |.| denotes the p-adic absolute value on ℚ, and v_{p} denotes the corresponding padic valuation. Let ℚ_{p} be the p-adic completion of ℚ and let ℂ_{p} be the p-adic completion of an algebraic closure of ℚ_{p}. For all the p-adic background, we refer to Amice [1]; in particular for a polynomial P (x) ∈ ℂ_{p}[x] and for r ∈ ℝ_{+}, we write |P |(r) := sup\begin{matrix}x∈ℂ_{p} \\ |x|≤r \end{matrix} |P (x)|.

For an integer n, let S_{p}(n) be the sum of the digits of the p-adic expansion of n. Throughout this article, we use the following well-known formula (cf. Amice [1, p. 102]):

v_{p}(n!) = \frac{n − S_{p}(n)}{p − 1} .  (1)

Lengyel [4] studied the 2-adic properties of the sequence defined by Z_{1} = 1 and

Z_{n} = ∑_{k=1}^{n−1} S(n, k)Z_{k}  (2)

for n ≥ 2, where the S(n, k) are Stirling numbers of the second kind. (See Lengyel [4] for the combinatorial properties of the Z_{n}). This sequence appears in Sloane’s database [5] as \underline{A005121}. In particular Lengyel showed the following results: Theorem 1. The Z_{n} satisfy

(a) v_{2}(Z_{2^{n}+L}) ≥ n for n ≥ 1 and L ≥ 0;

(b) v_{2}(Z_{k}) ≥ ⌊log_{2}(k)⌋ − 1 for k ≥ 1.

Lengyel also proposed some conjectures about these numbers; first [4, Conjecture 2]: Conjecture 2. For n ≥ 3, let Z_{n} be given by (2). Then v_{2}(Z_{2^{n}}) = n.

He also proposed [4, Conjecture 4]: Conjecture 3. For all n ≥ 2 we have

max{k | v_{2}(Z_{k}) = n} = 3 · 2^{n−1} .

2 The results

In this paper, we reprove the results of Lengyel by another method. This method allows us to prove the above two conjectures. More precisely we get the following theorems: Theorem 4. The lower bound

v_{2}(Z_{n}) ≥ log_{2}(n) − 1

holds for all n ≥ 1. Remark 5. The inequality in Theorem 4 implies the assertion (a) of Theorem 1 when L ≥ 1, and the assertion (b) of Theorem 1.

Theorem 6. If t ≥ 3, then

v_{2}(Z_{2^{t}}) = t .

Remark 7. This theorem proves Conjecture 2; in addition, it completes the assertion (a) of Theorem 1, by showing that the case L = 0 of the assertion (a) holds.

Theorem 8. For all t ≥ 2, we have

max{k | v_{2}(Z_{k}) = t} = 3 · 2^{t−1}

which proves Conjecture 3.

We also introduce a new sequence Y_{n} by permuting the Stirling numbers of the first and second kind. More precisely, let Y_{n} be the sequence of integers defined by Y_{1} = 1 and

Y_{n} = ∑_{m=1}^{n−1} s(n, m)Y_{m} .

for n ≥ 2. Let s(n, k) be, as usual, s(n, k) the Stirling numbers of the first kind. For properties of the Stirling numbers, we refer to Comtet [2, Chapter 5.5, pp. 212–219].

We prove the following theorem for the sequence Y_{n}:

Theorem 9. Let Y_{n} be as above. Then

(a) All the Y_{n} are odd;

(b) For n ≥ 1, we have v_{2}(Y_{n} + 1) = 1 if and only if n is congruent to 0 or 1 modulo 3.

We also get some results for a sequence similar to Lengyel’s sequence for primes p ≥ 3. Define the sequence Z_{n}^{⟨p⟩} by Z_{0}^{⟨p⟩} = 0, Z_{1}^{⟨p⟩} = 1, and

(p − 1)Z_{n}^{⟨p⟩} = ∑_{k=1}^{n−1} S(n, k)Z_{k}^{⟨p⟩}

or

pZ_{n}^{⟨p⟩} = ∑_{k=1}^{n} S(n, k)Z_{k}^{⟨p⟩}

for n ≥ 2. (Note that Z_{n}^{⟨p⟩} is not an integer, but only a p-integer).

We prove the following result below:

Theorem 10. The p-adic valuation of the Z_{n}^{⟨p⟩} satisfies

(a) v_{p}(Z_{n}^{⟨p⟩}) ≥ log_{p}(n) − 1 for n ≥ 1;

(b) v_{p}(Z_{n}^{⟨p⟩}) = t − 1 for n = p^{t};

(c) v_{p}(Z_{n}^{⟨p⟩}) ≥ t for n ≥ p^{t} + 1.

Remark 11. Note that property (c) is an immediate consequence of property (a). Hence we have only to show that (a) and (b) hold.

3 Use of the Stirling numbers of the first kind

We now show that the Z_{n} satisfy another recurrence relation:

Proposition 12. The Z_{n} satisfy

Z_{n} = s(n, 1) − 2 ∑_{m=1}^{n−1} s(n, m)Z_{m}, n ≥ 2 ;  (3)

Z_{n} = −s(n, 1) − 2 ∑_{m=2}^{n−1} s(n, m)Z_{m}, n ≥ 3 .  (4)

Proof. According to Comtet [2, Formula (6f), p. 144], the Stirling numbers of the first and second kind satisfy the formulae

∑_{k=0}^{n} S(n, k)s(k, m) = δ_{m,n} , and ∑_{k=0}^{n} s(n, k)S(k, m) = δ_{m,n} ,

where δ_{m,n} is the usual Kronecker symbol. These relations are equivalent to the following Stirling inversion formula:

∀ n ∈ ℕ (f_{n} = ∑_{m=1}^{n} s(n, m)g_{m} ⟺ g_{n} = ∑_{m=1}^{n} S(n, m)f_{m}) .  (5)

Applying this inversion formula to the recurrence relation for the Z_{n}, we obtain

Z_{n} = ∑_{k=1}^{n−1} S(n, k)Z_{k} ⇔ 2Z_{n} = ∑_{m=1}^{n} S(n, m)Z_{m} + ∑_{m=1}^{n} S(n, m)s(m, 1) ,

which can also be written

Z_{n} = ∑_{m=1}^{n} S(n, m)\frac{Z_{m} + s(n, 1)}{2} .

Next, by Stirling inversion we get

\frac{Z_{n} + s(n, 1)}{2} = ∑_{m=1}^{n} s(n, m)Z_{m} ⇔ \frac{−Z_{n} + s(n, 1)}{2} = ∑_{m=1}^{n−1} s(n, m)Z_{m} ,

which is the desired result.

Remark 13. Actually using exactly the same method, we get the following relation for the sequence Z_{n}^{⟨p⟩} and n ≥ 2:

Z_{n}^{⟨p⟩} = s(n, 1) − \frac{p}{p − 1} ∑_{m=1}^{n−1} s(n, m)Z_{m} .  (6)

Since s(n, 1) = (−1)^{n−1}(n − 1)! is a p-adic unit for n = 1, …, p, we get as an immediate consequence that Z_{n}^{⟨p⟩} is a p-adic unit for the same values of n.

4 Some p-adic properties of Stirling numbers of the

first kind

In this section, we prove some lemmas for the Stirling numbers of the first kind. Lemma 14. For n ≥ m ≥ 1, we get the lower bound

v_{p}(s(n, m)) ≥ ⌊\frac{n − 1}{p}⌋ + 1 − m .

Proof. Note that the inequality is trivial if ⌊\frac{n − 1}{p}⌋ + 1 − m ≤ 0. The Stirling numbers of the first kind (cf. [2, Formula (5e), p. 213]) are defined as follows:

P_{n}(x) = (x)_{n} := ∑_{m=1}^{n} s(n, m)x^{m} .

Take x ∈ ℂ_{p} with |x| = r with \frac{1}{p} < r < 1. Then |x − k| = 1 if k is not divisible by p and |x − k| = r otherwise. This shows that |P_{n}|(r) = max{|s(n, m)|r^{m}} is equal to r^{M}, where M = ⌊\frac{n − 1}{p}⌋ + 1 is the number of k, 0 ≤ k ≤ n − 1, that are divisible by p. Hence |s(n, m)|r^{m} ≤ r^{M}, and |s(n, m)| ≤ r^{M−m}.

The continuity of the map r ↦ |P_{n}|(r), [1, Cor. 4.2.7, p. 122], allows us to choose r = \frac{1}{p} in the previous inequality, which gives the desired lower bound. Lemma 15. If t ≥ 2, and n = p^{t}, it follows that

P_{n}(x) ≡ x^{p^{t−1}}(x^{p−1} − 1)^{p^{t−1}} (mod p) .

Therefore s(n, m) is divisible by p if m ≤ p^{t−1} − 1, and s(p^{t}, p^{t−1}) is not divisible by p. Proof. By hypothesis, we have n ≥ p^{2}. Let r ∈ {0, ⋯, p−1}. The number of integers k such that 0 ≤ k ≤ n − 1 and k ≡ r (mod p) is ⌊\frac{n − 1 − r}{p}⌋ + 1 = p^{t−1}. Hence it is independent of r. It follows that

P_{n}(x) ≡ ∏_{r=0}^{p−1}(x − r)^{p^{t−1}} mod p .

But ∏_{r=0}^{p−1}(x − r) ≡ x^{p} − x = x(x^{p−1} − 1) (mod p). The proof is now complete (the last two assertions are clear).

Now, we examine the value of s(n, k) modulo 4, for specific values of n.

Lemma 16. Let t ≥ 5, and n = 2^{t}. Then

∑_{k=0}^{n} s(n, k)x^{k} = P_{n}(x) = x^{2^{t−1}}(x^{2} − 1)^{2^{t−2}} (mod 4) .

Proof. We know that P_{n}(x) = x(x − 1) ⋯ (x − n + 1). Let r be such that 0 ≤ r ≤ 3. There

are M_{r} = ⌊\frac{n − r − 1}{4}⌋ + 1 values k, 0 ≤ k ≤ n − 1 such that k ≡ r (mod 4). Since n = 2^{t}, we immediately see that M_{r} is in fact independent of r. Hence M_{r} is equal to 2^{t−2}. Thus,

modulo 4, the polynomial P_{n} is congruent to ∏_{r=0}^{3}(x − r)^{2^{t−2}}.

We first consider the factor (x − 2)^{2^{t−2}}. Since (x − 2)^{2} ≡ x^{2} (mod 4), and t ≥ 5, or equivalently t − 2 ≥ 3, we see that

(x − 2)^{2^{t−2}} ≡ x^{2^{t−2}} (mod 4) .

Since 3 is congruent to −1 modulo 4, we have

P_{n}(x) ≡ x^{2^{t−1}}(x^{2} − 1)^{2^{t−2}} (mod 4) .

The proof of the lemma is complete.

Lemma 17. Let n = 2^{t} with t ≥ 5. Then, for all m, 1 ≤ m ≤ 2^{t} − 1, m ≠ 3 · 2^{t−2} and m ≠ 2^{t−1}, it follows that

s(2^{t}, m) ≡ 0 (mod 4) .

In addition, s(2^{t}, 2^{t−1} + 2^{t−2}) ≡ 0 (mod 2), and s(2^{t}, 2^{t−1}) ≡ 1 (mod 4).

Proof. From Formula (1) it follows that

v_{2}(\binom{2^{t−2}}{j}) = S_{2}(j) + S_{2}(2^{t−2} − j) − 1 .

If j ≠ 0 and not equal to 2^{t−2}, then S_{2}(j) + S_{2}(2^{t−2} − j) ≥ 2. If S_{2}(j) + S_{2}(2^{t−2} − j) = 2 then j = 2^{t−3}, because it implies that both j and 2^{t−2} − j are powers of 2 and hence equal (their sum is 2^{t−2}). Using the modulo 4 formula given above for the polynomial P_{n}(x), and the binomial theorem for the factor (x^{2} − 1)^{2^{t−2}}, we obtain

P_{n}(x) ≡ x^{2^{t}} − \binom{2^{t−2}}{2^{t−3}}x^{2^{t−1}+2^{t−2}} + x^{2^{t−1}} (mod 4) .

Since the 2-adic valuation of \binom{2^{t−2}}{2^{t−3}} is equal to 1, the lemma is proved.

Lemma 18. Let t ≥ 5, and n = 3 · 2^{t}. The following congruence holds:

P_{n}(x) ≡ ∑_{k=0}^{n} s(n, k)x^{k} = x^{3·2^{t−1}}(x^{2} − 1)^{3·2^{t−2}} (mod 4) .

Proof. Let r ∈ {0, ⋯, 3}. The number of k such that 0 ≤ k ≤ n − 1 and k ≡ r (mod 4) is ⌊\frac{n − 1 − r}{4}⌋ + 1 which is 3 · 2^{t−2} for all r. Hence

P_{n}(x) ≡ ∏_{r=0}^{3}(x − r)^{3·2^{t−2}} ≡ (∏_{r=0}^{3}(x − r)^{2^{t−2}})^{3} (mod 4) .

From the proof of Lemma 16 it follows that

∏_{r=0}^{3}(x − r)^{2^{t−2}} ≡ x^{2^{t−1}}(x^{2} − 1)^{2^{t−2}} (mod 4) .

The proof is now complete. Lemma 19. Let t ≥ 5, n = 3 · 2^{t}, and 1 ≤ m ≤ n. Then

(a) s(n, m) is divisible by 4 for m ∉ {2^{t+1}+2^{t−1}, 2^{t+1}, 3·2^{t−1}, 3·2^{t−1}+2^{t−2}, 3·2^{t}−2^{t−2}, 3·2^{t}};

(b) s(n, m) is even, but not divisible by 4, for m = 3 · 2^{t} − 2^{t−2} and m = 3 · 2^{t−1} + 2^{t−2};

(c) s(n, m) is odd for m = 2^{t+1} + 2^{t−1}, m = 2^{t+1}, m = 3 · 2^{t−1} and m = 3 · 2^{t}. In particular, s(n, 3 · 2^{t−1}) is odd, and s(n, 3 · 2^{t} − 1), s(n, 3 · 2^{t} − 2), and all the s(n, j) for j ≤ 3 · 2^{t−1} − 1 are divisible by 4. Proof. We know that P_{n}(x) ≡ x^{3·2^{t−1}}(x^{2} − 1)^{3·2^{t−2}} (mod 4) by Lemma 18. By the binomial theorem we get

(x^{2} − 1)^{3·2^{t−2}} = ∑_{j=0}^{3·2^{t−2}}(−1)^{j}\binom{3 · 2^{t−2}}{j}x^{2(3·2^{t−2}−j)} .

From Formula (1) we know that the 2-adic valuation of \binom{q}{j} is S_{2}(j) + S_{2}(q − j) − S_{2}(q). We have 3 · 2^{t−2} = 2^{t−1} + 2^{t−2}, and hence S_{2}(3 · 2^{t−2}) = 2. To prove the lemma it suffices (1) To find all the integers j such that

0 ≤ j ≤ 3 · 2^{t−2}, and T := S_{2}(j) + S_{2}(3 · 2^{t−2} − j) − 2 = \begin{cases}0; \\ 1. \end{cases}  (7)

(2) To show that they are precisely the integers given in (b) and (c).

First suppose that T = 0. We have the trivial solutions of equation (7) j = 0 and j = 3 · 2^{t−2}. Now we can assume 1 ≤ j ≤ 3 · 2^{t−2} − 1. Hence S_{2}(j) = S_{2}(3 · 2^{t−2} − j) = 1 (because S_{2}(n) ≥ 1), It follows that j and 3·2^{t−2} −j are powers of 2, say 2^{α} and 2^{β}. Equality 3 · 2^{t−2} = 2^{α} + 2^{β} immediately shows that α = t − 2 and β = t − 1, or vice-versa. We have found 4 values of j:

j = 0, j = 2^{t−2}, j = 2^{t−1} and j = 3 · 2^{t−2} .

After multiplying by x^{3·2^{t−1}}, we see that they are the values given in assertion (c).

Now suppose that T = 1. From the first case we know that 1 ≤ j ≤ 3 · 2^{t−2} − 1. From equation (7) it follows that S(j) = 1 or S(3 · 2^{t−2} − j) = 2 or vice-versa. This leads to study a relation of the form 2^{α} + (2^{β} + 2^{γ}) = 3 · 2^{t−2}, with β < γ. We leave to the reader to show that it implies α = β = t − 3 and γ = t − 1. Hence the two solutions j = 2^{t−3} and j = 3·2^{t−2} −2^{t−3}. After multiplying by x^{3·2^{t−1}} we see that these values are exactly the values in assertion (b).

For all other values of 1 ≤ m ≤ 3 · 2^{t} s(n, m) ≡ 0 (mod 4). The lemma is proved.

5 A lemma about sums of binomial coefficients

We also need a lemma about sums of binomials.

Lemma 20. Let j be a primitive third root of unity, r ∈ {0, 1, 2}, and n = 3k + r. For s ∈ {0, 1, 2} define

Γ_{s,r,k} = ∑_{\begin{matrix}0≤l≤n; \\ l≡s (mod 3) \end{matrix}} \binom{n}{l} .

It follows that

3Γ_{s,r,k} = 2^{n} + (−1)^{n}(j^{s+r} + j^{2(s+r)}) .

As a consequence, we get

• If r + s is not divisible by 3, then

3Γ_{s,r,k} = 2^{n} + (−1)^{n+1} .

• If r + s is divisible by 3, then

3Γ_{s,r,k} = 2^{n} + 2(−1)^{n} .

Proof. Write

(1 + x)^{n} = ∑_{l=0}^{n} \binom{n}{l}x^{l} ,

and choose successively x = 1, x = j, and x = j^{2}. It follows that

Γ_{0,r,k} + Γ_{1,r,k} + Γ_{2,r,k} = 2^{n} ,  (L_{1})
Γ_{0,r,k} + jΓ_{1,r,k} + j^{2}Γ_{2,r,k} = (1 + j)^{n} ,  (L_{2})
Γ_{0,r,k} + j^{2}Γ_{1,r,k} + jΓ_{2,r,k} = (1 + j^{2})^{n} .  (L_{3})

Since 1+j +j^{2} = 0, we get, when computing the quantities L_{1} +L_{2} +L_{3}, L_{1} +j^{2}L_{2} +jL_{3}, and L_{1} + jL_{2} + j^{2}L_{3},

3Γ_{0,r,k} = 2^{n} + (1 + j)^{n} + (1 + j^{2})^{n} = 2^{n} + (−1)^{n}(j^{r} + j^{2r}) ,
3Γ_{1,r,k} = 2^{n} + j^{2}(1 + j)^{n} + j(1 + j^{2})^{n} = 2^{n} + (−1)^{n}(j^{1+r} + j^{2r+2}) ,
3Γ_{2,r,k} = 2^{n} + j(1 + j)^{n} + j^{2}(1 + j^{2})^{n} = 2^{n} + (−1)^{n}(j^{r+2} + j^{2r+1}) .

The general formula follows.

Remark 21. Analogous results exist in, e.g., [3].

6 Proof of Theorem 4

We show the result by induction on n. For n ≤ 7, we check that the lower bound holds using the explicit numerical values of the Z_{n}, cf. [4, p. 179]. Hence our induction hypothesis will be

(n ≥ 7 ⇒ v_{2}(Z_{m}) ≥ log_{2}(m) − 1, 1 ≤ m ≤ n − 1) .  H(n)

We use Formula (4), valid for n ≥ 3:

Z_{n} = −s(n, 1) − 2 ∑_{m=2}^{n−1} s(n, m)Z_{m} .  (4)

We will show that all the terms in the last expression have 2-adic absolute value ≤ 2^{− log_{2}(n)+1}; this will imply that this is also the case for Z_{n}, and the result will be proved. We consider many different cases.

6.1 Let m be such that 2 ≤ m ≤ ⌊\frac{n − 1}{2}⌋ + 1. Using Lemma 14 and the induction hypothesis, we get

|s(n, m)Z_{m}| ≤ 2^{− log_{2}(m)+1−⌊\frac{n−1}{2}⌋−1+m} .

We want to show that this last term is bounded by 2^{− log_{2}(n)+2} (we have taken into account the factor 2 in Formula (4)). This is equivalent to showing that

m − log_{2}(m) ≤ ⌊\frac{n − 1}{2}⌋ − log_{2}(n) + 2 .

There are two cases, n even or odd.

First case: n even. Let n = 2h. As n ≥ 7, we have h ≥ 4. We also have ⌊\frac{n − 1}{2}⌋ = h − 1; hence m ≤ h. Since log_{2}(2h) = 1 + log_{2}(h), we have to show that

m − log_{2}(m) ≤ h − log_{2}(h) ,

which holds because the function x − log_{2}(x) is increasing for x ≥ 2.

Second case: n odd. Let n = 2h + 1 (hence h ≥ 3). We get ⌊\frac{n − 1}{2}⌋ = h; hence 2 ≤ m ≤ h + 1. First, suppose that m = h + 1. We have to show

h + 1 − log_{2}(h + 1) ≤ h − log_{2}(2h + 1) + 2

or log_{2}(2h + 1) ≤ log_{2}(h + 1) + 1 which is equivalent to showing 2h + 1 ≤ 2h + 2 and hence is true. Now we can suppose that 2 ≤ m ≤ h. Since h ≥ 3, we have 1 + \frac{1}{2h} ≤ \frac{7}{6}, and hence

1 − log_{2}(1 + \frac{1}{2h}) ≥ 1 − log_{2}(\frac{7}{6}) = \frac{log(12) − log(7)}{log 2} > 0 .

It suffices to show that

m − log_{2}(m) ≤ h − log_{2}(h) ,

which holds because the function x−log_{2}(x) is increasing for x ≥ 2, and 2 ≤ m ≤ h.

6.2 Now suppose that m verify ⌊\frac{n − 1}{2}⌋ + 2 ≤ m ≤ n − 1. We have only at our disposal the induction hypothesis. We have to show, taking into account the factor 2, that 2^{− log_{2}(m)+1} ≤ 2^{− log_{2}(n)+2}, or log_{2}(n) ≤ log_{2}(m) + 1. This is equivalent to showing n ≤ 2m. There are two cases:

(a) If n is even, n = 2h, we have m ≥ ⌊\frac{n − 1}{2}⌋+2 = h+1; hence 2m ≥ 2h+2 = n+2.

(b) If n is odd, n = 2h+1, we have m ≥ ⌊\frac{n − 1}{2}⌋+2 = h+2; hence 2m ≥ 2h+4 = n+3.

6.3 The only remaining term, s(n, 1), is equal to (−1)^{n−1}(n − 1)!, cf. [2, Formula (6b), p. 214]. We want to show that, for all n ≥ 7,

|(n − 1)!| = 2^{−n+1+S_{2}(n−1)} ≤ 2^{− log_{2}(n)+1} .

This is equivalent to showing that

S_{2}(n − 1) + log_{2}(n) ≤ n .

For m ≥ 1, we have S_{2}(m) ≤ 1+log_{2}(m), it suffices then to show that 1+log_{2}(n−1)+ log_{2}(n) ≤ n. This is equivalent to showing n(n − 1) ≤ 2^{n−1}. We prove this inequality by noticing that it holds for n = 6 and using an easy induction argument.

Now the proof of Theorem 4 is complete.

7 Proof of Theorem 6

We also use induction. Looking at the numerical values of Z_{n}, we check the equality for t = 3 and t = 4. So suppose that equality v_{2}(Z_{2^{h}}) = h holds for 3 ≤ h ≤ t − 1, and prove that v_{2}(Z_{2^{t}}) = t. We can suppose t ≥ 5.

Again using Formula (4) with n = 2^{t}, we get

Z_{2^{t}} = −s(2^{t}, 1) − 2 ∑_{m=2}^{2^{t}−1} s(2^{t}, m)Z_{m} .

We will prove that all terms in Eq. (4), with the exception of the term corresponding to m = 2^{t−1}, (note that t − 1 ≥ 4; hence m ≠ 4) have 2-adic valuation ≥ t + 1.

7.1 First, consider the valuation of the term s(2^{t}, 1) = (−1)^{2^{t}−1}(2^{t} − 1)!. From Formula (1) it follows that

v_{2}(s(2^{t}, 1)) = 2^{t} − 1 − S_{2}(2^{t} − 1) = 2^{t} − 1 − t .

We want to prove that 2^{t} − 1 − t ≥ t + 1 or, replacing t by t − 1, 2^{t−1} ≥ 1 + t; this last inequality holds for t = 3, and also for t ≥ 3 by an easy induction.

7.2 Now take the term 2s(2^{t}, m)Z_{m} with 2 ≤ m ≤ 2^{t−1} − 3. Its valuation satisfies

v_{2}(2s(2^{t}, m)Z_{m}) ≥ 1 + ⌊\frac{2^{t} − 1}{2}⌋ + 1 − m + log_{2}(m) − 1 = 2^{t−1} − m + log_{2}(m) .

As we want to prove that v_{2}(2s(2^{t}, m)Z_{m}) ≥ t + 1, it suffices to prove that

m − log_{2}(m) ≤ 2^{t−1} − 1 − t .

Since the function x − log_{2}(x) is increasing for x ≥ 2, we only have to prove the inequality for m = 2^{t−1} − 3. This is equivalent to showing that log_{2}(2^{t−1} − 3) ≥ t − 2, or 2^{t−2} ≥ 3. This last inequality holds by the hypothesis on t.

7.3 Now take a term 2s(2^{t}, m)Z_{m} with m = 2^{t−1} − 1 or 2^{t−1} − 2. We have to prove

v_{2}(2s(2^{t}, m)Z_{m}) = 1 + v_{2}(s(2^{t}, m)) + v_{2}(Z_{m}) ≥ t + 1 .

It follows from Lemma 17 that s(2^{t}, 2^{t−1} − 1) and s(2^{t}, 2^{t−1} − 2) are divisible by 4, and, since, for these two values, we have m = 2^{t−2} + L with L ≥ 1, we know that v_{2}(Z_{m}) ≥ t − 2. Hence

v_{2}(2s(2^{t}, m)Z_{m}) ≥ 1 + 2 + t − 2 = t + 1 .

7.4 Now examine 2s(2^{t}, m)Z_{m} with 2^{t−1} + 1 ≤ m ≤ 2^{t} − 1 and m ≠ 2^{t−1} + 2^{t−2} = 3 · 2^{t−2}. By Lemma 17, s(2^{t}, m) is divisible by 4 for these values of m. Hence

v_{2}(2s(2^{t}, m)Z_{m}) ≥ 3 + v_{2}(Z_{m}) ≥ 2 + log_{2}(m) .

It suffices to prove that log_{2}(m) ≥ t − 1, or m ≥ 2^{t−1}, which is true.

7.5 Now consider the term 2s(2^{t}, m)Z_{m} with m = 2^{t−1} + 2^{t−2}. By Lemma 17, we know that s(2^{t}, m) is divisible by 2 and that

v_{2}(Z_{m}) ≥ log_{2}(m) − 1 = log_{2}(3 · 2^{t−2}) − 1 = log_{2}(3) + t − 2 − 1 > t − 2 ,

hence v_{2}(Z_{m}) ≥ t − 1. Therefore

v_{2}(2s(2^{t}, m)Z_{m}) ≥ 1 + 1 + t − 1 = t + 1 .

7.6 We are only left with the term 2s(2^{t}, m)Z_{m} with m = 2^{t−1}. By the induction hypothesis, we have v_{2}(Z_{m}) = t − 1, and we know that s(2^{t}, 2^{t−1}) is odd by Lemma 17. Hence the 2-adic valuation of this term is exactly t.

We have proved that, in the expression (4) of Z_{2^{t}}, only one term has valuation t , all the others having valuation ≥ t + 1; hence v_{2}(Z_{2^{t}}) = t. The proof is complete.

8 Proof of Theorem 8

First we show that the conjecture holds for 3·2^{h}, with 2 ≤ h ≤ 4, by numerical computations; then we proceed by induction. Suppose the result true for 2 ≤ h ≤ t − 1; let us prove it for t. By the above, we can suppose that t ≥ 5. We have to prove two facts:

(a) For m = 3 · 2^{t}, v_{2}(Z_{m}) = t + 1;

(b) For m′ > 3 · 2^{t}, v_{2}(Z_{m′}) ≥ t + 2.

First, let us prove assertion (a). Of course we use Formula (4):

Z_{n} = −s(n, 1) − 2 ∑_{m=2}^{n−1} s(n, m)Z_{m} .

Take n = 3 · 2^{t}. We will prove that all the terms in this expression are of 2-adic valuation ≥ t + 2, with the exception of only one term.

8.1 First, look at s(3 · 2^{t}, 1). Its 2-adic valuation is 3 · 2^{t} − 1 − S_{2}(3 · 2^{t} − 1). Since 3 · 2^{t} − 1 = 2^{t+1} + 2^{t−1} + ⋯ + 1 we get S_{2}(3 · 2^{t} − 1) = t + 1. We have to show that 3 · 2^{t} − 1 − t − 1 ≥ t + 2. This inequality holds for t = 1. The general case follows by an easy induction.

8.2 Now consider 2s(3·2^{t}, m)Z_{m}, with 2 ≤ m ≤ 3·2^{t−1} −2. Using Lemma 14 and Theorem 4, we easily see that its 2-adic valuation is ≥ 3·2^{t−1} −m+log_{2}(m). Hence we have only to prove that 3·2^{t−1} −t−2 ≥ m−log_{2}(m). The function x−log_{2}(x) being increasing it suffices to prove this last inequality for m = 3 · 2^{t−1} − 2. This is equivalent to showing that log_{2}(3 · 2^{t−1} − 2) ≥ t, which is obvious since 3 · 2^{t−1} − 2 = 2^{t} + (2^{t−1} − 2) ≥ 2^{t}.

8.3 Now take m = 3 · 2^{t−1} − 1 = 2^{t} + (2^{t−1} − 1). By Theorem 4, v_{2}(Z_{m}) > t − 1, therefore v_{2}(Z_{m}) ≥ t. By Lemma 19, v_{2}(s(3 · 2^{t}, m)) ≥ 2, and we are done.

8.4 Now suppose that 3 · 2^{t−1} + 1 ≤ m ≤ 3 · 2^{t} − 1, and m ∉ {2^{t+1}, 2^{t+1} + 2^{t−1}, 3 · 2^{t−1}, 3 · 2^{t} − 2^{t−2}, 3 · 2^{t−1} + 2^{t−2}}. By Lemma 19 it follows that v_{2}(s(3 · 2^{t}, m)) ≥ 2. On the other hand, m = 3 · 2^{t−1} + L = 2^{t} + L′ with L′ > 0. Then v_{2}(Z_{m}) ≥ t and this ends the case.

8.5 Now examine the two cases m_{1} = 3 · 2^{t} − 2^{t−2} and m_{2} = 3 · 2^{t−1} + 2^{t−2}. By Lemma 19, we know that v_{2}(s(3 · 2^{t}, m)) = 1 for these values of m. Since m_{1} = 2^{t+1} + (2^{t} − 2^{t−2}), v_{2}(Z_{m_{1}}) ≥ t + 1 by Theorem 4, and v_{2}(Z_{m_{2}}) ≥ t + 1 by the induction hypothesis, because m_{2} > 3 · 2^{t−1}, and this ends the case.

8.6 Now consider the two cases m_{3} = 2^{t+1} and m_{4} = 2^{t+1} + 2^{t−1}. By Lemma 19 we know that s(3 · 2^{t}, m_{j}) is odd for j = 3, 4. We have already proved that v_{2}(Z_{m_{3}}) = t + 1; hence v_{2}(2s(n, m_{3})Z_{m_{3}}) = t+2. It follows that v_{2}(Z_{m_{4}}) ≥ t+1, because m_{4} = 2^{t+1} +L with L ≥ 1, and we get v_{2}(2s(3 · 2^{t}, m_{4})Z_{m_{4}}) ≥ t + 2.

8.7 Only one value of m remains, namely, m = 3 · 2^{t−1}. We know that s(3 · 2^{t}, 3 · 2^{t−1}) is odd, and by the induction hypothesis we know that that v_{2}(Z_{m}) = t. The 2-adic valuation of this term is t + 1 and this is the only term with this property, all other terms having 2-adic valuation ≥ t + 2.

Hence v_{2}(Z_{3·2^{t}}) = t + 1, and this ends the first part of the proof of Theorem 8.

Now let us prove the second part of Theorem 8. Let n be such that n ≥ 3 · 2^{t} + 1. We want to prove that v_{2}(Z_{n}) ≥ t + 2. We use the

recurrence formula (4) again:

Z_{n} = −s(n, 1) − 2 ∑_{m=2}^{n−1} s(n, m)Z_{m} .

It is enough to show that all the terms in this formula have 2-adic valuation ≥ t + 2.

8.8 First, consider the term s(n, 1). Its 2-adic valuation is n − 1 − S_{2}(n − 1). Since S_{2}(n − 1) ≤ 1 + log_{2}(n − 1), we have to prove that (n − 1) − log_{2}(n − 1) ≥ t + 3. It suffices to prove that 3·2^{t} −log_{2}(3·2^{t}) ≥ t+3, and since log_{2}(3) < 2, that 3·2^{t} ≥ 2t+5, or 3 · 2^{t−1} ≥ t + 3. This last inequality holds for t = 2, and hence for t ≥ 2 by an easy induction.

8.9 Next, consider the case 2 ≤ m ≤ 3 · 2^{t−1} − 2. Apply Lemma 14 and Theorem 4. Using

the following inequality, valid for n ≥ 3 · 2^{t} + 1, ⌊\frac{n − 1}{2}⌋ ≥ 3 · 2^{t−1}, we have to prove

3 · 2^{t−1} + 1 − m + log_{2}(m) ≥ t + 2 ,

or

3 · 2^{t−1} − t − 1 ≥ m − log_{2}(m) .

It suffices to prove this inequality for m = 3 · 2^{t−1} − 2. It is equivalent to showing that log(3 · 2^{t−1} − 2) ≥ t − 1, or 3 · 2^{t−1} − 2 ≥ 2^{t−1}, which is clear.

8.10 Now consider the case m = 3 · 2^{t−1} − 1. We have v_{2}(s(n, m)) ≥ ⌊\frac{n − 1}{2}⌋ + 1 − m ≥

3 · 2^{t−1} + 1 − m. Hence it suffices to prove

1 + 3 · 2^{t−1} + 1 − 3 · 2^{t−1} + 1 + v_{2}(Z_{m}) ≥ t + 2 ,

i.e., 3 + v_{2}(Z_{m}) ≥ t + 2. Since m = 2^{t} + (2^{t−1} − 1) it follows that v_{2}(Z_{m}) ≥ t. The assertion is proved.

8.11 Consider the case m = 3 · 2^{t−1}. By the induction hypothesis v_{2}(Z_{m}) = t hence

v_{2}(s(n, m)) ≥ ⌊\frac{n − 1}{2}⌋+1−m ≥ 3·2^{t−1} +1−m = 1. It follows that v_{2}(2s(n, m)Z_{m}) ≥

1 + 1 + t = t + 2.

8.12 Consider the last case, where 3 · 2^{t−1} + 1 ≤ m < n. By the induction hypothesis we have v_{2}(Z_{m}) ≥ t + 1. Hence v_{2}(2s(n, m)Z_{m}) ≥ t + 2.

We have proved that all the terms in the formula giving Z_{n} have 2-adic valuation ≥ t + 2 therefore v_{2}(Z_{n}) ≥ t + 2 for n ≥ 3 · 2^{t} + 1. The proof of Theorem 8 is now complete.

9 Proof of Theorem 9

(a) With exactly the same proof as in Proposition 12, we prove another recurrence formula for the Y_{n}:

Y_{n} = −S(n, 1) + 2 ∑_{m=1}^{n} S(n, m)Y_{m} .

Since S(n, 1) = 1, this gives

Y_{n} = 1 − 2 ∑_{m=1}^{n−1} S(n, m)Y_{m} .

Hence all the Y_{n} are odd.

(b) We can suppose that n ≥ 2. By the Stirling inversion formula (5), it follows that

2Y_{n} = ∑_{m=1}^{n} s(n, m)Y_{m} .

Taking x = 1 in the formula

x(x − 1) ⋯ (x − n + 1) = ∑_{m=1}^{n} s(n, m)x^{m} ,

we get that ∑_{m=1}^{n} s(n, m) = 0. Hence it follows that

2Y_{n} = ∑_{m=1}^{n} s(n, m)(Y_{m} + 1) .

By the above equalityH_{j} = \frac{Y_{j} + 1}{2} is an integer. Hence we have

Y_{n} = 2H_{n} − 1 = ∑_{m=1}^{n} s(n, m)H_{m}

and so

H_{n} ≡ 1 + ∑_{m=1}^{n−1} s(n, m)H_{m} (mod 2) .

Now we will prove by induction that H_{n} is odd, for n congruent to 0 or 1 modulo 3, and even for n congruent to 2 modulo 3. Clearly this will prove the result. We easily check that the preceding assertion holds for the first few values of the sequence H_{n}.

By Lemma 14 we know that v_{2}(s(n, m)) ≥ M − m, where M = ⌊\frac{n − 1}{2}⌋ + 1. Therefore

H_{n} ≡ 1 + ∑_{m=M}^{n−1} s(n, m)H_{m} (mod 2) .

We also have

x(x − 1) ⋯ (x − n + 1) ≡ x^{M}(x − 1)^{n−M} (mod 2) .

This implies that s(n, M + j) ≡ \binom{n − M}{j} (mod 2). We therefore have

H_{n} ≡ 1 + ∑_{j=0}^{n−M−1} \binom{n − M}{j}H_{j+M} (mod 2) .

By the induction hypothesis, H_{j+M} is zero modulo 2 if j + M is congruent to 2 modulo 3. Hence

H_{n} ≡ 1 + ∑_{\begin{matrix}0≤j≤n−M−1 \\ M+j≡0 (mod 3) \end{matrix}} \binom{n − M}{j} + ∑_{\begin{matrix}0≤j≤n−M−1 \\ M+j≡1 (mod 3) \end{matrix}} \binom{n − M}{j} (mod 2) .

Now write n = 6k + s, s ∈ {0, 1, 2, 3, 4, 5}, and check each case.

Case s=1: We have M = 3k, n − M = 3k. Hence

H_{n} = 1 + ∑_{\begin{matrix}0≤j≤3k−1 \\ j≡0 (mod 3) \end{matrix}} \binom{3k}{j} + ∑_{\begin{matrix}0≤j≤3k−1 \\ j≡1 (mod 3) \end{matrix}} \binom{3k}{j} (mod 2) ,

which can be written as follows:

H_{n} ≡ Γ_{0,0,k} + Γ_{1,0,k} (mod 2) .

From case (b) of Lemma 20 it follows that

3(Γ_{0,0,k} + Γ_{1,0,k}) = 2^{3k+1} + (−1)^{3k} ,

hence H_{n} is odd. Case s=2: It follows that M = 3k + 1 and n − M = 3k. Hence

H_{n} ≡ 1 + ∑_{\begin{matrix}0≤j≤3k−1 \\ j≡2 (mod 3) \end{matrix}} \binom{3k}{j} + ∑_{\begin{matrix}0≤j≤3k−1 \\ j≡0 (mod 3) \end{matrix}} \binom{3k}{j} (mod 2) ,

which can be written as follows:

H_{n} ≡ Γ_{2,1,k} + Γ_{0,1,k} (mod 2) .

By Lemma 20, we have

3(Γ_{2,1,k} + Γ_{0,1,k}) = 2^{3k+2} + (−1)^{3k+1} ,

and hence H_{n} is odd. Case s=3: It follows that M = 3k + 1 and n − M = 3k + 1. Hence

H_{n} ≡ 1 + ∑_{\begin{matrix}0≤j≤3k \\ j≡2 (mod 3) \end{matrix}} \binom{3k + 1}{j} + ∑_{\begin{matrix}0≤j≤3k \\ j≡0 (mod 3) \end{matrix}} \binom{3k + 1}{j} (mod 2) ,

which can be written as follows:

H_{n} ≡ 1 + Γ_{2,1,k} + Γ_{0,1,k} (mod 2) .

By Lemma 20

3(Γ_{2,1,k} + Γ_{0,1,k}) = 2^{3k+2} + (−1)^{3k+1}

hence H_{n} is even. Case s=4: It follows that M = 3k + 2 and n − M = 3k + 1. Hence

H_{n} ≡ 1 + ∑_{\begin{matrix}0≤j≤3k \\ j≡1 (mod 3) \end{matrix}} \binom{3k + 1}{j} + ∑_{\begin{matrix}0≤j≤3k \\ j≡2 (mod 3) \end{matrix}} \binom{3k + 1}{j} (mod 2) ,

which can be written as follows:

H_{n} ≡ Γ_{1,1,k} + Γ_{2,1,k} (mod 2) .

By Lemma 20 we have

3(Γ_{1,1,k} + Γ_{2,1,k}) = 2^{3k+2} + (−1)^{3k+1} ,

and hence H_{n} is odd. Case s=5: It follows that M = 3k + 2 and n − M = 3k + 2. Hence

H_{n} ≡ 1 + ∑_{\begin{matrix}0≤j≤3k+1 \\ j≡1 (mod 3) \end{matrix}} \binom{3k + 2}{j} + ∑_{\begin{matrix}0≤j≤3k+1 \\ j≡2 (mod 3) \end{matrix}} \binom{3k + 2}{j} (mod 2) ,

which can be written as follows:

H_{n} ≡ 1 + Γ_{1,2,k} + Γ_{2,2,k} (mod 2) .

By Lemma 20

3(Γ_{2,1,k} + Γ_{0,1,k}) = 2^{3k+3} + (−1)^{3k+2} ,

and hence H_{n} is odd. Case s=6: It follows that M = 3k + 3 and n − M = 3k + 2. Hence

H_{n} ≡ 1 + ∑_{\begin{matrix}0≤j≤3k+1; \\ j≡0 (mod 3) \end{matrix}} \binom{3k + 2}{j} + ∑_{\begin{matrix}0≤j≤3k+1; \\ j≡1 (mod 3) \end{matrix}} \binom{3k + 2}{j} (mod 2) ,

which can be written as follows:

H_{n} ≡ 1 + Γ_{0,2,k} + Γ_{1,2,k} (mod 2) .

By Lemma 20 we have

3(Γ_{0,2,k} + Γ_{1,2,k}) = 2^{3k+3} + (−1)^{3k+2} ,

and hence H_{n} is even. The proof of Theorem 9 is now complete.

10 Proof of property (a) of Theorem 10

We use induction on n. For 1 ≤ n ≤ p, the property holds, because log_{p}(n) − 1 ≤ 0. Now suppose the property holds for m ≤ n−1, we have to show the property for n. By the above, one can suppose that n ≥ p + 1.

It is enough to prove that all the terms in Formula (6)

Z_{n}^{⟨p⟩} = s(n, 1) − \frac{p}{p − 1} ∑_{m=1}^{n−1} s(n, m)Z_{m}^{⟨p⟩}

have a p-adic valuation ≥ log_{p}(n) − 1.

10.1 Begin with s(n, 1) = (−1)^{n−1}(n − 1)!. Its p-adic valuation is \frac{n − 1 − S_{p}(n − 1)}{p − 1}. We

have to prove that this quantity is ≥ log_{p}(n) − 1. Write n − 1 = a_{0} + a_{1}p + ⋯ + a_{m}p^{m}, with a_{k} ∈ {0, ⋯, p−1} and a_{m} ≠ 0. We have n ≤ 1+(p−1)(1+p+⋯+p^{m}) = p^{m+1}; hence log_{p}(n) ≤ m + 1. It suffices to prove

a_{1} + a_{2}(1 + p) + ⋯ + a_{m}(1 + p + ⋯ + p^{m−1}) ≥ m .

But in the sum 1 + p + ⋯ + p^{m−1}, all terms are ≥ 1, the second term is ≥ 3, and a_{m} ≥ 1, and we are done.

10.2 Now let m be such that 1 ≤ m ≤ ⌊\frac{n − 1}{p}⌋ + 1. One can neglect the factor \frac{1}{p − 1}. We

have hence to prove

v_{p}(ps(n, m)Z_{m}^{⟨p⟩}) = 1 + v_{p}(s(n, m)) + v_{p}(Z_{m}^{⟨p⟩}) ≥ log_{p}(n) − 1 .

Using Lemma 14 and the induction hypothesis, it suffices to prove

1 + ⌊\frac{n − 1}{p}⌋ + 1 − m + log_{p}(m) − 1 ≥ log_{p}(n) − 1 ,

or

⌊\frac{n − 1}{p}⌋ + 2 − log_{p}(n) ≥ m − log_{p}(m) .  (8)

There are two cases \begin{cases}(a): & n divisible by p; \\ b): & n not divisible by p. \end{cases} (a) Suppose that n is divisible by p. Let n = kp. It follows that ⌊\frac{n − 1}{p}⌋ = k − 1;

hence 1 ≤ m ≤ k. We then have to prove

k − log_{p}(k) ≥ m − log_{p}(m) ,

which holds because the function x − log_{p}(x) is increasing for x ≥ 1.

(b) Suppose that n is not divisible by p Let n = kp + r, with 1 ≤ r ≤ p − 1. it follows that 1 ≤ m ≤ k + 1. First examine the case m = k + 1; we have to prove that

k + 2 − log_{p}(kp + r) ≥ k + 1 − log_{p}(k + 1) ,

or p(k + 1) ≥ kp + r, which is true. Hence we can suppose m ≤ k. Since k + 1 − log_{p}(k + 1) ≥ m − log_{p}(m), It follows that relation (8) is also satisfied in this case .

10.3 Now suppose that ⌊\frac{n − 1}{p}⌋ + 2 ≤ m ≤ n − 1. Using the induction hypothesis again,

v_{p}(Z_{m}^{⟨p⟩}) ≥ log_{p}(m) − 1, we get

v_{p}(ps(n, m)Z_{m}^{⟨p⟩}) ≥ 1 + v_{p}(Z_{m}^{⟨p⟩}) ≥ log_{p}(m) .

We want to prove that log_{p}(m) ≥ log_{p}(n) − 1, or p · m ≥ n. Suppose on the contrary

that p · m ≤ n − 1. It follows that m ≤ ⌊\frac{n − 1}{p}⌋, in contradiction with hypothesis:

m ≥ ⌊\frac{n − 1}{p}⌋ + 2.

The proof of property (a) of Theorem 10 is now complete.

11 Proof of property (b) of Theorem 10

We proceed by induction. We have seen (cf. Remark 13) that Z_{p}^{⟨p⟩} is a p-adic unit; hence v_{p}(Z_{p}^{⟨p⟩}) = 0, which is property (b) for t = 1.

Now suppose property (b) satisfied for n = p^{k}, with 1 ≤ k ≤ t − 1. We want to prove it for n = p^{t}. One can suppose that t ≥ 2. We use formula (6) again:

Z_{n}^{⟨p⟩} = s(n, 1) − \frac{p}{p − 1} ∑_{m=1}^{n−1} s(n, m)Z_{m}^{⟨p⟩} .

We will prove that all terms in the above formula have p-adic valuation greater than t, with the only exception of the term with index m = p^{t−1}, which has p-adic valuation t − 1.

11.1 First, consider the term s(n, 1) = (−1)^{n−1}(n − 1)!. Its p-adic valuation is

\frac{n − 1 − S_{p}(n − 1)}{p − 1} = 1 + p + ⋯ + p^{t−1} − t = (p − 1) + ⋯ + (p^{t−1} − 1) .

All the terms in this sum are ≥ 1, and for example the first one is ≥ 2 and hence the sum is ≥ t.

11.2 Now suppose that 1 ≤ m ≤ p^{t−1} − 2. It follows that

v_{p}(ps(n, m)Z_{m}^{⟨p⟩}) ≥ 1 + ⌊\frac{n − 1}{p}⌋ + 1 − m + log_{p}(m) − 1 .

It suffices to show that

⌊\frac{n − 1}{p}⌋ + 1 − t ≥ m − log_{p}(m) .

Since ⌊\frac{n − 1}{p}⌋ + 1 = p^{t−1}, we have to prove

p^{t−1} − t ≥ m − log_{p}(m) .

Since the function x − log_{p}(x) is increasing for x ≥ 1, it suffices to show

p^{t−1} − t ≥ p^{t−1} − 2 − log_{p}(p^{t−1} − 2) ,

or p^{t−1} − 2 ≥ p^{t−2}, which is obvious.

11.3 Now consider the term of index m = p^{t−1} − 1. By Lemma 15, we know that s(n, m) = s(p^{t}, p^{t−1} − 1) is divisible by p. It follows that

v_{p}(p · s(n, m)Z_{m}^{⟨p⟩}) ≥ 1 + 1 + v_{p}(Z_{m}^{⟨p⟩}) ≥ 2 + v_{p}(Z_{m}^{⟨p⟩}) .

Since m > p^{t−2}, it also follows that v_{p}(Z_{m}^{⟨p⟩}) > t − 3 by property (a) of Theorem 10. Hence v_{p}(Z_{m}^{⟨p⟩}) ≥ t − 2 and we are done.

11.4 Now take m such that p^{t−1} + 1 ≤ m ≤ 2^{t} − 1. By property (a) of Theorem 10, we know that v_{p}(Z_{m}^{⟨p⟩}) ≥ t − 1 for such m. It follows that

v_{p}(p · s(2^{t}, m)Z_{m}^{⟨p⟩}) ≥ t ,

and we are done for this case also.

11.5 Now consider the value m = p^{t−1}. By the induction hypothesis, it follows that v_{p}(Z_{m}^{⟨p⟩}) = t − 2. By Lemma 15, s(n, m) = s(2^{t}, 2^{t−1})) is not divisible by p. It follows that the p-adic valuation of ps(n, m)Z_{m}^{⟨p⟩} is exactly t − 1, and this is the only term in the sum with this valuation, all the others have valuation ≥ t.

Hence v_{p}(Z_{p^{t}}^{⟨p⟩}) = t − 1. The proof of Theorem 10 is now complete.

12 Acknowledgments

We thank the anonymous referee for her/his careful reading, and for suggesting a more elegant proof of Proposition 12 and many other improvements. We also thank Fred Weissler for his help.

References

[1] Y. Amice, Les Nombres p-adiques, Presses universitaires de France, 1975.

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

[3] F. T. Howard, Congruences for the Stirling numbers and associated Stirling numbers. Acta Arith. 55 (1990), 29–41.

[4] T. Lengyel, On some 2-adic properties of a recurrence involving Stirling numbers. p-Adic Numbers Ultrametric Anal. Appl. 4 (2012), 179–186.

[5] N. J. A. Sloane, The Online Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 11B73; Secondary 11F85. Keywords: Lengyel’s sequence, Stirling number, congruence, p-adic property.

(Concerned with sequence \underline{A005121}.)

Received January 24 2014; revised version received June 2 2014; June 16 2014. Published in Journal of Integer Sequences, June 17 2014.

Return to Journal of Integer Sequences home page.