On the Periodicity Problem for Residual r-Fubini Sequences

Amir Abbas Asgari

National Organization for Development of Exceptional Talents (NODET) Tehran Iran

                    asgari@helli.ir

Majid Jahangiri School of Mathematics Department of Science Shahid Rajaee Teacher Training University P. O. Box 16785-163 Tehran Iran

                   jahangiri@ipm.ir

Abstract

For any positive integer r, the r-Fubini number with parameter n, denoted by F_{n,r}, is equal to the number of ways that the elements of a set with n + r elements can be weakly ordered such that the r least elements are in distinct orders. In this article we focus on the sequence of residues of the r-Fubini numbers modulo an arbitrary positive integer s and show that this sequence is periodic and then, exhibit how to calculate its period length.

1 Introduction

The Fubini numbers (also known as the ordered Bell numbers) form an integer sequence in which the nth term counts the number of weak orderings of a set with n elements. Weak ordering means that the elements can be ordered, allowing ties. Cayley [2] studied the Fubini numbers as the number of a certain kind of trees with n + 1 terminal nodes. The Fubini numbers can also be defined as the sum of the Stirling numbers of the second kind, \left\{{n \atop k}\right\}, which counts the number of partitions of an n-element set into k non-empty subsets. The sequence of residues of the Fubini numbers modulo a positive integer s was studied by Poonen [6]. He showed that this sequence is periodic and calculated the period length for each positive integer s.

The r-Stirling numbers of the second kind are defined as an extension to the Stirling numbers of the second kind, in which the first r elements contained in distinct subsets. Similarly the r-Fubini numbers, which are denoted by F_{n,r}, are defined as the number of ways which the elements of a set with n + r elements can be weakly ordered such that the first r elements are in distinct places. Consider the sequence of remainders of F_{n,r} modulo an arbitrary number s ∈ ℕ in which r is fixed, which is denoted by A_{r,s}. One can study the periodicity problem for this sequence. Mező [4] investigated this problem for s = 10. In this article ω(A_{r,s}), the period of A_{r,s}, is computed for any positive integer s. Based on the fundamental theorem of arithmetic, ω(A_{r,p}) is calculated for powers of odd primes p^{m}. The cases s = 2^{m} are studied separately. Therefore if s = 2^{m}p_{1}^{m_{1}}p_{1}^{m_{1}} ⋯ p_{k}^{m_{k}} is the prime factorization, then the ω(A_{r,s}) is equal to the least common multiple of ω(A_{r,p_{i}^{m_{i}}})s and ω(A_{r,2^{m}}), for i = 1, 2, …, k.

Section 2 contains the basic definitions and relations. The length of the periods in the case of odd prime powers are computed in the Section 3. The similar results about the 2 powers are stated in the Section 4. The last section contains the final theorem which presents the conclusion of the article.

2 Basic concepts

Let \left\{{n \atop k}\right\} be the Stirling number of the second kind with the parameters n and k and let \left\{{n \atop k}\right\}_{r} be the r-Stirling number of the second kind with parameters n and k. It is clear that n ≥ k ≥ r. Fubini numbers are computed as follows [4]:

F_{n} = ∑_{k=0}^{n} k!\left\{{n \atop k}\right\}.

In a similar way we can evaluate the r-Fubini number F_{n,r} by

F_{n,r} = ∑_{k=0}^{n}(k + r)!\left\{{n + r \atop k + r}\right\}_{r}.

There are simple relations and formulae about \left\{{n \atop k}\right\}_{r} which are listed below. One can find a proof of them in [1, 4, 5] and [3, Thm. 4.5.1, p. 158].

\left\{{n \atop m}\right\}_{r} = \left\{{n \atop m}\right\}_{r−1} − (r − 1)\left\{{n − 1 \atop m}\right\}_{r−1}, 1 ≤ r ≤ n  (1)
\left\{{n \atop m}\right\}_{1} = \left\{{n \atop m}\right\}  (2)
\left\{{n + r \atop r}\right\}_{r} = r^{n}  (3)
\left\{{n + r \atop r + 1}\right\}_{r} = (r + 1)^{n} − r^{n}  (4)
\left\{{n \atop m}\right\} = \frac{1}{m!} ∑_{j=1}^{m}(−1)^{m−j}\binom{m}{j}j^{n}  (5)

\left\{{n \atop m}\right\}_{r} = \frac{1}{m!} ∑_{j=r}^{m}(−1)^{m−j}\binom{m}{j}j^{n−(r−1)} (\frac{(j − 1)!}{(j − r)!}) .  (6)

By φ(n) we indicate the number of positive integer numbers less than n and co-prime to it. It is known as Euler’s totient function. The value of φ(n) can be computed via the following relation [3, Example 4.7.3, p. 167]:

φ(n) = n ∏_{p|n}(1 − \frac{1}{p}).

3 The r-Fubini residues modulo prime powers

Let p be a prime number greater than 2 and m be a positive integer. If (F_{n,r}) denotes the sequence of r-Fubini numbers for a fixed positive integer r, we indicate by A_{r,q} = (F_{n,r}(mod q)), for n ∈ ℕ, the sequence of residues of the r-Fubini numbers modulo the positive integer q. In this section we try to compute the period length of the sequence A_{r,q} when q = p^{m}. This length is denoted by ω(A_{r,q}).

Proposition 1. Let p be an odd prime and let q = p^{m}, m ∈ ℕ. If q ≤ r, then ω(A_{r,q}) = 1.

Proof. The proof is very simple. Since p ≤ r, we can deduce that p | (k + r)!, for k ≥ 0, and by the relation F_{n,r} = ∑_{k=0}^{n}(k + r)!\left\{{n+r \atop k+r}\right\}_{r}, we have p | F_{n,r}. Therefore ω(A_{r,p}) = 1.

As pointed out in the above proposition, it is sufficient to investigate the period length in the cases of q > r.

Lemma 2. Let p be an odd prime and r, m ∈ ℕ with p ≥ r + 1. Then

p^{m} − r ≥ m.

Proof. For m = 1 the result is obvious. Suppose the inequality holds for any m ≥ 2. Since p(p + m) > 2(p + m) > 2p + m, we have

p^{2} + pm − p ≥ p + m.  (7)

Since p − 1 ≥ r, the induction hypothesis can be reformulated to p^{m} ≥ p − 1 + m. Multiplication by p results p^{m+1} ≥ p^{2} + pm − p. By (7) we have p^{m+1} ≥ p + (m + 1) − 1.

Theorem 3. Let p be an odd prime and q = p^{m}. After the (m − 1)th term the sequence A_{r,q} has a period with length ω(A_{r,q}) = φ(q). In other words, F_{n+φ(q),r} ≡ F_{n,r} (mod q), for n ≥ m − 1.

Proof. If n ≥ q − r − 1 we can write

F_{n+φ(q),r} − F_{n,r} = ∑_{k=0}^{n+φ(q)}(k + r)!\left\{{n + φ(q) + r \atop k + r}\right\}_{r} − ∑_{k=0}^{n}(k + r)!\left\{{n + r \atop k + r}\right\}_{r}

≡ ∑_{k=0}^{q−r−1}(k + r)! (\left\{{n + φ(q) + r \atop k + r}\right\}_{r} − \left\{{n + r \atop k + r}\right\}_{r})

≡ ∑_{k=0}^{q−r−1} ∑_{j=r}^{k+r}(−1)^{k+r−j}\binom{k + r}{j}j^{n+1} (\frac{(j − 1)!}{(j − r)!}) (j^{φ(q)} − 1) (mod q).

If j = cp, c ∈ ℕ, then j^{n+1} = (cp)^{q−r+h}, for some h ≥ 0, so from Lemma 2 it follows that j^{n+1} ≡ 0 (mod q). If gcd(j, q) = 1, by Euler’s theorem j^{φ(q)} − 1 ≡ 0 (mod q), so the right hand side of the above congruence relation vanished and we have

F_{n+φ(q),r} ≡ F_{n,r} (mod q), for n ≥ q − r − 1.  (8)

If m − 1 ≤ n < q − r − 1 then

F_{n+φ(q),r} − F_{n,r} ≡ ∑_{k=0}^{q−r−1}(k + r)! (\left\{{n + φ(q) + r \atop k + r}\right\}_{r} − \left\{{n + r \atop k + r}\right\}_{r})

− ∑_{k=n+φ(q)+1}^{q−r−1}(k + r)!\left\{{n + φ(q) + r \atop k + r}\right\}_{r} + ∑_{k=n+1}^{q−r−1}(k + r)!\left\{{n + r \atop k + r}\right\}_{r}

≡ ∑_{k=0}^{q−r−1} ∑_{j=r}^{k+r}(−1)^{k+r−j}\binom{k + r}{j}j^{n+1} (\frac{(j − 1)!}{(j − r)!}) (j^{φ(q)} − 1)

− ∑_{k=n+φ(q)+1}^{q−r−1}(k + r)!\left\{{n + φ(q) + r \atop k + r}\right\}_{r} + ∑_{k=n+1}^{q−r−1}(k + r)!\left\{{n + r \atop k + r}\right\}_{r} (mod q).

Since n ≥ m−1, in the indices where j = cp, c ∈ ℕ, we have j^{n+1} = (cp)^{m+h}, for some h ≥ 0, and it is deduced that j^{n+1} ≡ 0 (mod q). When gcd(j, q) = 1, again j^{φ(q)} − 1 ≡ 0 (mod q) by Euler’s theorem. In the sums ∑_{k=n+1}^{q−r−1}(k + r)!\left\{{n+r \atop k+r}\right\}_{r} and ∑_{k=n+φ(q)+1}^{q−r−1}(k + r)!\left\{{n+φ(q)+r \atop k+r}\right\}_{r} the upper parameter of the r-Stirling number is less than the lower one, and therefore these two sums are equal to zero. So

F_{n+φ(q),r} − F_{n,r} ≡ ∑_{k=0}^{q−r−1} ∑_{j=r}^{k+r}(−1)^{k+r−j}\binom{k + r}{j}j^{n+1} (\frac{(j − 1)!}{(j − r)!}) (j^{φ(q)} − 1) ≡ 0 (mod q),

and therefore

F_{n+φ(q),r} ≡ F_{n,r} (mod q) for m − 1 ≤ n < q − r − 1.  (9)

Combining results (8) and (9) gives F_{n+φ(q),r} ≡ F_{n,r} (mod q), for n ≥ m − 1.

4 The r-Fubini residues modulo powers of 2

As in many other computations in number theory, the case of p = 2 has its own difficulties that require special attention. In the case of powers of 2, initially we calculate the residues of 2-Fubini numbers and then use the results in the case of the r-Fubini numbers. We classify the sequence of remainders of 2-Fubini numbers modulo 2^{m}, m ≥ 7, in Theorem 6 and then, work on remainders of the r-Fubini numbers modulo 2^{m}, m ≥ 7 in Theorem 9. The special cases will be proved in Theorems 4, 7 and 8. The trivial cases in which 2^{m} ≤ r with period length 1 are omitted.

Theorem 4. If 3 ≤ m ≤ 6, then after the (m − 1)th term the sequence A_{2,2^{m}} has a period with length ω(A_{2,2^{m}}) = 2.

Proof. By using the formula F_{n,2} = ∑_{k=0}^{n}(k + 2)!\left\{{n+2 \atop k+2}\right\}_{2} we prove that F_{n+2,2} − F_{n,2} ≡ 0 (mod 64). Then F_{n+2,2} − F_{n,2} ≡ 0 (mod 2^{m}) for 3 ≤ m ≤ 5.

F_{n+2,2} − F_{n,2} = ∑_{k=0}^{n+2}(k + 2)!\left\{{n + 4 \atop k + 2}\right\}_{2} − ∑_{k=0}^{n}(k + 2)!\left\{{n + 2 \atop k + 2}\right\}_{2}

≡ ∑_{k=0}^{5}(k + 2)! (\left\{{n + 4 \atop k + 2}\right\}_{2} − \left\{{n + 2 \atop k + 2}\right\}_{2})

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

In the case m = 6 then n ≥ 5, so if j is even, then j^{n+1} = (2c)^{6+h}, for some h ≥ 0 and therefore 64 | j^{n+1}. For odd j we have gcd(j, 64) = 1, so by Euler’s theorem we have j^{32} ≡ 1 (mod 64), and therefore j^{n+1+32} ≡ j^{n+1} (mod 64). This implies that

F_{n+2,2} − F_{n,2} ≡ ∑_{k=0}^{5} ∑_{l=1}^{⌊(k+1)/2⌋}(−1)^{k+2−(2l+1)}\binom{k + 2}{2l + 1}(2l + 1)^{n+1} ((2l + 1)^{2} − 1) × 2l

≡ 16 ∑_{k=0}^{5}(−1)^{k+1} ∑_{l=1}^{⌊(k+1)/2⌋} \binom{k + 2}{2l + 1}(2l + 1)^{n+1} (\frac{l(l + 1)}{2}) l (mod 64).

Enumerating the last summation for 2 ≤ n ≤ 33 shows that it is divisible by 64 and because of periodicity of remainders of j^{n+1} modulo 64, the result follows.

Analogous to Lemma 2, it can be easily deduced by induction, showing that for each positive integer m > 1 we have

2^{m} − 2 ≥ m .  (10)

This can be shown by using the relation 2^{m+1} ≥ 2m + 4 > m + 3, for m > 1. The following lemma provides a simple but essential relation used in the next theorem. Its proof is provided in Appendix A.

Lemma 5. For m ≥ 7 and 5 ≤ i ≤ 2^{m−6} we have 2^{m−6} − i | 2^{i−5}\binom{2^{m−6}−1}{i}.

Theorem 6. If m ≥ 7, after the (m − 1)th term, the sequence A_{2,2^{m}} has a period with length ω(A_{2,2^{m}}) = 2^{m−6}.

Proof. In the case of n ≥ 2^{m} − 3, from (10) we can deduce that n ≥ 2^{m} − 3 ≥ m − 1. So we have

F_{n+2^{m−6},2} − F_{n,2} ≡ ∑_{k=0}^{n+2^{m−6}}(k + 2)!\left\{{n + 2^{m−6} + 2 \atop k + 2}\right\}_{2} − ∑_{k=0}^{n}(k + 2)!\left\{{n + 2 \atop k + 2}\right\}_{2}

≡ ∑_{k=0}^{2^{m}−3}(k + 2)! (\left\{{n + 2^{m−6} + 2 \atop k + 2}\right\}_{2} − \left\{{n + 2 \atop k + 2}\right\}_{2})

≡ ∑_{k=0}^{2^{m}−3} ∑_{j=2}^{k+2}(−1)^{k+2−j}\binom{k + 2}{j}j^{n+1}(j^{2^{m−6}} − 1)(j − 1) (mod 2^{m}).

When j is even, then j^{n+1} = (2c)^{2^{m}−2+h}, for some h ≥ 0. So by (10), 2^{m} | j^{n+1}. For odd j we have

F_{n+2^{m−6},2} − F_{n,2} ≡ ∑_{k=0}^{2^{m}−3} ∑_{l=1}^{⌊(k+1)/2⌋}(−1)^{k+2−(2l+1)}\binom{k + 2}{2l + 1}(2l + 1)^{n+1}((2l + 1)^{2^{m−6}} − 1) × 2l

≡ 2^{m−4} ∑_{k=0}^{2^{m}−3}(−1)^{k+1} ∑_{l=1}^{⌊(k+1)/2⌋} \binom{k + 2}{2l + 1}(2l + 1)^{n+1} (\frac{(2l + 1)^{2^{m−6}} − 1}{2^{m−5}}) l

≡ 2^{m−4} ∑_{k=0}^{2^{m}−3}(−1)^{k+1} ∑_{l=1}^{⌊(k+1)/2⌋} \binom{k + 2}{2l + 1}(2l + 1)^{n+1} ∑_{i=1}^{2^{m−6}} l^{i}2^{i−1} (\frac{(2^{m−6} − 1)!}{i!(2^{m−6} − i)!})

× l (mod 2^{m}).

The last expression contains m − 4 factors of 2, so it is sufficient to prove that the last summation is divisible by 16. This summation is denoted by S. Simplify the summation ∑_{i=1}^{2^{m−6}} l^{i}2^{i−1} \frac{(2^{m−6}−1)!}{i!(2^{m−6}−i)!} and using Lemma 5 gives

∑_{i=1}^{2^{m−6}} l^{i}2^{i−1} (\frac{(2^{m−6} − 1)!}{i!(2^{m−6} − i)!}) ≡ ∑_{i=1}^{4} l^{i}2^{i−1} (\frac{(2^{m−6} − 1)!}{i!(2^{m−6} − i)!}) ≡ l + l^{2}(2^{m−6} − 1)

+ \frac{l^{3} × 2(2^{m−6} − 1)(2^{m−6} − 2)}{3} + \frac{l^{4}(2^{m−6} − 1)(2^{m−6} − 2)(2^{m−6} − 3)}{3} (mod 16).

Assume m ≥ 10 (the case 7 ≤ m ≤ 9 is studied at the end of the proof). So 16 | 2^{m−6}. Let 3a = 2(2^{m−6} − 1)(2^{m−6} − 2) and 3b = (2^{m−6} − 1)(2^{m−6} − 2)(2^{m−6} − 3). Then 3a ≡ 4 (mod 16) and 3b ≡ −6 (mod 16). Therefore a ≡ −4 (mod 16) and b ≡ −2 (mod 16). So the proof continues as follows:

S ≡ ∑_{k=0}^{2^{m}−3}(−1)^{k+1} ( ∑_{l=1}^{⌊(k+1)/2⌋} \binom{k + 2}{2l + 1}(2l + 1)^{n+1}(l − l^{2} − 4l^{3} − 2l^{4})l) (mod 16)

S ≡ ∑_{k=0}^{2^{m}−3}(−1)^{k+1} ∑_{l=1}^{⌊(k+1)/2⌋} \binom{k + 2}{2l + 1}(2l + 1)^{n+1} (\frac{l(l + 1)}{2}) (−2l^{2} − 2l + 1)l (mod 8).

Let P (l) and A(k, r, n) be the remainder of \frac{1}{2}(2l + 1)^{n+1}(l(l + 1))(−2l^{2} − 2l + 1)l and ∑_{l=−∞}^{∞} \binom{k+2}{2l+r}P (l) divided by 8, respectively. By Pascal’s identity, we have \binom{k+2}{2l+r} = \binom{k+1}{2l+r} + \binom{k+1}{2l+r−1} and therefore

∑_{l=−∞}^{∞} \binom{k + 2}{2l + r}P (l) = ∑_{l=−∞}^{∞} \binom{k + 1}{2l + r}P (l) + ∑_{l=−∞}^{∞} \binom{k + 1}{2l + r − 1}P (l),

so

A(k, r, n) = A(k − 1, r, n) + A(k − 1, r − 1, n).  (11)

We can write

A(k, r + 32, n) ≡ ∑_{l=−∞}^{∞} \binom{k + 2}{2l + r + 32}P (l) (mod 8).

The sequence (P (l))_{l=−∞}^{∞} has period 16, so P (l + 16) = P (l). Set l′ = l + 16, then

A(k, r + 32, n) ≡ ∑_{l′=−∞}^{∞} \binom{k + 2}{2l′ + r}P (l′) ≡ A(k, r, n) (mod 8).  (12)

Since gcd(2l + 1, 16) = 1, Euler’s theorem implies (2l + 1)^{8} ≡ 1 (mod 16) and therefore (2l + 1)^{n+1+8} ≡ (2l + 1)^{n+1} (mod 16). The quantity A(6, r, n) vanishes for 1 ≤ r ≤ 32 and 9 ≤ n ≤ 24, by enumeration, then by (11) and (12), we deduce that

A(k, r, n) = 0, for k ≥ 6.  (13)

Therefore

A(k, 1, n) ≡ ∑_{l=−∞}^{∞} \binom{k + 2}{2l + 1}(2l + 1)^{n+1} (\frac{l(l + 1)}{2}) (−2l^{2} − 2l + 1)l

≡ ∑_{l=1}^{⌊(k+1)/2⌋} \binom{k + 2}{2l + 1}(2l + 1)^{n+1} (\frac{l(l + 1)}{2}) (−2l^{2} − 2l + 1)l ≡ 0 (mod 8),

for k ≥ 6. If 1 ≤ k ≤ 5, 9 ≤ n ≤ 24 and 1 ≤ r ≤ 32 we have ∑_{k=1}^{5}(−1)^{k+1}A(k, r, n) ≡ 0 (mod 8). The period length of A(k, r, n) with respect to r and n implies that

∑_{k=1}^{5}(−1)^{k+1}A(k, 1, n) ≡ 0 (mod 8), for n ≥ 9.

Combining this with (13) we have

S ≡ ∑_{k=1}^{2^{m}−3}(−1)^{k+1}A(k, 1, n) ≡ 0 (mod 8), for n ≥ 0.

So the result follows in the case of n ≥ 2^{m} − 3. If m − 1 ≤ n < 2^{m} − 3 we can write

F_{n+2^{m−6},2} − F_{n,2} = ∑_{k=0}^{n+2^{m−6}}(k + 2)!\left\{{n + 2^{m−6} + 2 \atop k + 2}\right\}_{2} − ∑_{k=0}^{n}(k + 2)!\left\{{n + 2 \atop k + 2}\right\}_{2}

= ∑_{k=0}^{2^{m}−3}(k + 2)! (\left\{{n + 2^{m−6} + 2 \atop k + 2}\right\}_{2} − \left\{{n + 2 \atop k + 2}\right\}_{2})

− ∑_{k=n+2^{m−6}+1}^{2^{m}−3}(k + 2)!\left\{{n + 2^{m−6} + 2 \atop k + 2}\right\}_{2} + ∑_{k=n+1}^{2^{m}−3}(k + 2)!\left\{{n + 2 \atop k + 2}\right\}_{2}

≡ ∑_{k=0}^{2^{m}−3} ∑_{j=1}^{k+2}(−1)^{k+2−j}\binom{k + 2}{j}j^{n+1}(j^{2^{m−6}} − 1)(j − 1) (mod 2^{m}).

When j is even, then j^{n+1} = (2c)^{m+h}, for some h ≥ 0, so 2^{m} | j^{n+1}. Since m ≥ 10, for odd j we have

∑_{k=0}^{2^{m}−3} ∑_{j=1}^{k+2}(−1)^{k+2−j}\binom{k + 2}{j}j^{n+1}(j^{2^{m−6}} − 1)(j − 1)

≡ 2^{m−4} ∑_{k=0}^{2^{m}−3}(−1)^{k+1} ∑_{l=1}^{⌊(k+1)/2⌋} \binom{k + 2}{2l + 1}(2l + 1)^{n+1}(l − l^{2} − 4l^{3} − 2l^{4})l (mod 2^{m}).

The last summation is exactly the S and the proof will be similar as above. Combine with the previous case we have the following congruence relation

F_{n+2^{m−6},2} ≡ F_{n,2} (mod 2^{m}), for m ≥ 10.  (14)

In the case where 7 ≤ m ≤ 9, the remainder value of the sum

∑_{k=0}^{2^{m}−3}(−1)^{k+1} ∑_{l=1}^{⌊(k+1)/2⌋} \binom{k + 2}{2l + 1}(2l + 1)^{n+1} (∑_{i=1}^{4} l^{i}2^{i−1} \frac{(2^{m−6} − 1)!}{i!(2^{m−6} − i)!}) l

modulo 16 is computed for m − 1 ≤ n ≤ m + 14. Divisibility of all these values by 16 implies that the recent sum is divisible by 16, and therefore

F_{n+2^{m−6},2} ≡ F_{n,2} (mod 2^{m}), for 7 ≤ m ≤ 9.  (15)

Summing up the congruence relations (14) and (15) gives

ω(A_{2,2^{m}}) = 2^{m−6}, for m ≥ 7.

Theorem 7. For m = 1 and m = 2, the sequence A_{r,2^{m}} is periodic from the first term and the period length is ω(A_{r,2^{m}}) = 1.

Proof. The proof of this theorem is divided into three cases. For r = 2 we have

F_{n+1,2} − F_{n,2} = ∑_{k=0}^{n+1}(k + 2)!\left\{{n + 3 \atop k + 2}\right\}_{2} − ∑_{k=0}^{n}(k + 2)!\left\{{n + 2 \atop k + 2}\right\}_{2}

≡ 2 (\left\{{n + 3 \atop 2}\right\}_{2} − \left\{{n + 2 \atop 2}\right\}_{2}) + 6 (\left\{{n + 3 \atop 3}\right\}_{2} − \left\{{n + 2 \atop 3}\right\}_{2}) (mod 4)

= 2 (2^{n+1} − 2^{n}) + 6 (3^{n+1} − 2^{n+1} − (3^{n} − 2^{n}))

= 2^{n+1} + 6(2 × 3^{n} − 2^{n}) = 4(2^{n−1} + 3^{n+1} − 3 × 2^{n−1})

= 4(3^{n+1} − 2^{n}) ≡ 0 (mod 4).

So we can deduce that ω(A_{2,4}) = 1 and obviously ω(A_{2,2}) = 1.

For r = 3 we can write

F_{n+1,3} − F_{n,3} = ∑_{k=0}^{n+1}(k + 3)!\left\{{n + 4 \atop k + 3}\right\}_{3} − ∑_{k=0}^{n}(k + 3)!\left\{{n + 3 \atop k + 3}\right\}_{3}

≡ 6 (\left\{{n + 4 \atop 3}\right\}_{3} − \left\{{n + 3 \atop 3}\right\}_{3}) (mod 4)

=6 (3^{n+1} − 3^{n}) = 6 × 2 × 3^{n} = 4 × 3^{n+1} ≡ 0 (mod 4).

Therefore we have ω(A_{3,4}) = 1 and ω(A_{3,2}) = 1.

Finally if r ≥ 4, let r = 4 + h, for some h ≥ 0, then

F_{n+1,r} − F_{n,r} = ∑_{k=0}^{n+1}(k + r)!\left\{{n + 1 + r \atop k + r}\right\}_{r} − ∑_{k=0}^{n}(k + r)!\left\{{n + r \atop k + r}\right\}_{r}.

Since 4 | (k+r)!, for all k ≥ 0, we can write F_{n+1,r}−F_{n,r} ≡ 0 ( mod 4). Therefore ω(A_{r,4}) = 1 and ω(A_{r,2}) = 1.

Theorem 8. If 3 ≤ m ≤ 6, after the (m − 1)th term, the sequence A_{r,2^{m}} has a period with length ω(A_{r,2^{m}}) = 2.

Proof. The proof of this theorem is similar to the proof of Theorem 4. It is enough to prove the theorem for m = 6; then the result follows for m = 3, 4 and 5. Since n ≥ m − 1, then for m = 6 we have n ≥ 5. For 3 ≤ r ≤ 7 we have

F_{n+2,r} − F_{n,r} = ∑_{k=0}^{n+2}(k + r)!\left\{{n + 2 + r \atop k + r}\right\}_{r} − ∑_{k=0}^{n}(k + r)!\left\{{n + r \atop k + r}\right\}_{r}

≡ ∑_{k=0}^{7−r} ∑_{j=r}^{k+r}(−1)^{k+r−j}\binom{k + r}{j}j^{n+1}(j^{2} − 1) (\frac{(j − 1)!}{(j − r)!})

≡ ∑_{k=0}^{7−r} ∑_{j=r}^{k+r}(−1)^{k+r−j}\binom{k + r}{j}j^{n+1}(j^{2} − 1)(j − 1) (\frac{(j − 2)!}{(j − r)!}) (mod 64).

When j is even, then j^{n+1} = (2c)^{6+h}, for some h ≥ 0, and so 64 | j^{n+1}. For odd j we have gcd(j, 64) = 1 and Euler’s theorem gives j^{32} ≡ 1 (mod 64). Therefore j^{n+1+32} ≡ j^{n+1} (mod 64), and we can write

∑_{k=0}^{7−r} ∑_{j=r}^{k+r}(−1)^{k+r−j}\binom{k + r}{j}j^{n+1}(j^{2} − 1)(j − 1)\frac{(j − 2)!}{(j − r)!}

≡ ∑_{k=0}^{7−r} ∑_{l=⌊r/2⌋}^{⌊(k+r−1)/2⌋}(−1)^{k+r−(2l+1)}\binom{k + r}{2l + 1}(2l + 1)^{n+1}((2l + 1)^{2} − 1) × 2l (\frac{(2l − 1)!}{(2l + 1 − r)!})

≡ 16 ∑_{k=0}^{7−r}(−1)^{k+r−1} ∑_{l=⌊r/2⌋}^{⌊(k+r−1)/2⌋} \binom{k + r}{2l + 1}(2l + 1)^{n+1} (\frac{l(l + 1)}{2}) l (\frac{(2l − 1)!}{(2l + 1 − r)!}) (mod 64).

By computation we see that the recent summation is divisible by 4, for 2 ≤ n ≤ 33. So the proof for 3 ≤ r ≤ 7 is completed.

If r ≥ 8, since 64 | 8!, then 64 | (k + r)!, and

F_{n+2,r} − F_{n,r} = ∑_{k=0}^{n+2}(k + r)!\left\{{n + 2 + r \atop k + r}\right\}_{r} − ∑_{k=0}^{n}(k + r)!\left\{{n + r \atop k + r}\right\}_{r} ≡ 0 (mod 64),

so ω(A_{r,2^{6}}) = 2, for r ≥ 8, and the proof is completed.

Theorem 9. If m ≥ 7, after the (m − 1)th term, the sequence A_{r,2^{m}} has a period with length ω(A_{r,2^{m}}) = 2^{m−6}.

Proof. The proof of this theorem is similar to the proof of Theorem 6. In the case of n ≥ 2^{m} − r − 1 and r ≥ 8 we have

F_{n+2^{m−6},r} − F_{n,r} = ∑_{k=0}^{n+2^{m−6}}(k + r)!\left\{{n + 2^{m−6} + r \atop k + r}\right\}_{r} − ∑_{k=0}^{n}(k + r)!\left\{{n + r \atop k + r}\right\}_{r}

≡ ∑_{k=0}^{2^{m}−r−1}(k + r)! (\left\{{n + 2^{m−6} + r \atop k + r}\right\}_{r} − \left\{{n + r \atop k + r}\right\}_{r})

≡ ∑_{k=0}^{2^{m}−r−1} ∑_{j=r}^{k+r}(−1)^{k+r−j}\binom{k + r}{j}j^{n+1}(j^{2^{m−6}} − 1) (\frac{(j − 1)!}{(j − r)!}) (mod 2^{m}).

In the case of 2^{m} > r > 2^{m} − m, since m ≥ 7 this implies that r > 2^{m} − m ≥ 2^{m−1}, so

2^{m} | (2^{m−1})! | (k + r)!, for each k ≥ 0.

Therefore both summations in the above first equation are zero modulo 2^{m} and in this case ω(A_{r,2^{m}}) = 2^{m−6}. When r ≤ 2^{m} − m, if j is even then j^{n+1} = (2c)^{2^{m}−r+h}, for some h ≥ 0. So 2^{m} | j^{n+1}. For odd j we have (j, 2^{m−5}) = 1, and 2^{m−5} | j^{2^{m−6}} − 1 by Euler’s theorem. Since r ≥ 8 we can write \frac{(j−1)!}{(j−r)!} = (\frac{(j−8)!}{(j−r)!}) ∏_{i=1}^{7}(j − i). Therefore 32 | \frac{(j−1)!}{(j−r)!} and

2^{m} | (j^{2^{m−6}} − 1) (\frac{(j−1)!}{(j−r)!}).

In the case of m − 1 ≤ n < 2^{m} − r − 1 and r ≥ 8 we have

F_{n+2^{m−6},r} − F_{n,r} = ∑_{k=0}^{n+2^{m−6}}(k + r)!\left\{{n + 2^{m−6} + r \atop k + r}\right\}_{r} − ∑_{k=0}^{n}(k + r)!\left\{{n + r \atop k + r}\right\}_{r}

≡ ∑_{k=0}^{2^{m}−r−1}(k + r)! (\left\{{n + 2^{m−6} + r \atop k + r}\right\}_{r} − \left\{{n + r \atop k + r}\right\}_{r})

− ∑_{k=n+2^{m−6}+1}^{2^{m}−r−1}(k + r)!\left\{{n + 2^{m−6} + r \atop k + r}\right\} + ∑_{k=n+1}^{2^{m}−r−1}(k + r)!\left\{{n + r \atop k + r}\right\} (mod 2^{m})

= ∑_{k=0}^{2^{m}−r−1}(k + r)! (\left\{{n + 2^{m−6} + r \atop k + r}\right\}_{r} − \left\{{n + r \atop k + r}\right\}_{r}) + 0,

and the proof proceeds as in the previous case. In the case of 3 ≤ r ≤ 7 one can deduce similarly to the proof of Theorem 6 that

F_{n+2^{m−6},r} − F_{n,r} ≡ ∑_{k=0}^{2^{m}−r−1} ∑_{j=r}^{k+r}(−1)^{k+r−j}\binom{k + r}{j}j^{n+1}(j^{2^{m−6}} − 1) (\frac{(j − 1)!}{(j − r)!}) (mod 2^{m}).

Exactly the same as Theorem 6, the terms with even j vanish and only the terms with odd j remain. So we have

F_{n+2^{m−6},r} − F_{n,r} ≡ ∑_{k=0}^{2^{m}−r−1} ∑_{l=⌊r/2⌋}^{⌊(k+r−1)/2⌋}(−1)^{k+r−(2l+1)}\binom{k + r}{2l + 1}(2l + 1)^{n+1}((2l + 1)^{2^{m−6}} − 1)

× (\frac{((2l + 1) − 1)!}{((2l + 1) − r)!})

≡ 2^{m−5} ∑_{k=0}^{2^{m}−r−1}(−1)^{k+r−1} ∑_{l=⌊r/2⌋}^{⌊(k+r−1)/2⌋} \binom{k + r}{2l + 1}(2l + 1)^{n+1}

× ( ∑_{i=1}^{2^{m−6}} l^{i}2^{i−1} (\frac{(2^{m−6} − 1)!}{i!(2^{m−6} − i)!})) (\frac{(2l)!}{(2l − r + 1)!}) (mod 2^{m}).

Since gcd(2l + 1, 16) = 1, Euler’s theorem shows that (2l + 1)^{n+1+8} ≡ (2l + 1)^{n+1} (mod 16). If m ≥ 10, we have

F_{n+2^{m−6},r} − F_{n,r} ≡ 2^{m−4} ∑_{k=0}^{2^{m}−r−1}(−1)^{k+r−1} ∑_{l=⌊r/2⌋}^{⌊(k+r−1)/2⌋} \binom{k + r}{2l + 1}(2l + 1)^{n+1} (\frac{l(l + 1)}{2})

× (−2l^{2} − 2l + 1) (\frac{(2l)!}{(2l − r + 1)!}) (mod 2^{m}).

Therefore it is sufficient to compute the above summation (without factor 2^{m−4}) for 3 ≤ r ≤ 7 and 9 ≤ n ≤ 16 to show that it is divisible by 16.

For 7 ≤ m ≤ 9 we evaluate the sum

∑_{k=0}^{2^{m}−r−1}(−1)^{k+r−1} ∑_{l=⌊r/2⌋}^{⌊(k+r−1)/2⌋} \binom{k + r}{2l + 1}(2l + 1)^{n+1} ∑_{i=1}^{2^{m−6}} l^{i}2^{i−1} \frac{(2^{m−6} − 1)!}{i!(2^{m−6} − i)!} (\frac{(2l)!}{(2l − r + 1)!})

for m−1 ≤ n ≤ m+6 to show that it is divisible by 32. Then it follows that ω(A_{r,2^{m}}) = 2^{m−6}, for all m ≥ 7.

5 The conclusion

We now state the final theorem, which shows how to compute ω(A_{r,s}) for any s ∈ ℕ.

Theorem 10. Let s ∈ ℕ and s > 1 with the prime factorization s = 2^{m}p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{k}^{m_{k}} and let D = {p_{i}^{m_{i}} | p_{i}^{m_{i}} > r, 1 ≤ i ≤ k}. Define E = {m_{i} − 1 | p_{i}^{m_{i}} ∈ D}, F = {φ(p_{i}^{m_{i}}) | p_{i}^{m_{i}} ∈ D} and a = max(E ∪ {m − 1}) and let b be the least common multiple (lcm) of the elements of F. Then

ω(A_{r,s}) = \begin{cases}b, & if 0 ≤ m ≤ 2 or 2^{m} ≤ r; \\ lcm(2, b), & if 3 ≤ m ≤ 6 and 2^{m} > r ; \\ lcm(2^{m−6}, b), & if m ≥ 7 and 2^{m} > r, \end{cases}  (16)

and periodicity of the sequence A_{r,s} is seen after the a-th term.

Proof. Let l be the right hand side of (16). For each d ∈ D ∪ {2^{m}}, ω(A_{r,d}) | l and for each p_{j}^{m_{j}} ∉ D such that 1 ≤ j ≤ k, we have 1 = ω(A_{r,p_{j}^{m_{j}}}) | l, so

F_{n+l,r} ≡ F_{n,r} (mod 2^{m})
F_{n+l,r} ≡ F_{n,r} (mod p_{i}^{m_{i}}), for i = 1, 2, …, k.

Since gcd(2^{m}, p_{1}^{m_{1}}, p_{2}^{m_{2}}, …, p_{k}^{m_{k}}) = 1, the multiplication of all above congruence relations gives the required result.

6 Acknowledgments

The authors would like to thank the anonymous referee for his/her valuable comments and guides.

A Proof of Lemma 5

After simplifying the lemma’s relation we have

\frac{2^{i−5}\binom{2^{m−6}−1}{i}}{2^{m−6} − i} = \frac{2^{i−5}(2^{m−6} − 1)(2^{m−6} − 2) ⋯ (2^{m−6} − i + 1)}{i!}.  (17)

It is sufficient to show that the right hand side of (17) is integer. We know that \binom{2^{m−6}}{i} ∈ ℕ, i.e.,

i! | 2^{m−6}(2^{m−6} − 1) ⋯ (2^{m−6} − i + 1).

If O_{i} denotes the product of the odd factors of i!, since (O_{i}, 2^{m−6}) = 1, then O_{i} | (2^{m−6} − 1) ⋯ (2^{m−6} − i + 1). So in (17) we only need to prove that

ν_{2}(2^{i−5}(2^{m−6} − 1)(2^{m−6} − 2) ⋯ (2^{m−6} − i + 1)) ≥ ν_{2}(i!),

where by ν_{2}(x) we mean that 2^{ν_{2}(x)} | x, but 2^{ν_{2}(x)+1} ∤ x. Let A = ν_{2}((2^{m−6} − 1)(2^{m−6} − 2) ⋯ (2^{m−6} − i + 1)) and B = ν_{2}(i!). Let e be the unique integer such that 2^{e} ≤ i < 2^{e+1}. So

A = ∑_{k=1}^{e}⌊\frac{i − 1}{2^{k}}⌋, B = ∑_{k=1}^{e}⌊\frac{i}{2^{k}} ⌋.  (18)

If we show that

B − A ≤ e  (19)

then the lemma is concluded if it is proved that

i + A ≥ B + 5.  (20)

It can easily be shown that B = ν_{2}(i!) and A = ν_{2}((i − 1)!), so B − A = ν_{2}(i). Since 2^{e} ≤ i < 2^{e+1}, therefore ν_{2}(i) ≤ e and (19) follows. For e = 2, integer possibilities for inequality (20) are as follows:

\begin{matrix}i & A & B \\ 5 & 3 & 3 \\ 6 & 3 & 4 \\ 7 & 4 & 4 \end{matrix}

For e ≥ 3 one can deduce by simple induction that

2^{e} ≥ e + 5,

so i ≥ 2^{e} ≥ e + 5. Add B − e to these inequalities and use (19) demonstrates (20) for i ≥ 8.

References

[1] A. Z. Broder, The r-Stirling numbers, Discrete Math. 49 (1984), 241–259.

[2] A. Cayley, On the analytical forms called trees, Amer. J. Math. 4 (1881), 266–268.

[3] C. Chuan-Chong and K. Khee-Meng, Principles and Techniques in Combinatorics, World Scientific, 1992.

[4] I. Mező, Periodicity of the last digits of some combinatorial sequences, J. Integer Sequences 17 (2014), Article 14.1.1.

[5] I. Mező and J. L. Ramírez, Some identities of the r-Whitney numbers, Aequationes Math. 90 (2016), 393–406.

[6] B. Poonen, Periodicity of a combinatorial sequence, Fibonacci Quart. 26 (1988), 70–76.

2010 Mathematics Subject Classification: Primary 11B50; Secondary 11B75, 05A10, 11B73, 11Y55. Keywords: residue modulo prime power factors, r-Fubini number, r-Stirling number of the second kind, periodic sequence.

(Concerned with sequences \underline{A000670}, \underline{A008277}, \underline{A143494}, \underline{A143495}, \underline{A143496}, \underline{A232472}, \underline{A232473}, and \underline{A232474}.)

Received March 18 2017; revised version received April 16 2017; April 1 2018; April 12 2018; April 21 2018. Published in Journal of Integer Sequences, May 8 2018.

Return to Journal of Integer Sequences home page.