Realizability of Some Combinatorial Sequences

Geng-Rui Zhang School of Mathematical Sciences Peking University Beijing 10871 People’s Republic of China

                grzhang@stu.pku.edu.cn

Abstract

A sequence a = (a_{n})_{n=1}^{∞} of non-negative integers is called realizable if there is a self-map T : X → X on a set X such that a_{n} is equal to the number of periodic points of T in X of (not necessarily exact) period n, for all n ≥ 1. The sequence a is called almost realizable if there exists a positive integer m such that (ma_{n})_{n=1}^{∞} is realizable. In this article, we show that certain wide classes of integer sequences are realizable, which contain many famous combinatorial sequences, such as the sequences of Apéry numbers of both kinds, central Delannoy numbers, Franel numbers, Domb numbers, Zagier numbers, and central trinomial coefficients. We also show that the sequences of Catalan numbers, Motzkin numbers, and large and small Schröder numbers are not almost realizable.

1 Introduction

Let ℤ_{≥0} denote the set of non-negative integers and ℤ^{+} the set of positive integers. In this paper, the serial numbers “Axxxxxx” associated with certain sequences in the paper all refer to the corresponding sequence numbers in the On-Line Encyclopedia of Integer Sequences (OEIS) [31]. We consider a property for sequences of non-negative integers which is inspired from dynamical systems.

Definition 1. A sequence a = (a(n))_{n=1}^{∞} of non-negative integers is called realizable if one of the two following equivalent conditions holds.

(1) there is a self-map T : X → X on a set X such that

a(n) = #{x ∈ X : T^{n}(x) = x}

for all n ≥ 1;

(2) (μ ∗ a)(n) is a non-negative integer divisible by n, for all n ≥ 1, where μ is the (classical) Möbius function and the operation ∗ is the Dirichlet convolution of arithmetic functions.

In this case, we also say that the sequence a = (a(n))_{n=1}^{∞} is realized via the map T and T realizes a.

Remark 2. For the equivalence, see [29, p. 398]. In the description (2), the condition

(μ ∗ a)(n) ≥ 0

for all n ≥ 1 is called the sign condition, and the condition

(μ ∗ a)(n) ≡ 0 (mod n)

for all n ≥ 1 is called the Dold condition. In the description (1), by [37] one can equally require X to be an annulus and f a C^{∞} diffeomorphism of X.

Miska and Ward [23] defined the following generalization of realizability:

Definition 3. Let a = (a_{n})_{n=1}^{∞} be a sequence of non-negative integers. If there exists m ∈ ℤ^{+} such that the sequence (ma_{n})_{n=1}^{∞} is realizable, then we say that a is almost realizable, and the minimal such m ∈ ℤ^{+} is denoted by Fail(a). When a is not almost realizable, we set Fail(a) = ∞.

Example 4. We give some examples of sequences which are realizable, almost realizable, or not almost realizable.

(1) The sequence (2^{n} − 1)_{n=1}^{∞} \underline{A000225} is realized via the map T : ℝ/ℤ → ℝ/ℤ, x ↦ 2x mod 1, the times-2 map on the circle ℝ/ℤ.

(2) The sequence (|(−2)^{n} − 1|)_{n=1}^{∞} \underline{A062510} is realized via the map z ↦ z^{−2} on the circle 𝕊^{1} = {z ∈ ℂ : |z| = 1}.

(3) Let d ∈ ℤ^{+}, X = {0, 1, …, d − 1}^{ℤ}, and T : X ∋ (x_{n})_{n} ↦ (x_{n+1})_{n} ∈ X be the shift map on X. Then the sequence (d^{n})_{n=1}^{∞} is realized via T.

(4) Consider a sequence (U_{n})_{n=1}^{∞} given by U_{n+2} = U_{n+1} + U_{n}, n ≥ 1, U_{1} = a, U_{2} = b, where a, b ∈ ℤ_{≥0}. Note that b = 3a = 3 gives the Lucas sequence (L_{n}) (\underline{A000032}) and a = b = 1 gives the Fibonacci sequence (F_{n}) (\underline{A000045}). Puri and Ward [29] have showed that the sequence (U_{n}) is realizable if and only if b = 3a if and only if (U_{n}) is a non-negative integer multiple of the Lucas sequence. In particular, the Fibonacci sequence (F_{n}) is not realizable. Indeed, Moss and Ward [25] proved that (F_{n}) is not almost realizable, but the sequence (F_{n^{2}})_{n=1}^{∞} (\underline{A054783}) is almost realizable with Fail((F_{n^{2}})) = 5.

(5) Write S^{(1)}(n, k) for the (signless) Stirling number of the first kind, and S^{(2)}(n, k) for the Stirling number of the second kind, where n ≥ k ∈ ℤ_{≥0}, see [33, pp. 32, 81]. For k ≥ 1, set S_{k}^{(1)} = (S^{(1)}(n + k − 1, k))_{n=1}^{∞} and S_{k}^{(2)} = (S^{(2)}(n + k − 1, k))_{n=1}^{∞}. Miska and Ward [23] have showed that S_{k}^{(1)} is not almost realizable for every k ≥ 1, and that S_{k}^{(2)} is realizable if and only if k ∈ {1, 2}, while S_{k}^{(2)} is almost realizable with Fail(S_{k}^{(2)}) | (k − 1)! for every k ≥ 1.

(6) Write (E_{n}) for the sequence of Euler numbers \underline{A122045}, given by the exponential generating function

\frac{2}{e^{t} + e^{−t}} = ∑_{n=0}^{∞} E_{n} \frac{t^{n}}{n!}.

Moss [24, Theorem 5.3.2] proved that the sequence ((−1)^{n}E_{2n})_{n=1}^{∞} (\underline{A000364}) is realizable.

(7) Write (B_{n}) for the sequence of Bernoulli numbers, given by the exponential generating function

\frac{t}{e^{t} − 1} = ∑_{n=0}^{∞} B_{n} \frac{t^{n}}{n!},

cf. [32, Exercise 5.55]. For each n ≥ 1, let b_{n} ∈ ℤ^{+} be the denominator of B_{2n} in the fraction in lowest terms (\underline{A002445}) and write |\frac{B_{2n}}{2n} | = \frac{τ_{n}}{η_{n}} with τ_{n}, η_{n} ∈ ℤ^{+}, and gcd(τ_{n}, η_{n}) = 1. Then (b_{n})_{n=1}^{∞}, (τ_{n})_{n=1}^{∞} (\underline{A001067} taking absolute value), and (η_{n})_{n=1}^{∞} (\underline{A006953}) are realizable according to [13, Theorem 2.6] and [24, Theorem 5.5.3, Theorem 5.5.10]. Indeed, the sequence (η_{n})_{n=1}^{∞} can be realized via an endomorphism of a group.

(8) Write (G_{n}) for the sequence of Genocchi numbers \underline{A226158}, given by the exponential generating function

\frac{−2t}{e^{−t} + 1} = ∑_{n=1}^{∞} G_{n} \frac{t^{n}}{n!}.

See [32, Exercise 5.8] for more on these numbers. It is easy to see that G_{2n+1} = 0 and e_{n} := (−1)^{n}G_{2n} = (−1)^{n}2(1 − 4^{n})B_{2n} is a positive odd integer for n ≥ 1. Since η_{1} = 12 and τ_{1} = 1, by (7) and Fermat’s little theorem, for every prime p ≥ 5, we have

e_{p} = 2(4^{p} − 1) × 2p × \frac{τ_{p}}{η_{p}} ≡ 4p(4 − 1)\frac{1}{12} ≡ 0 ≢ 1 = e_{1} (mod p).

If the sequence (e_{n})_{n=1}^{∞} is almost realizable, then p | Fail((e_{n})) for every prime p ≥ 5, contradicting the fact that ℤ^{+} ∋ Fail((e_{n})) < ∞. Therefore, the sequence (e_{n})_{n=1}^{∞} is not almost realizable.

(9) Consider a multiplicative arithmetic function f whose values are non-negative integers. Then μ∗f is also multiplicative. Using multiplicativity, we see that (f(n))_{n=1}^{∞} is realizable if and only if

0 ≤ f(p^{m}) − f(p^{m−1}) = (μ ∗ f)(p^{m}) ≡ 0 (mod p^{m})

for every prime p and m ∈ ℤ^{+}. For example, consider the divisor function σ_{k}(n) = ∑_{d|n} d^{k}, n ∈ ℤ^{+}, for k ∈ ℤ^{+}. As σ_{k} is multiplicative, from the above observation it is clear that (σ_{k}(n))_{n=1}^{∞} is realizable.

(10) Let (Bell(n))_{n=0}^{∞} be the sequence of Bell numbers \underline{A000110}, which was introduced by Bell [6]. By the Touchard congruence [36], for every prime p, we have

Bell(p) − Bell(1) ≡ Bell(0) = 1 (mod p).

As in (8), we see that the sequence (Bell(n))_{n=1}^{∞} is not almost realizable. For more information on Bell numbers, see [6, 5, 3] and the references therein.

(11) Let d_{n} be the number of derangements \underline{A000166} of the set \{1, …, n\} for n ≥ 1. It is well-known that d_{n} = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} . Then, for every prime number p, we have

d_{p} − d_{1} = p! ∑_{k=0}^{p−1} \frac{(−1)^{k}}{k!} + (−1)^{p} − 0 ≡ (−1)^{p} (mod p).

As in (8), we see that the sequence (d_{n})_{n=1}^{∞} is not almost realizable.

In this article, we consider the realizability of some combinatorial sequences related to binomial coefficients, which are defined below.

Definition 5. For r ∈ ℤ^{+} and n, s ∈ ℤ_{≥0}, define

A(n, r, s) = ∑_{k=0}^{n} \binom{n}{k}^{r}\binom{n + k}{k}^{s}.

Remark 6. Definition 5 includes many well-known sequences in combinatorics. For example, (A(n))_{n=0}^{∞} := (A(n, 2, 2))_{n=0}^{∞} is the sequence of Apéry numbers (of the first kind) \underline{A005259}, and (β(n))_{n=0}^{∞} := (A(n, 2, 1))_{n=0}^{∞} is the sequence of Apéry numbers of the second kind \underline{A005258}. The Apéry numbers of both kinds were introduced by Apéry [2] to prove the irrationality of ζ(3). For more information on Apéry numbers, see [7, 39, 30] and the references therein. The sequence of central Delannoy numbers \underline{A001850} is (D(n))_{n=0}^{∞} := (A(n, 1, 1))_{n=0}^{∞}, cf. [32, Example 6.3.8]. The number D(n) equals the number of paths from the southwest corner (0, 0) of a square grid to the northeast corner (n, n), using only single steps north, northeast, or east. See [4, 35] to learn more about the central Delannoy numbers. Usually, the sequence (f^{(3)}(n)) \underline{A000172} is called the sequence of Franel numbers, which was first introduced by Franel [14]. Generally, for r ∈ ℤ^{+}, we call (f^{(r)}(n))_{n=0}^{∞} := (A(n, r, 0))_{n=0}^{∞} the sequence of Franel numbers of order r. Note that (f^{(1)}(n)) = (2^{n}) has been studied in (3) of Example 4, and that (f^{(2)}(n)) is the sequence of central binomial coefficients \underline{A000984}.

Definition 7. For r ∈ ℤ^{+} and n, s, t ∈ ℤ_{≥0}, define

D(n, r, s, t) = ∑_{k=0}^{n} \binom{n}{k}^{r}\binom{2k}{k}^{s}\binom{2(n − k)}{n − k}^{t}.

Remark 8. The sequence of Domb numbers \underline{A002895} is (Domb(n))_{n=0}^{∞} := (D(n, 2, 1, 1))_{n=0}^{∞}, which was introduced by Domb [11]. For more information on Domb numbers, we refer the reader to [11, 9, 21] and the references therein. We call (Z(n))_{n=0}^{∞} := (D(n, 1, 1, 1))_{n=0}^{∞} the sequence of Zagier numbers (\underline{A081085}), which corresponds to Zagier [40, E. in Table 2].

Definition 9. The sequence (P (n))_{n=0}^{∞} of Catalan-Larcombe-French numbers \underline{A053175} is given by the formula

P (n) = 2^{n} ∑_{k=0}^{n} \binom{n}{2k}\binom{2k}{k}^{2}4^{n−2k}, n ≥ 0.

Remark 10. Catalan [8] showed that (P (n)) has the following recurrence relation:

(n + 1)^{2}P (n + 1) = 8(3n^{2} + 3n + 1)P (n) − 128n^{2}P (n − 1), n ≥ 1.

The number P (n) is the “other” Catalan number in the sense of Larcombe-French [17]. Larcombe and French [17] showed that P (n) can be given by elliptic integrals. We will show that (P (n))_{n=1}^{∞} is realizable (Remark 16), while the sequence (C(n))_{n=1}^{∞} of (true) Catalan numbers is not almost realizable ((1) of Theorem 21).

Definition 11. For r ∈ ℤ^{+} and n, s, t, u ∈ ℤ_{≥0}, define

T (n, r, s, t, u) = ∑_{k=0}^{n} \binom{n}{2k}^{r}\binom{n + k}{k}^{s}\binom{2k}{k}^{t}\binom{2(n − k)}{n − k}^{u}.

Remark 12. For n ≥ 1, the central trinomial coefficient T (n) is defined to be the coefficient of x^{n} in (x^{2} + x + 1)^{n} (\underline{A002426}). Clearly, T (n) = T (n, 1, 0, 1, 0).

The sequences given in Definitions 5, 7, 9, and 11 are all realizable. In fact, the results can be generalized further, see Remarks 33 and 34.

Theorem 13. For every s ∈ ℤ_{≥0} and r ∈ ℤ^{+}, the sequence (A(n, r, s))_{n=1}^{∞} is realizable.

Remark 14. In particular, the sequence of Apéry numbers (of the first kind), the sequence of Apéry numbers of the second kind, the sequence of central Delannoy numbers, and the sequence of Franel numbers of order r ∈ ℤ^{+} are all realizable.

Theorem 15. For every s, t ∈ ℤ_{≥0}, and r ∈ ℤ^{+}, the sequence (D(n, r, s, t))_{n=1}^{∞} is realizable.

Remark 16. In particular, the sequence of Domb numbers and the sequence of Zagier numbers are both realizable. Moreover, the sequence of Catalan-Larcombe-French numbers is also realizable. Larcombe and French [18, Theorem 3] proved that P (n) = 2^{n}Z(n) for all n ≥ 0. As in (3) of Example 4, the sequence (2^{n})_{n=1}^{∞} is realized via the shift map T : X = {0, 1}^{ℤ} → X. By Theorem 15, there exists a map F : Y → Y on a set Y such that

Z(n) = #{y ∈ Y : F^{n}(y) = y}, n ≥ 1.

Clearly, the sequence (P (n))_{n=1}^{∞} = (2^{n}Z(n))_{n=1}^{∞} is realized via the map

T × F : X × Y → X × Y, (x, y) ↦ (T (x), F (y)).

Remark 17. By Theorem 13, for all m, r ∈ ℤ^{+}, s ∈ ℤ_{≥0}, and every prime p, we have

A(p^{m}, r, s) ≡ A(p^{m−1}, r, s) (mod p^{m}).

In fact, in the proof of Theorem 13, we will show that for every m, n, r ∈ ℤ^{+}, s ∈ ℤ_{≥0}, and every prime p, we have

A(np^{m}, r, s) ≡ A(np^{m−1}, r, s) (mod p^{m}).  (1)

(The congruence (1) is a result of Theorem 13 and Lemma 30.) For certain values of r and s, results stronger than (1) have been proved. For example, Straub [34, Theorem 1.1] asserted that for (V (n)) in the 15 known sporadic Apéry-like sequences [34, pp. 1–2], arbitrary prime p ≥ 3, and m, n ∈ ℤ^{+}, we have

V (np^{m}) ≡ V (np^{m−1}) (mod p^{2m}).  (2)

The 15 known sporadic Apéry-like sequences include (f^{(3)}(n))_{n}, (f^{(4)}(n))_{n} (the sequence \underline{A005260}), (A(n))_{n}, (β(n))_{n}, (Z(n))_{n}, (Domb(n))_{n}, (D(n, 2, 1, 0))_{n} (the sequence \underline{A002893}), and some other sequences, see [20]. Similarly, in the proof of Theorem 15, we will show that for all m, n, r ∈ ℤ^{+}, s, t ∈ ℤ_{≥0}, and every prime p, we have

D(np^{m}, r, s, t) ≡ D(np^{m−1}, r, s, t) (mod p^{m}).  (3)

(The congruence (3) is a result of Theorem 15 and Lemma 30.) Also, for restricted values of s, t, and p, results stronger than (3) have been proved. For example, Osburn and Sahu [27, Theorem 1.1] showed that for all m, n, s, t ∈ ℤ^{+}, r ∈ {2, 3, 4, …}, and every prime p ≥ 5, we have

D(np^{m}, r, s, t) ≡ D(np^{m−1}, r, s, t) (mod p^{3m}).  (4)

Theorem 18. For every r ∈ ℤ^{+} and s, t, u ∈ ℤ_{≥0}, the sequence (T (n, r, s, t, u))_{n=1}^{∞} is realizable.

Next we consider some other famous sequences involving binomial coefficients as well, but they are not almost realizable.

Definition 19. (1) The sequence of Catalan numbers \underline{A000108} (C(n))_{n=0}^{∞} is given by the

formula

C(n) := \frac{1}{n + 1}\binom{2n}{n} = \binom{2n}{n} − \binom{2n}{n + 1}, n ≥ 0;

(2) The sequence of Motzkin numbers \underline{A001006} (M(n))_{n=0}^{∞} is given by the formula

M(n) := ∑_{k=0}^{n} \binom{n}{2k}C(k), n ≥ 0;

(3) The sequence of large Schröder numbers \underline{A006318} is given by the formula

S(n) := ∑_{k=0}^{n} \binom{n + k}{2k}C(k), n ≥ 0.

Remark 20. The Motzkin numbers are first appeared in Motzkin [26] in a circle chording setting. The large Schröder number S(n) describes the number of paths from the southwest corner (0, 0) of a square grid to the northeast corner (n, n), using only single steps north, northeast, or east, that do not rise above the SW-NE diagonal.

Theorem 21. The following sequences are not almost realizable.

(1) (C(n))_{n=1}^{∞};

(2) (M(n))_{n=1}^{∞};

(3) (S(n))_{n=1}^{∞}.

Remark 22. The sequence of little Schröder numbers \underline{A001003} (s(n))_{n=1}^{∞} is given by the formula

s(n) := ∑_{k=1}^{n} N(n, k)2^{k−1}, n ≥ 1,

cf. [32, p. 178]. Here

N(n, k) = \frac{1}{n}\binom{n}{k}\binom{n}{k − 1} ∈ ℤ^{+}

is the Narayana number \underline{A001263}, cf. [32, Exercise 6.36]. It is well-known that S(n) = 2s(n) for every n ≥ 1, so from (3) of Theorem 21, we deduce that the sequence (s(n))_{n=1}^{∞} of little Schröder numbers is not almost realizable as well.

It is interesting to consider the realizability of combinatorial sequences of different types, which may not involve binomial coefficients. Motivated by computations, we make the following conjecture.

Conjecture 23. For n ≥ 1, let p(n) be the number of partitions of n, i.e., ways of writing n as an (unordered) sum of positive integers (\underline{A000041}). Then the sequence

(p(n))_{n=1}^{∞} = (1, 2, 3, 5, 7, 11, 15, …)

of partition numbers is not almost realizable.

Remark 24. However, we show that the sequence (p(n))_{n=1}^{∞} satisfies the sign condition. Clearly, the sequence (p(n))_{n=1}^{∞} is increasing. By Remark 29, it suffices to check that

p(2n) ≥ np(n), n ≥ 1.  (5)

By [22, Corollary 3.1] and [19, Theorem 15.7], for all integers n ≥ 3, we have

\frac{1}{14}e^{2\sqrt{n}} < p(n) < \frac{π}{\sqrt{6(n − 1)}}e^{π\sqrt{\frac{2}{3} n}}.

Thus, for every integer n ≥ 523, we have

\frac{p(2n)}{p(n)} > \frac{\sqrt{6(n − 1)}}{14π}e^{(2\sqrt{2}−π\sqrt{\frac{2}{3}} )\sqrt{n}} > n.

For integers 1 ≤ n ≤ 522, the equation (5) has been checked by direct computation via a computer. Hence the sequence (p(n))_{n=1}^{∞} satisfies the sign condition.

In §2, we consider several useful lemmas. In §3, we complete the proofs of Theorems 13, 15, 18, and 21, and give some remarks.

2 Auxiliary lemmas

First, we need the following well-known theorem of Kummer [16].

Lemma 25 (Kummer’s theorem). Given a prime number p and integers n ≥ m ≥ 0, the value of ν_{p} (\binom{n}{m}) is equal to the number of carries when m is added to n − m in base p. Here ν_{p} denotes the standard p-adic valuation on ℚ.

The following lemma is [15, Corollary of p. 490] by Helou and Terjanian.

Lemma 26. Let n ≥ m ≥ 0 be integers.

(1) For every prime p ≥ 5, we have

\binom{np}{mp} ≡ \binom{n}{m} (mod p^{3+max(ν_{p}(m),ν_{p}(n−m))+ν_{p}(\binom{n}{m})}).

(2) For p = 3, we have

\binom{3n}{3m} ≡ \binom{n}{m} (mod 3^{2+max(ν_{3}(m),ν_{3}(n−m))+ν_{3}(\binom{n}{m})}).

(3) For p = 2, we have

\binom{2n}{2m} ≡ \binom{n}{m} (mod 2^{1+max(ν_{2}(m),ν_{2}(n−m))+ν_{2}(\binom{n}{m})}).

Here, for two integers A, B, and a prime p, the expression A ≡ B (mod p^{∞}) means that A ≡ B (mod p^{N}) for all N ∈ ℤ^{+}, or equivalently, A = B.

Note that in Lemma 26, the conclusion trivially holds when m = 0.

Lemma 27. Let n ∈ ℤ_{≥0} and p be a prime divisor of n. Set m = ν_{p}(n) ∈ ℤ^{+} ∪ {∞}. Then

\binom{n}{λp} ≡ \binom{n/p}{λ} (mod p^{max(m,ν_{p}(n−λp))}),

for every non-negative integer λ.

Proof. When n = 0, we have \binom{n}{λp} = 0 = \binom{n/p}{λ}. Hence the conclusion is clear. We may assume that n > 0. Write n = lp^{m}. Observe that gcd(l, m) = 1. If λ ≥ lp^{m−1} or λ = 0, then \binom{n}{λp} = \binom{n/p}{λ} ∈ \{0, 1\}, so the conclusion holds. Now assume that 0 < λ < lp^{m−1}. As 1 + ν_{p}((n/p) − λ) = ν_{p}(n − λp), by Lemma 26, it suffices to show that

1 + max (ν_{p}(λ), ν_{p}(lp^{m−1} − λ)) + ν_{p} (\binom{lp^{m−1}}{λ}) ≥ m.

Write λ = p^{t}q, where t = ν_{p}(λ) ∈ ℤ_{≥0} and q ∈ ℤ^{+} with p ∤ q. When t ≥ m − 1, we have

1 + max (ν_{p}(λ), ν_{p}(lp^{m−1} − λ)) + ν_{p} (\binom{lp^{m−1}}{λ}) ≥ 1 + ν_{p}(λ) = 1 + t ≥ m.

If t ≤ m − 2, then ν_{p}(n/p) = m − 1 > m − 2 ≥ t = max(ν_{p}(λ), ν_{p}((n/p) − λ)), so by Lemma 25 we see that

ν_{p} (\binom{lp^{m−1}}{λ}) = ν_{p} (\binom{lp^{m−1}}{qp^{t}}) ≥ m − 1 − t.

Thus,

1 + max (ν_{p}(λ), ν_{p}(lp^{m−1} − λ)) + ν_{p} (\binom{lp^{m−1}}{λ}) ≥ 1 + t + m − 1 − t = m.

The following lemma gives a sufficient condition for the sign condition.

Lemma 28. Let (b(n))_{n=1}^{∞} be a sequence of non-negative real numbers. Assume that there is a constant C ≥ 1.221 such that b(n + 1) ≥ Cb(n) for every n ≥ 1. Then (μ ∗ b)(n) ≥ 0 for every n ≥ 1.

Proof. Set f = μ ∗ b. By assumption we have b(n + k) ≥ C^{k}b(n) for every n ≥ 1 and k ≥ 0. In particular, (b(n))_{n=1}^{∞} is non-decreasing and non-negative. Trivially, f(1) = b(1) ≥ 0. For every prime number p and k ∈ ℤ^{+}, since p^{k} > p^{k−1}, we have

f(p^{k}) = b(p^{k}) − b(p^{k−1}) ≥ 0.

For every pair of distinct prime numbers p_{1} ≠ p_{2} and k_{1}, k_{2} ∈ ℤ^{+}, we have

f (p_{1}^{k_{1}}p_{2}^{k_{2}}) = b (p_{1}^{k_{1}}p_{2}^{k_{2}}) − b (p_{1}^{k_{1}−1}p_{2}^{k_{2}}) − b (p_{1}^{k_{1}}p_{2}^{k_{2}−1}) + b (p_{1}^{k_{1}−1}p_{2}^{k_{2}−1})
≥ b (p_{1}^{k_{1}}p_{2}^{k_{2}}) − C^{p_{1}^{k_{1}−1}p_{2}^{k_{2}}−p_{1}^{k_{1}}p_{2}^{k_{2}}}b (p_{1}^{k_{1}}p_{2}^{k_{2}}) − C^{p_{1}^{k_{1}}p_{2}^{k_{2}−1}−p_{1}^{k_{1}}p_{2}^{k_{2}}}b (p_{1}^{k_{1}}p_{2}^{k_{2}}) + 0
≥ (1 − C^{3−3×2} − C^{2−3×2}) b (p_{1}^{k_{1}}p_{2}^{k_{2}})
≥ (1 − 1.221^{−3} − 1.221^{−4}) b (p_{1}^{k_{1}}p_{2}^{k_{2}})
≥ 0.

The minimum positive integer with at least three distinct prime divisor is 30 = 2 × 3 × 5, so it suffices to show that f(n) ≥ 0 for n ≥ 30. Assume that n ≥ 30, and set m = ⌊\frac{n}{2}⌋ ≥ 15. Then

f(n) = ∑_{d|n} μ (\frac{n}{d}) b(d) = b(n) + ∑_{d|n,d≠n} μ (\frac{n}{d}) b(d) ≥ b(n) − ∑_{d|n,d≠n} b(d)

≥ b(n) − ∑_{d=1}^{m} b(d) ≥ C^{m}b(m) − ∑_{d=1}^{m} C^{d−m}b(m) ≥ (C^{m} − m)b(m)

≥ (1.221^{m} − m)b(m) ≥ 0,

since m ≥ 15.

Remark 29. The converse of Lemma 28 is false, in general. For example, the trivial sequence (1)_{n=1}^{∞} provides a counterexample. Note that the number 1.221 in the statement can be replaced by the unique positive root x_{0} = 1.220744 ⋯ of the equation x^{4} = x + 1. Puri [28] observed that if (b(n))_{n=1}^{∞} is a non-decreasing sequence of non-negative real numbers with

b(2n) ≥ nb(n),  (6)

for all n ≥ 1, then (μ ∗ b)(n) ≥ 0 for all n ≥ 1, cf. [23, proof of Lemma 8]. Note that Lemma 28 cannot be deduced directly from the observation of Puri since 1.221^{n} < n for n ∈ {2, 3, …, 12}, and vice versa.

We consider the Dold condition now, which has an equivalent statement as follows.

Lemma 30. Let (V (n))_{n=1}^{∞} be a sequence of integers. Then the following conditions are equivalent.

(1) for every n, m ∈ ℤ^{+}, and every prime number p, we have

V (np^{m}) ≡ V (np^{m−1}) (mod p^{m});

(2) (V (n))_{n=1}^{∞} satisfies the Dold condition, i.e., (μ ∗ V)(n) ≡ 0 (mod n), for every n ≥ 1.

Proof. Set g = μ ∗ V. Given an arbitrary integer n ≥ 2, write n = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{l}^{m_{l}}, where p_{1}, …, p_{l} are pairwise distinct primes, and l, m_{1}, …, m_{l} ∈ ℤ^{+}. Set n_{1} = p_{2}^{m_{2}} ⋯ p_{l}^{m_{l}}. Here n_{1} = 1 when l = 1. Then, we have

\begin{aligned}g(n) & = ∑_{d|n} μ(d)V (\frac{n}{d}) = ∑_{d|n_{1}} (μ(d)V (\frac{n}{d}) + μ(dp_{1})V (\frac{n}{dp_{1}} )) \\ & = ∑_{d|n_{1}} μ(d) (V (\frac{n_{1}}{d} p_{1}^{m_{1}}) + μ(p_{1})V (\frac{n_{1}}{d} p_{1}^{m_{1}−1})) \\ & = ∑_{d|n_{1}} μ(d) (V (\frac{n_{1}}{d} p_{1}^{m_{1}}) − V (\frac{n_{1}}{d} p_{1}^{m_{1}−1})) . \end{aligned}  (7)

First assume that for every n, m ∈ ℤ^{+}, and every prime number p, we have

V (np^{m}) ≡ V (np^{m−1}) (mod p^{m}).

We show that the Dold condition holds. The congruence g(1) ≡ 0 (mod 1) trivially holds. For an arbitrary integer n = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{l}^{m_{l}} ≥ 2 as above, we have

g(n) = ∑_{d|n_{1}} μ(d) (V (\frac{n_{1}}{d} p_{1}^{m_{1}}) − V (\frac{n_{1}}{d} p_{1}^{m_{1}−1})) ≡ 0 (mod p_{1}^{m})

by (7). Similarly, we have g(n) ≡ 0 (mod p_{j}^{m_{j}}) for 1 < j ≤ l. Thus, we get g(n) ≡ 0 (mod n), i.e., the Dold condition is verified.

Now assume that for every n ∈ ℤ^{+}, we have g(n) ≡ 0 (mod n). We will show that for every n, m ∈ ℤ^{+}, and every prime number p, we have

V (np^{m}) ≡ V (np^{m−1}) (mod p^{m}).  (8)

Write n = n_{1}p^{s}, where n_{1} ∈ ℤ^{+} and s ∈ ℤ_{≥0} with gcd(n_{1}, p) = 1. Note that the congruence

V (n_{1}p^{m+s}) ≡ V (n_{1}p^{m+s−1}) (mod p^{m+s})

implies the congruence (8), hence it suffices to show that (8) holds in the case gcd(n, p) = 1. We use induction on n ∈ ℤ^{+}. When n = 1, the congruence (8) follows from

V (p^{m}) − V (p^{m−1}) = g(p^{m}) ≡ 0 (mod p^{m}).

Let n be an arbitrary integer at least 2 and assume that (8) hold for all smaller n (with gcd(n, p) = 1). Thus, by (7), the inductive hypothesis, and the Dold condition, we have

0 ≡ g(np^{m}) = ∑_{d|n} μ(d) (V (\frac{n}{d}p^{m}) − V (\frac{n}{d}p^{m−1}))

≡ μ(1) (V (np^{m}) − V (np^{m−1})) + ∑_{d|n,d>1} μ(d) · 0

= V (np^{m}) − V (np^{m−1}) (mod p^{m}).

(Here np^{m}, n, p, m correspond to n, n_{1}, p_{1}, m_{1} in (7), respectively.) Therefore, we have showed that (8) holds for every n, m ∈ ℤ^{+}, and every prime p.

Remark 31. From the proof of Lemma 30, we can require that n and p are coprime in condition (1).

3 Proofs of theorems

Proof of Theorem 13. Fix s ∈ ℤ_{≥0} and r ∈ ℤ^{+}. Write V (n) = A(n, r, s), n ≥ 1, for simplicity of notation. Set g = μ ∗ V. For n = 1, it is clear that g(1) = V (1) = 1 + 2^{s} is divisible by 1. Given arbitrary m, n ∈ ℤ^{+}, and an arbitrary prime number p, we consider the difference V (np^{m}) − V (np^{m−1}) modulo p^{m}. Let 0 ≤ k ≤ np^{m} be an integer. If p ∤ k, then we have

\binom{np^{m}}{k} ≡ 0 (mod p^{m})

by Lemma 25. If p | k, then

\binom{np^{m}}{k} ≡ \binom{np^{m−1}}{k/p} (mod p^{m}), \binom{np^{m} + k}{k} ≡ \binom{np^{m−1} + k/p}{k/p} (mod p^{m})

by Lemma 27, since ν_{p}(np^{m} + k − k) ≥ m. Therefore,

V (np^{m}) − V (np^{m−1}) = ∑_{k=0}^{np^{m}} \binom{np^{m}}{k}^{r}\binom{np^{m} + k}{k}^{s} − ∑_{k=0}^{np^{m−1}} \binom{np^{m−1}}{k}^{r}\binom{np^{m−1} + k}{k}^{s}

≡ 0 + ∑_{λ=0}^{np^{m−1}} \binom{np^{m}}{λp}^{r}\binom{np^{m} + λp}{λp}^{s} − ∑_{k=0}^{np^{m−1}} \binom{np^{m−1}}{k}^{r}\binom{np^{m−1} + k}{k}^{s}

≡ ∑_{λ=0}^{np^{m−1}} \binom{np^{m−1}}{λ}^{r}\binom{np^{m−1} + λ}{λ}^{s} − ∑_{k=0}^{np^{m−1}} \binom{np^{m−1}}{k}^{r}\binom{np^{m−1} + k}{k}^{s}

= 0 (mod p^{m}).

We get that

V (np^{m}) − V (np^{m−1}) ≡ 0 (mod p^{m}).

By Lemma 30, we see that (V (n))_{n=1}^{∞} satisfies the Dold condition.

It suffices to show that g(n) ≥ 0 for all n ∈ ℤ^{+}. For every n ≥ 1, we have

V (n + 1) = ∑_{k=0}^{n+1} \binom{n + 1}{k}^{r}\binom{n + 1 + k}{k}^{s} = 1 + ∑_{k=1}^{n+1} \binom{n + 1}{k}^{r}\binom{n + 1 + k}{k}^{s}

= 1 + ∑_{k=1}^{n+1} (\binom{n}{k} + \binom{n}{k − 1})^{r} (\binom{n + k}{k} + \binom{n + k}{k − 1})^{s}

≥ 1 + ∑_{k=1}^{n+1} (\binom{n}{k}^{r}\binom{n + k}{k}^{s} + \binom{n}{k − 1}^{r}\binom{n + k}{k − 1}^{s})

≥ 1 + ∑_{k=1}^{n+1} (\binom{n}{k}^{r}\binom{n + k}{k}^{s} + \binom{n}{k − 1}^{r}\binom{n + k − 1}{k − 1}^{s})

= 2 ∑_{k=0}^{n} \binom{n}{k}^{r}\binom{n + k}{k}^{s} = 2V (n).

As 2 > 1.221, the Dold condition g(n) ≥ 0 for all n ∈ ℤ^{+} follows from Lemma 28. Therefore, the sequence (V (n))_{n=1}^{∞} is realizable.

Remark 32. In the proof of Theorem 13, we have showed that A(n + 1, r, s) ≥ 2A(n, r, s), for all n, s ≥ 0, and r ≥ 1. For some specified values of r and s, some stronger results are known. Recall that A(n) = A(n, 2, 2), β(n) = A(n, 2, 1), D(n) = A(n, 1, 1), and f^{(r)}(n) = A(n, r, 0). Xia and Yao [38, Corollary 5] proved that the sequence (A(n))_{n=0}^{∞} is strictly log-convex, i.e.,

\frac{A(n + 1)}{A(n)} > \frac{A(n)}{A(n − 1)}, n ≥ 1.

Hence, for all n ≥ 1, we have

\frac{A(n + 1)}{A(n)} ≥ \frac{A(2)}{A(1)} = \frac{73}{5} > 2.

Xia and Yao also showed that the sequence (D(n))_{n=0}^{∞} is strictly log-convex [38, Corollary 6], hence we have

\frac{D(n + 1)}{D(n)} ≥ \frac{D(2)}{D(1)} = \frac{13}{3} > 2, n ≥ 1.

The result [10, Theorem 5.2] of Chen and Xia implies that the sequence (β(n))_{n=0}^{∞} is strictly log-convex, hence we get

\frac{β(n + 1)}{β(n)} ≥ \frac{β(2)}{β(1)} = \frac{19}{3} > 2, n ≥ 1.

The result [12, Corollary 4.3] of Došlić implies that for r ∈ {3, 4}, the sequence (f^{(r)}(n))_{n=0}^{∞} is log-convex, i.e.,

f^{(r)}(n + 1)f^{(r)}(n − 1) ≥ f^{(r)}(n)^{2}, n ≥ 1.

Proof of Theorem 15. Fix s, t ∈ ℤ_{≥0}, and r ∈ ℤ^{+}. Write W (n) = D(n, r, s, t), n ≥ 1, for simplicity of notation. Set g = μ ∗ W. For n = 1, it is clear that g(1) = W (1) = 2^{t} + 2^{s} is divisible by 1. Given m, n ∈ ℤ^{+}, and an arbitrary prime number p, we consider the difference A := W (np^{m}) − W (np^{m−1}) modulo p^{m}. Let 0 ≤ k ≤ np^{m} be an integer. If p ∤ k, then we have

\binom{np^{m}}{k} ≡ 0 (mod p^{m})  (9)

by Lemma 25. Now assume that p | k and write k = lp^{u}, where (l, u) = (0, m) when k = 0, and l, u ∈ ℤ^{+} with gcd(l, p) = 1 when k > 0. We claim that

\binom{np^{m}}{k}^{r}\binom{2k}{k}^{s}\binom{2(np^{m} − k)}{np^{m} − k}^{t} ≡ \binom{np^{m−1}}{lp^{u−1}}^{r}\binom{2lp^{u−1}}{lp^{u−1}}^{s}\binom{2(np^{m−1} − lp^{u−1})}{np^{m−1} − lp^{u−1}}^{t} (mod p^{m}). (10)

Note that Lemma 27 implies that

\binom{np^{m}}{k}^{r} ≡ \binom{np^{m−1}}{lp^{u−1}}^{r} (mod p^{m}).

By Lemma 25, we have ν_{p} (\binom{2M}{M}) ≥ δ_{2,p} for all M ∈ ℤ^{+}, where δ_{2,p} is the Kronecker symbol. From Lemma 26, we see that

\binom{2k}{k} ≡ \binom{2lp^{u−1}}{lp^{u−1}} (mod p^{1+u}),  (11)
\binom{2(np^{m} − k)}{np^{m} − k} ≡ \binom{2(np^{m−1} − lp^{u−1})}{np^{m−1} − lp^{u−1}} (mod p^{1+min(u,m)}).  (12)

Thus, the congruence (10) holds if u ≥ m−1. Assume that 1 ≤ u ≤ m−2. By the definition of u, we have 0 < k < np^{m}. From Lemma 25, we get that

v_{p} (\binom{np^{m}}{k}) = v_{p} (\binom{np^{m−1}}{k/p}) ≥ m − u.  (13)

Set N = max(0, m − r(m − u)). To show (10), it suffices to prove the congruences

\binom{2k}{k} ≡ \binom{2lp^{u−1}}{lp^{u−1}} (mod p^{N}) and \binom{2(np^{m} − k)}{np^{m} − k} ≡ \binom{2(np^{m−1} − lp^{u−1})}{np^{m−1} − lp^{u−1}} (mod p^{N}),

(14) which follows from (11) and (12), since r ≥ 1 and 1 ≤ u ≤ m − 2 imply

N = max(0, ru − (r − 1)m) < 1 + u = 1 + min(u, m).

By (9) and (10), the difference A = W (np^{m}) − W (np^{m−1}) satisfies

A = ∑_{k=0}^{np^{m}} \binom{np^{m}}{k}^{r}\binom{2k}{k}^{s}\binom{2(np^{m} − k)}{np^{m} − k}^{t} − ∑_{k=0}^{np^{m−1}} \binom{np^{m−1}}{k}^{r}\binom{2k}{k}^{s}\binom{2(np^{m−1} − k)}{np^{m−1} − k}^{t}

≡ 0 + ∑_{λ=0}^{np^{m−1}} \binom{np^{m}}{λp}^{r}\binom{2λp}{λp}^{s}\binom{2(np^{m} − λp)}{np^{m} − λp}^{t} − ∑_{k=0}^{np^{m−1}} \binom{np^{m−1}}{k}^{r}\binom{2k}{k}^{s}\binom{2(np^{m−1} − k)}{np^{m−1} − k}^{t}

≡ ∑_{λ=0}^{np^{m−1}} \binom{np^{m−1}}{λ}^{r}\binom{2λ}{λ}^{s}\binom{2(np^{m−1} − λ)}{np^{m−1} − λ}^{t} − ∑_{k=0}^{np^{m−1}} \binom{np^{m−1}}{k}^{r}\binom{2k}{k}^{s}\binom{2(np^{m−1} − k)}{np^{m−1} − k}^{t}

= 0 (mod p^{m}).

We get W (np^{m}) ≡ W (np^{m−1}) (mod p^{m}). Hence, the Dold condition for (W (n))_{n=1}^{∞} follows from Lemma 30.

We consider the sign condition. It is clear that the sequence (\binom{2n}{n})_{n=0}^{∞} is strictly increasing by looking the ratios of two adjacent terms. For all n ≥ 1, we have

W (n + 1) = ∑_{k=0}^{n+1} \binom{n + 1}{k}^{r}\binom{2k}{k}^{s}\binom{2(n + 1 − k)}{n + 1 − k}^{t}

= \binom{2(n + 1)}{n + 1}^{t} + ∑_{k=1}^{n+1} (\binom{n}{k} + \binom{n}{k − 1})^{r} \binom{2k}{k}^{s}\binom{2(n + 1 − k)}{n + 1 − k}^{t}

≥ \binom{2(n + 1)}{n + 1}^{t} + ∑_{k=1}^{n+1} (\binom{n}{k}^{r} + \binom{n}{k − 1}^{r}) \binom{2k}{k}^{s}\binom{2(n + 1 − k)}{n + 1 − k}^{t}

≥ \binom{2n}{n}^{t} + ∑_{k=1}^{n} \binom{n}{k}^{r}\binom{2k}{k}^{s}\binom{2(n − k)}{n − k}^{t} + ∑_{k=0}^{n} \binom{n}{k}^{r}\binom{2k}{k}^{s}\binom{2(n − k)}{n − k}^{t}

= 2 ∑_{k=0}^{n} \binom{n}{k}^{r}\binom{2k}{k}^{s}\binom{2(n − k)}{n − k}^{t} = 2W (n).

As 2 > 1.221 and W (n) > 0 for all n ≥ 1, the sign condition for (W (n))_{n=1}^{∞} holds by Lemma 28. Thus, the sequence (W (n))_{n=1}^{∞} is realizable.

Remark 33. For every r ∈ ℤ^{+} and s, t, u ∈ ℤ_{≥0}, set

C(n, r, s, t, u) = ∑_{k=0}^{n} \binom{n}{k}^{r}\binom{n + k}{k}^{s}\binom{2k}{k}^{t}\binom{2(n − k)}{n − k}^{u}, n ≥ 1.

A very similar argument proves that the sequence (C(n, r, s, t, u))_{n=1}^{∞} is realizable, which generalizes both Theorem 13 and Theorem 15.

Proof of Theorem 18. Fix r ∈ ℤ^{+} and s, t, u ∈ ℤ_{≥0}. As in Remark 33, applying Lemma 30, the combination of the proof of Theorem 15 and Lemma 30 with small modification implies the Dold condition for (T (n, r, s, t, u) =: X(n))_{n=1}^{∞}. The only differences are that in many places k should be replaced by 2k, so the formula (13) should have a correction term, i.e.,

(13) should be

v_{p} (\binom{np^{m}}{2k}) = v_{p} (\binom{np^{m−1}}{2k/p}) ≥ m − u − δ_{2,p},

and that N should be max(0, m − r(m − u − δ_{2,p})). Since m − r(m − u − 1) ≤ 1 + u under the conditions r ≥ 1 and 1 ≤ u ≤ m − 2, we see that the proof is still valid.

For the sign condition, we first consider the easier case of central trinomial coefficients, i.e., the case when (r, s, t, u) = (1, 0, 1, 0). We will use the observation of Puri stated as in Remark 29. Fix n ∈ ℤ^{+}. For a polynomial h(x) and k ∈ ℤ_{≥0}, let [x^{k}]h(x) denote the coefficient of x^{k} in h(x). Then

T (2n) = [x^{2n}](x^{2} + x + 1)^{2n} ≥ ([x^{n}](x^{2} + x + 1)^{n})^{2} = T (n)^{2}.

Clearly, the sequence of central trinomial coefficients is increasing. By Remark 29, it suffices to show that T (n) ≥ n, for every n ≥ 1. For n ∈ {1, 2, 3}, T (n) ≥ n trivially holds. When n ≥ 4, we have

T (n) ≥ 1 + \binom{n}{2⌊\frac{n}{2}⌋}\binom{2⌊\frac{n}{2}⌋}{⌊\frac{n}{2}⌋} ≥ 1 + 2 ⌊\frac{n}{2}⌋ ≥ n.

Therefore, the sequence (T (n))_{n=1}^{∞} satisfies the sign condition.

Now we consider the sign condition for the general case. We will prove that

X(n + 1) ≥ \frac{7}{5}X(n), n ≥ 1,  (15)

from which the sign condition follows, applying Lemma 28.

Fix n ∈ ℤ^{+}. When n = 1, we have X(2) = 6^{u} + 3^{s}2^{t+u} ≥ 2 × 2^{u} = 2X(1). When n = 2, we have

X(3) = 20^{u} + 3^{r}4^{s}2^{t}6^{u} ≥ 2 × 6^{u} − δ_{u,0} + 3 × 4^{s}2^{t}6^{u} ≥ 2 × 6^{u} − δ_{u,0} + 1 + 2 × 4^{s}2^{t}6^{u}
≥ 2(6^{u} + 4^{s}2^{t}6^{u}) ≥ 2(6^{u} + 3^{s}2^{t+u}) = 2X(2).

Similarly, it is easy to check that X(4) ≥ 2X(3) and X(5) ≥ 2X(4) hold. Now assume that n ≥ 5. (Here n ≥ 5 ensures that n_{1} − 1 ≥ 1 below.)

For integers m, l ≥ 0, set

f_{m}(l) = \binom{m + l}{l}^{s}\binom{2l}{l}^{t},

which is non-decreasing with respect to both m and l.

We give a lower bound of X(n + 1) − X(n) =: B as follows. As in the proofs of Theorems 13 and 15, from the identity \binom{m+1}{l+1} = \binom{m}{l} + \binom{m}{l+1}, we get \binom{m+1}{l+1}^{v} ≥ \binom{m}{l}^{v} + \binom{m}{l+1}^{v}, where m ≥ l ≥ 0 and v ≥ 1 are integers. Set n_{0} = ⌊\frac{n+1}{2}⌋ ∈ [3, n − 2]. Since the central binomial coefficient \binom{2m}{m} is strictly increasing and \binom{n+1+k}{k} ≥ \binom{n+k}{k}, we have

\begin{aligned}B & = \binom{2(n + 1)}{n + 1}^{u} + ∑_{k=1}^{n_{0}} \binom{n + 1}{2k}^{r}f_{n+1}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u} − X(n) \\ & ≥ \binom{2n}{n}^{u} + ∑_{k=1}^{n_{0}} (\binom{n}{2k}^{r} + \binom{n}{2k − 1}^{r}) f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u} − X(n) \\ & ≥ ∑_{k=1}^{n_{0}} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u}. \end{aligned}  (16)

Using (16), we will give a lower bound of X(n + 1) − 2X(n). Set n_{1} = ⌊\frac{n+3}{4}⌋ = ⌈\frac{n}{4}⌉ ∈ [2, n − 3]. When 1 ≤ k ≤ n_{1}, we have

2k − 1 ≤ 2 ⌈\frac{n}{4}⌉ − 1 ≤ \frac{n + 1}{2}.

When n_{1} + 1 ≤ k ≤ n_{0}, we have

2k − 1 ≥ 2 ⌈\frac{n}{4}⌉ + 1 ≥ \frac{n}{2} + 1.

Set

Δ′ = (\binom{n}{2n_{1} − 1}^{r}f_{n}(n_{1}) − \binom{n}{2n_{1} − 2}^{r}f_{n}(n_{1} − 1)) \binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u}

and

Δ = \binom{n}{2n_{1} − 2}^{r} (f_{n}(n_{1}) − f_{n}(n_{1} − 1)) \binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u}.

Then, we have

B ≥ ∑_{k=1}^{n_{0}} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u}

= ∑_{k=1}^{n_{1}} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u} + ∑_{k=n_{1}+1}^{n_{0}} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u}

≥ (∑_{k=1}^{n_{1}} \binom{n}{2k − 2}^{r}f_{n}(k − 1)\binom{2(n + 1 − k)}{n + 1 − k}^{u} + Δ′) + ∑_{k=n_{1}+1}^{n_{0}} \binom{n}{2k}^{r}f_{n}(k)\binom{2(n − k)}{n − k}^{u}

= ∑_{l=0}^{n_{1}−1} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} + Δ′ + ∑_{k=n_{1}+1}^{n_{0}} \binom{n}{2k}^{r}f_{n}(k)\binom{2(n − k)}{n − k}^{u}

= ∑_{l=0,l≠n_{1}}^{n_{0}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} + Δ′,

(17) where we use (16) in the first inequality. Thus, we have

X(n + 1) − 2X(n) ≥ Δ′ − \binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n − n_{1})}{n − n_{1}}^{u}.  (18)

Note that Δ′ ≥ Δ, since

|2n_{1} − 1 − \frac{n}{2}| ≤ |2n_{1} − 2 − \frac{n}{2}|

and f_{n}(n_{1}) ≥ f_{n}(n_{1} − 1). Consequently, the inequality (18) implies

X(n + 1) − 2X(n) ≥ Δ − \binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n − n_{1})}{n − n_{1}}^{u}.  (19)

Write n = 4m + q with m ∈ ℤ^{+} and q ∈ {0, 1, 2, 3}. We see that n_{1} = m + 1 − δ_{0,q}. The proof of (15) then proceeds by cases, according to the value of q.

If q ∈ {1, 2}, then

|\frac{n}{2} − 2n_{1}| = |\frac{q}{2} + 2δ_{0,q} − 2| = 2 − \frac{q}{2} ≥ \frac{q}{2} = |\frac{q}{2} + 2δ_{0,q}| = |\frac{n}{2} − (2n_{1} − 2)| ,

so we have \binom{n}{2n_{1}−2} ≥ \binom{n}{2n_{1}}. Consequently, we have

\begin{aligned}\frac{1}{2}X(n) & ≤ ∑_{\begin{matrix}0≤l≤n_{0}, \\ l∉\{n_{1}−1,n_{1}\} \end{matrix}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} + \frac{1}{2} ∑_{l∈\{n_{1}−1,n_{1}\}}^{n_{0}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} \\ & ≤ ∑_{\begin{matrix}0≤l≤n_{0}, \\ l∉\{n_{1}−1,n_{1}\} \end{matrix}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} + \binom{n}{2n_{1} − 2}^{r}f_{n}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u} \\ & = X(n) + Δ − \binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n − n_{1})}{n − n_{1}}^{u}. \end{aligned} (20)

By (19) and (20), we get that

X(n + 1) ≥ \frac{3}{2}X(n).

Now assume that q = 3. We have

|\frac{n}{2} − 2n_{1}| = \frac{1}{2} = |\frac{n}{2} − (2n_{1} − 1)| < \frac{3}{2} = |\frac{n}{2} − (2n_{1} − 2)| ,

so we get

\binom{n}{2n_{1} − 1} = \binom{n}{2n_{1}} > \binom{n}{2n_{1} − 2}.

Consequently, we have

\begin{aligned}\frac{1}{2}X(n) & ≤ ∑_{\begin{matrix}0≤l≤n_{0}, \\ l∉\{n_{1}−1,n_{1}\} \end{matrix}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} + \frac{1}{2} ∑_{l∈\{n_{1}−1,n_{1}\}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} \\ & ≤ ∑_{\begin{matrix}0≤l≤n_{0}, \\ l∉\{n_{1}−1,n_{1}\} \end{matrix}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} + \binom{n}{2n_{1} − 1}^{r}f_{n}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u} \\ & = X(n) + Δ′ − \binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n − n_{1})}{n − n_{1}}^{u}. \end{aligned} (21)

By (18) and (21), we see that

X(n + 1) ≥ \frac{3}{2}X(n).

At last assume that q = 0. Then we have n = 4m, n_{0} = 2m, and n_{1} = m ≥ 2. Note that

\binom{n + 1}{2n_{1}}^{r} = \binom{4m + 1}{2m}^{r} = (\binom{4m}{2m}\frac{4m + 1}{2m + 1})^{r} ≥ \frac{9}{5}\binom{4m}{2m}^{r} = \frac{9}{5}\binom{n}{2n_{1}}^{r},

since m ≥ 2 and r ≥ 1. Thus, setting

E = X(n + 1) − \frac{9}{5}\binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u},

we have

\begin{aligned}E & ≥ X(n + 1) − \binom{n + 1}{2n_{1}}^{r}f_{n+1}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u} \\ & = \binom{2(n + 1)}{n + 1}^{u} + ∑_{1≤k≤n_{0},k≠n_{1}} \binom{n + 1}{2k}^{r}f_{n+1}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u} \\ & ≥ \binom{2n}{n}^{u} + ∑_{1≤k≤n_{0},k≠n_{1}} (\binom{n}{2k}^{r} + \binom{n}{2k − 1}^{r}) f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u} \\ & ≥ X(n) − \binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u} + ∑_{k=1,k≠n_{1}}^{n_{0}} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u}. \end{aligned} (22)

Recall that B = X(n + 1) − X(n). From (22), we see that

B ≥ \frac{4}{5}\binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u} + ∑_{k=1,k≠n_{1}}^{n_{0}} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u}. (23)

We claim that

∑_{k=1,k≠n_{1}}^{n_{0}} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u} ≥ ∑_{\begin{matrix}0≤l≤n_{0}, \\ l∉\{n_{1}−1,n_{1}\} \end{matrix}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u}.  (24)

In fact, the inequality (24) follows from the inequalities

∑_{k=1}^{n_{1}−1} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u} ≥ ∑_{k=1}^{n_{1}−1} \binom{n}{2k − 2}^{r}f_{n}(k − 1)\binom{2(n + 1 − k)}{n + 1 − k}^{u}

and

∑_{k=n_{1}+1}^{n_{0}} \binom{n}{2k − 1}^{r}f_{n}(k)\binom{2(n + 1 − k)}{n + 1 − k}^{u} ≥ ∑_{k=n_{1}+1}^{n_{0}} \binom{n}{2k}^{r}f_{n}(k)\binom{2(n − k)}{n − k}^{u}.

Observe that the term

\binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u} = \binom{4m}{2m}^{r}f_{4m}(m)\binom{6m + 2}{3m + 1}^{u}

is not smaller than both

\binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n − n_{1})}{n − n_{1}}^{u} = \binom{4m}{2m}^{r}f_{4m}(m)\binom{6m}{3m}^{u}

and

\binom{n}{2n_{1} − 2}^{r}f_{n}(n_{1} − 1)\binom{2(n − (n_{1} − 1))}{n − (n_{1} − 1)}^{u} = \binom{4m}{2m − 2}^{r}f_{4m}(m − 1)\binom{6m + 2}{3m + 1}^{u}.

Hence, we have

\binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u} ≥ \frac{1}{2} ∑_{l∈\{n_{1}−1,n_{1}\}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u}.  (25)

Therefore, by (23), (24), and (25), we deduce that

\begin{aligned}B & ≥ \frac{4}{5}\binom{n}{2n_{1}}^{r}f_{n}(n_{1})\binom{2(n + 1 − n_{1})}{n + 1 − n_{1}}^{u} + ∑_{\begin{matrix}0≤l≤n_{0}, \\ l∉\{n_{1}−1,n_{1}\} \end{matrix}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} \\ & ≥ \frac{2}{5} ∑_{l∈\{n_{1}−1,n_{1}\}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} + \frac{2}{5} ∑_{\begin{matrix}0≤l≤n_{0}, \\ l∉\{n_{1}−1,n_{1}\} \end{matrix}} \binom{n}{2l}^{r}f_{n}(l)\binom{2(n − l)}{n − l}^{u} \\ & = \frac{2}{5}X(n), \end{aligned}  (26)

which gives

X(n + 1) ≥ \frac{7}{5}X(n).

We have completed the proof of the claimed inequality (15) (and hence the theorem).

Remark 34. For every n, r_{1}, r_{2}, s, t, u ∈ ℤ_{≥0} with r_{1} + r_{2} ≥ 1, define

V (n, r_{1}, r_{2}, s, t, u) = ∑_{k=0}^{n} \binom{n}{k}^{r_{1}} \binom{n}{2k}^{r_{2}} \binom{n + k}{k}^{s}\binom{2k}{k}^{t}\binom{2(n − k)}{n − k}^{u}.

Here we follow the convention 0^{0} = 1. Note that (V (n, 1, 1, 0, 0, 0))_{n} is the sequence of quadrinomial coefficients \underline{A005725}. When r_{1}r_{2} = 0, i.e., when r_{1} = 0 or r_{2} = 0, the sequence (V (n, r_{1}, r_{2}, s, t, u))_{n=1}^{∞} is realizable by Remark 33 and Theorem 18. Indeed, for all r_{1}, r_{2}, s, t, u ∈ ℤ_{≥0} with r_{1}+r_{2} ≥ 1, an essentially same argument as the one given in the proof of Theorem 18 shows that the sequence (V (n, r_{1}, r_{2}, s, t, u))_{n=1}^{∞} is realizable. For shortening the paper, we omit the details. Remark 35. Let r_{1}, r_{2}, s, t, u be non-negative integers with r_{1} + r_{2} ≥ 1. Set V (n) = V (n, r_{1}, r_{2}, s, t, u) for n ≥ 1. Clearly, we have V (1) > 0. By checking the proof of Lemma 28, it is easy to see that (μ ∗ V)(n) > 0 for every n ≥ 1. According to Remark 34, the sequence (V (n))_{n}^{∞} is realizable. Then (μ ∗ V)(n) ≥ n for all n ≥ 1. Thus, for every map T : X → X realizing V and n ∈ ℤ^{+}, there is at least one periodic orbit of T with exact period n in X.

Proof of Theorem 21.

(1) For an arbitrary prime number p, we have

C(p) ≡ (p + 1)C(p) = \binom{2p}{p} = \frac{(p + 1) ⋯ (p + p − 1)}{(p − 1)!} × 2 ≡ 2 (mod p),  (27)

where the modulo is taken over the ring ℤ_{p}. Thus, we have

(μ ∗ C)(p) = C(p) − C(1) = C(p) − 1 ≡ 1 (mod p).  (28)

Assume that (C(n))_{n=1}^{∞} is almost realizable. By (28), we see that p | Fail(C). However, the prime number p can be arbitrary large, contradicting the fact that ℤ^{+} ∋ Fail(C) < ∞. Therefore, the sequence (C(n))_{n=1}^{∞} is not almost realizable.

(2) Let p be an arbitrary odd prime number. By using (27) and Lemma 25, we get

\begin{aligned}(μ ∗ M)(2p) & = M(2p) − M(p) − M(2) + M(1) \\ & = ∑_{k=0}^{p} \binom{2p}{2k}C(k) − ∑_{k=0}^{\frac{p−1}{2}} \binom{p}{2k}C(k) − 2 + 1 \\ & ≡ \binom{2p}{0}C(0) + \binom{2p}{2p}C(p) − \binom{p}{0}C(0) − 2 + 1 \\ & = C(p) − 1 \\ & ≡ 1 (mod p). \end{aligned}  (29)

Assume that (M(n))_{n=1}^{∞} is almost realizable. By (29), we deduce that p | Fail(M). Similar to (1), we see that (M(n))_{n=1}^{∞} is not almost realizable.

(3) Let p be an arbitrary odd prime number. For an integer p/2 < k < p − 1, we have

C(k) = \frac{1}{k + 1}\binom{2k}{k} ≡ 0 (mod p)

by Lemma 25. For an integer 0 < k < p/2, we have \binom{p+k}{2k} ≡ 0 (mod p) by Lemma 25. Note that

C(p − 1) = \frac{1}{p}\binom{2p − 2}{p − 1} = \frac{(p + 1) ⋯ (2p − 2)(2p − 1)}{(p − 1)!} \frac{1}{2p − 1} ≡ −1 (mod p).

Then with (27), we have

(μ ∗ S)(p) = S(p) − S(1) = ∑_{k=0}^{p} \binom{p + k}{2k}C(k) − 2

≡ \binom{p}{0}C(0) + \binom{2p − 1}{2p − 2}C(p − 1) + \binom{2p}{2p}C(p) − 2

≡ C(p) − C(p − 1) − 1

≡ 2 − (−1) − 1 = 2 (mod p).

Similar to (1), we see that (S(n))_{n=1}^{∞} is not almost realizable.

Remark 36. Although the sequences in Theorem 21 are not almost realizable, they all satisfy the sign condition. Clearly, we have C(n+1) = \frac{2(2n+1)}{n+2}C(n) ≥ 2C(n), for every n ≥ 1. Hence, by Lemma 28, the sequence (C(n))_{n=1}^{∞} satisfies the sign condition. Aigner [1, Proposition 3] proved that the sequence (M(n))_{n=0}^{∞} is log-concave, so the sign condition follows from M(2)/M(1) = 2 and Lemma 28. Xia and Yao [38, Corollary 7] showed that the sequence (s(n))_{n=0}^{∞} of little Schröder numbers is strictly log-concave, so the sign condition for (s(n))_{n=1}^{∞} follows from s(2)/s(1) = 3 and Lemma 28. Clearly, the sequence (S(n))_{n=1}^{∞} of large Schröder numbers also satisfies the sign condition.

4 Acknowledgments

We thank the anonymous referee for a careful reading of a first version of the manuscript and for numerous insightful remarks and suggestions that greatly improved the quality of the paper.

References

[1] M. Aigner, Motzkin numbers, European J. Combin. 19 (1998), 663–675.

[2] A. Apéry, Irrationalité de ζ(2) et ζ(3), Astérisque 61 (1979), 11–13.

[3] Nobuhiro Asai, Izumi Kubo, and H.-H. Kuo, Bell numbers, log-concavity, and logconvexity, Acta Appl. Math. 63 (2000), 79–87.

[4] C. Banderier and S. Schwer, Why Delannoy numbers?, J. Statist. Plann. Inference 135 (2005), 40–54.

[5] H. W. Becker and J. Riordan, The arithmetic of Bell and Stirling numbers, Amer. J. Math. 70 (1948), 385–394.

[6] E. T. Bell, The iterated exponential integers, Ann. of Math. 39 (1938), 539–557.

[7] F. Beukers, Another congruence for the Apéry numbers, J. Number Theory 25 (1987), 210–220.

[8] E. Catalan, Sur les nombres de Segner, Rend. Circ. Mat. Pal. 1 (1887), 190–201.

[9] H. H. Chan, S. H. Chan, and Z. Liu, Domb’s numbers and Ramanujan-Sato type series for 1/π, Adv. Math. 186 (2004), 396–410.

[10] W. Y. C. Chen and E. X. W. Xia, The 2-log-convexity of the Apéry numbers, Proc. Amer. Math. Soc. 139 (2011), 391–400.

[11] C. Domb, On the theory of cooperative phenomena in crystals, Adv. Phys. 9 (1960), 149–361.

[12] T. Došlić, Log-balanced combinatorial sequences, Int. J. Math. Math. Sci. 4 (2005), 507–522.

[13] G. Everest, A. J. van der Poorten, Y. Puri, and T. Ward, Integer sequences and periodic points, J. Integer Sequences 5 (2002), Article 02.2.3.

[14] J. Franel, On a question of Laisant, L’Intermédiaire des Mathématiciens 1 (1894), 45– 47.

[15] C. Helou and G. Terjanian, On Wolstenholme’s theorem and its converse, J. Number Theory 127 (2008), 475–499.

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

[17] P. G. Larcombe and D. R. French, On the “other” Catalan numbers: a historical formulation re-examined, Congr. Numer. 143 (2000), 33–64.

[18] P. G. Larcombe and D. R. French, A new generating function for the Catalan-Larcombe-French sequences: proof of a result by Jovovic, Congr. Numer. 166 (2004), 161–172.

[19] J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 2nd edition, 2001.

[20] A. Malik and A. Straub, Divisibility properties of sporadic Apéry-like numbers, Res. Number Theory 2 (2016), no. 5.

[21] G.-S. Mao and M. J. Schlosser, Supercongruences involving domb numbers and binary quadratic forms, Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM 118 (2024), no. 11.

[22] A. Maróti, On elementary lower bounds for the partition function, Integers 3 (2003), #A10.

[23] P. Miska and T. Ward, Stirling numbers and periodic points, Acta Arith. 201 (2021), 421–435.

[24] P. Moss, The arithmetic of realizable sequences, PhD thesis, University of East Anglia, 2003.

[25] P. Moss and T. Ward, Fibonacci along even powers is (almost) realizable, Fibonacci Quart. 60 (2022), 40–47.

[26] T. Motzkin, Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products, Bull. Amer. Math. Soc. 54 (1948), 352–360.

[27] R. Osburn and B. Sahu, A supercongruence for generalized Domb numbers, Funct. Approx. Comment. Math. 48 (2013), 29–36.

[28] Y. Puri, Arithmetic properties of periodic orbits, PhD thesis, University of East Anglia, 2000.

[29] Y. Puri and T. Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quart. 39 (2001), 398–402.

[30] A. L. Schmidt, Legendre transforms and Apéry’s sequences, J. Aust. Math. Soc. 58 (1995), 358–375.

[31] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. Available

at https://oeis.org.

[32] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Vol. 62 of Cambridge Stud. Adv. Math., Cambridge Univ. Press, 1999.

[33] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Vol. 49 of Cambridge Stud. Adv. Math., Cambridge Univ. Press, 2nd edition, 2011.

[34] A. Straub, Gessel-Lucas congruences for sporadic sequences, Monatsh. Math. (2023),

    published online. Available at https://doi.org/10.1007/s00605-023-01894-3.

[35] R. A. Sulanke, Objects counted by the central Delannoy numbers, J. Integer Sequences 6 (2003), Article 03.1.5.

[36] J. Touchard, Propriétés arithmétiques de certains nombres recurrents, Ann. Soc. Sci. Bruxelles 53A (1933), 21–31.

[37] A. J. Windsor, Smoothness is not an obstruction to realizability, Ergodic Theory Dynam. Systems 28 (2008), 1037–1041.

[38] E. X. W. Xia and O. X. M. Yao, A criterion for the log-convexity of combinatorial sequences, Electron. J. Combin. 20 (4) (2013), #P3.

[39] W. Xia and Z.-W. Sun, On congruences involving Apéry numbers, Proc. Amer. Math. Soc. 151 (2023), 3305–3315.

[40] D. Zagier, Integral solutions of Apéry-like recurrence equations, In Groups and Symmetries: From Neolithic Scots to John McKay, Vol. 47 of CRM Proc. Lecture Notes, pp. 349–366. Amer. Math. Soc., 2009.

2020 Mathematics Subject Classification: Primary 11B50; Secondary 37P35, 05A10, 11B83. Keywords: realizability, almost realizability, Apéry number, Franel number, Domb number, central Delannoy number.

(Concerned with sequences \underline{A000032}, \underline{A000041}, \underline{A000045}, \underline{A000108}, \underline{A000110}, \underline{A000166}, \underline{A000172}, \underline{A000225}, \underline{A000364}, \underline{A000984}, \underline{A001003}, \underline{A001006}, \underline{A001067}, \underline{A001263}, \underline{A001850}, \underline{A002426}, \underline{A002445}, \underline{A002893}, \underline{A002895}, \underline{A005258}, \underline{A005259}, \underline{A005260}, \underline{A005725}, \underline{A006318}, \underline{A006953}, \underline{A053175}, \underline{A054783}, \underline{A062510}, \underline{A081085}, \underline{A122045}, and \underline{A226158}.)

Received March 20 2023; revised versions received March 21 2023; February 26 2024. Published in Journal of Integer Sequences, February 28 2024.

Return to Journal of Integer Sequences home page.