Lucasnomial Fuss-Catalan Numbers and Related Divisibility Questions

Christian Ballot Département de Mathématiques et Informatique Université de Caen-Normandie France

              christian.ballot@unicaen.fr

Abstract

For all integers n ≥ 1 we define the generalized Lucasnomial Fuss-Catalan numbers

C_{U,a,r}(n) := \frac{U_{r}}{U_{(a−1)n+r}} \binom{an + r − 1}{n}_{U},

and prove their integrality. Here U is a fundamental Lucas sequence, a ≥ 2 and r ≥ 1 are integers, and \binom{∗}{∗}_{U} denotes a Lucasnomial coefficient. If U = I, where I_{n} = n, then the C_{I,a,r}(n) are the usual generalized Fuss-Catalan numbers. With the assumption that U is regular, we show that U_{(a−1)n+k} divides \binom{an}{n}_{U} for all n ≥ 1 but a set of asymptotic density 0 if k ≥ 1, but only for a small set if k ≤ 0. This small set is finite when U ≠ I and at most of upper asymptotic density 1 − log 2 when U = I. We also determine all triples (U, a, k), where k ≥ 2, for which the exceptional set of density 0 is actually finite, and in fact empty.

1 Introduction

The Catalan numbers C_{n}, which may be defined algebraically by the formula \frac{1}{n+1} \binom{2n}{n}, appear in all kinds of mathematical contexts and have numerous combinatorial interpretations. One may get seriously acquainted with them by consulting the recent book of Stanley [28]. They admit several generalizations. Two of them are relevant to this paper. First, the generalized Fuss-Catalan numbers, defined for all integers n ≥ 1 as

\frac{r}{(a − 1)n + r}\binom{an + r − 1}{n},  (1)

where a ≥ 2 and r ≥ 1 are fixed integers. Fuss-Catalan numbers, which correspond to r = 1, are shown [28, Exercise A14, pp. 108] to have combinatorial interpretations that extend some of the interpretations for ordinary Catalan numbers. We note that Fuss-Catalan numbers are sometimes plainly called generalized Catalan numbers (e.g., [29]). The second generalization of interest to this paper are the Lucasnomial Catalan numbers

\frac{1}{U_{n+1}} \binom{2n}{n}_{U},  (2)

where U = (U_{n}) is a fundamental Lucas sequence and \binom{2n}{n}_{U} is the generalized central binomial coefficient with respect to U. Both generalizations are known to yield integers only; see, e.g., [5, 11]. In Section 2, the integrality of more general numbers is proved, namely the generalized Lucasnomial Fuss-Catalan numbers

C_{U,a,r}(n) := \frac{U_{r}}{U_{(a−1)n+r}} \binom{an + r − 1}{n}_{U},  (3)

where U is a regular fundamental Lucas sequence, and a ≥ 2 and r ≥ 1 are given integers. The numbers

C_{U,a,1}(n) = \frac{1}{U_{(a−1)n+1}} \binom{an}{n}_{U},  (4)

where r = 1 are simply referred to as Lucasnomial Fuss-Catalan numbers. Thus, ordinary Catalan and Fibonomial Catalan numbers which correspond, respectively, to (U, a, r) = (I, 2, 1) and (U, a, r) = (F, 2, 1) are particular instances of Lucasnomial Fuss-Catalan numbers. Throughout the paper, the letter I denotes the identity sequence, i.e., I_{n} = n for all n ≥ 0, while F denotes the Fibonacci sequence defined by F_{n+2} = F_{n+1} + F_{n}, for all n ≥ 0, F_{0} = 0 and F_{1} = 1.

In Section 2, the integrality of various Lucasnomial generalizations of classical numbers is established. Indeed, Theorem 6 unconditionally establishes the integrality of all Lucasnomial Fuss-Catalan numbers, Theorem 9 proves the integrality of all generalized Lucasnomial Fuss-Catalan numbers with the restriction that U be regular, Theorem 12 deduces from Theorem 9 the integrality of the generalized Lucasnomial Lobb numbers L_{m,s}^{U,a}, defined by

L_{m,s}^{U,a} := \frac{U_{as+1}}{U_{(a−1)m+s+1}} \binom{am}{(a − 1)m + s}_{U},  (5)

for a ≥ 1, m > s ≥ 0, and, given the author’s patronym we could hardly fail to show Theorem 13, which establishes the integrality of all Lucasnomial ballot numbers B_{U}(a, b), defined by

B_{U}(a, b) := \frac{U_{a−b}}{U_{a+b}} \binom{a + b}{a}_{U},  (6)

for all a > b ≥ 0 integers.

However, Section 2 apart, the rest of the paper is devoted to a variant of Lucasnomial Fuss-Catalan numbers, namely the numbers

\frac{1}{U_{(a−1)n+k}} \binom{an}{n}_{U},  (7)

where k is a fixed integer. The investigation we launched into persues the research work conducted in two recent papers, one of Pomerance [22] and then one of the author [5].

Given a triple (U, a, k), we consider the set D_{U,a,k} of all positive integers n for which U_{(a−1)n+k} divides the Lucasnomial \binom{an}{n}_{U}. When n is in D_{U,a,k}, then the numbers in (7) are integers. When k = 1, they are Lucasnomial Fuss-Catalan numbers and are integers for all n ≥ 1. Thus, D_{U,a,1} = ℕ. The main question the paper addresses is how does replacing 1 by k affects the sets D_{U,a,k}? How far astray do we get from the Catalan phenomenon?

In his clear and attractive paper [22], Pomerance studied how often the middle binomial coefficients \binom{2n}{n} are divisible by n + k, when k is a fixed arbitrary integer. The enquiry brought out two chief phenomena: the singularity of the Catalan numbers and a drastic difference in behavior between the case k ≥ 1 and the case k ≤ 0. Indeed, if k ≠ 1, then \overline{D}_{I,2,k}, the complementary set of D_{I,2,k} in the positive integers, is infinite. That is, there are infinitely many n for which n + k does not divide \binom{2n}{n}. Secondly, if k ≥ 1, then D_{I,2,k} has asymptotic density one, whereas if k ≤ 0, although D_{I,2,k} is infinite, its upper asymptotic density, whose value is still unknown — see Section 3 — is small and definitely less than 1/3.

Before describing the content of the second paper [5], we recall some notions.

A fundamental Lucas sequence U = U(P, Q) is a binary linear recurrent sequence defined by the initial values U_{0} = 0, U_{1} = 1 and the recurrence

U_{n+2} = P U_{n+1} − QU_{n},  (8)

for all integers n ≥ 0, where P and Q are nonzero integers. The discriminant Δ of U(P, Q) is P^{2} − 4Q, i.e., it is the discriminant of the characteristic polynomial associated with the recursion.

In stating our results we often use the notation U(P, Q), with parameters P and Q, to designate a Lucas sequence later simply referred to as U and with terms U_{n}. Note that all terms of a sequence U are integers. With its initial conditions U turns out to be a divisibility, or a divisible sequence, i.e., one that satisfies, for all positive integers m and n, the property

m | n ⟹ U_{m} | U_{n}.  (9)

A fundamental Lucas sequence is nondegenerate if U_{n} ≠ 0 for all n ≥ 1. Nondegeneracy occurs whenever the ratio of the zeros of x^{2} − P x + Q is not a root of unity of order ≥ 2. Alternatively, the condition U_{12} ≠ 0 is necessary and sufficient to ensure the nondegeneracy of U — see, e.g., [2, Section 2]. We sometimes use the abbreviation ‘NFLS’, or ‘NFL-sequence’, for a nondegenerate fundamental Lucas sequence.

A regular Lucas sequence U(P, Q) is a NFLS such that gcd(P, Q) = 1.^{1} This property is well-known to confer a stronger form of divisibility to the sequence U, i.e., for all nonnegative integers m and n

gcd(U_{m}, U_{n}) = |U_{gcd(m,n)}|.  (10)

Conversely, property (10) is easily seen to imply gcd(P, Q) = 1.

A Lucasnomial, or a Lucasnomial coefficient, is a generalized binomial coefficient with respect to a nondegenerate fundamental Lucas sequence U. That is, for m ≥ n ≥ 1, the Lucasnomial \binom{m}{n}_{U} is defined as

\binom{m}{n}_{U} := \frac{U_{m}U_{m−1} ⋯ U_{m−n+1}}{U_{n}U_{n−1} ⋯ U_{1}} ,

and as 1, if m ≥ 0 and n = 0, and as 0 otherwise. Thus, for instance,

\binom{6}{3}_{F} = \frac{F_{6} · F_{5} · F_{4}}{F_{3} · F_{2} · F_{1}} = \frac{8 · 5 · 3}{2 · 1 · 1} = 60.

The important Lucasnomial identity

\binom{m}{n}_{U} = U_{n+1}\binom{m − 1}{n}_{U} − QU_{m−n−1}\binom{m − 1}{n − 1}_{U}, for m ≥ n ≥ 1,  (11)

easily follows from the Lucas identity [2, Section 5]

U_{m} = U_{n+1}U_{m−n} − QU_{n}U_{m−n−1}.

The integrality of all Lucasnomials may be seen inductively from (11).

There are two particular Lucas sequences U(P, Q) for which the corresponding Lucasnomials have their own name. On the one hand, of course, the ordinary binomial coefficients \binom{m}{n} = \binom{m}{n}_{I}, for which I = U(2, 1) and I_{n} = n for all n ≥ 0. On the other hand, we have the Fibonomials, \binom{m}{n}_{F}, derived from the much-studied Fibonacci sequence F which is equal to U(1, −1). Indeed, Fibonomials appeared earlier than general Lucasnomials in the mathematical literature.

In the sequel, we usually assume P > 0. Indeed, given P and Q,

U(−P, Q)(n) = (−1)^{n−1}U(P, Q)(n), for all n ≥ 0,

so that Lucasnomials with respect to U(−P, Q) are, up to sign, identical to corresponding Lucasnomials with respect to U(P, Q). Therefore, the two sets D_{U(±P,Q),a,k} are identical.

Lucasnomial Catalan numbers with respect to a NFLS U, defined in (2), deserve their appellation as they are integral for all n ≥ 0 [5, 12, 14, 24]. Gould [13, 14] might have been the first person to coin the term ‘Fibonomial Catalan number’ for U = F and to prove their integrality. To date and to our knowledge there is no combinatorial interpretation of Lucasnomial Catalan numbers for U ≠ I, even though combinatorial interpretations of Lucasnomials themselves exist and have received attention [6, 7, 23, 24].

1The nondegeneracy condition simplifies to U_{3} ≠ 0, i.e., to not having P^{2} = Q = 1 when gcd(P, Q) = 1.

Because I is a particular NFLS and because the Catalan phenomenon persists when we consider Lucasnomial Catalan numbers, it was natural to find out whether

1. The sets D_{U,2,k} all missed infinitely many integers as soon as k ≠ 1,

2. The cleavage observed between the cases k ≥ 1 and k ≤ 0 for U = I remained true generally.

The answers [5] were essentially affirmative at least for all regular Lucas sequences if not for one exception with respect to question 1, namely the sequence U(1, 2). For this sequence, D_{U,2,2} turns out to be the whole set of natural numbers. The behavioral dichotomy between k ≥ 1 and k ≤ 0 is even sharper than for U = I. That is, if Δ ≠ 0, then the sets D_{U,2,k} are finite when k ≤ 0, but still have asymptotic density 1 when k ≥ 1. (The only two zero-discriminant regular Lucas sequences are U(±2, 1) and the only one with P > 0 is U = I = U(2, 1).)

This paper sets about discovering whether, for all regular Lucas sequences U and all integers k, the divisor sets D_{U,a,k} display the same features for a > 2 as for a = 2. Section 3 is a study of the case k ≤ 0: Theorem 14 shows the finiteness of all D_{U,a,k} when U is not I, while, in Theorem 15, the sets D_{I,a,k} are once more proven to be of asymptotic density less than 1/3. That all sets D_{I,a,k}, k ≤ 0, are infinite, is conjectured, but only proven, given an a ≥ 3, for infinitely many values of k in Theorem 16. The section ends by discussing the current knowledge about the size of D_{I,2,0}, the set of integers n ≥ 1 that divide the middle binomial coefficient \binom{2n}{n}. It may seem like a simple case, yet with much food for thought leftover.

Section 4 establishes a number of lemmas and examines some examples that help to understand the direction we took and the methods we used, while speeding up the search carried out in Section 5. Indeed, Section 5 is devoted to the search for triples (U, a, k), k ≥ 2, called Catalan-like triples, for which D_{U,a,k} is the entire set of all natural numbers. We found exactly four new Catalan-like triples. Except for those five Catalan-like triples — i.e., including the triple (U(1, 2), 2, 2) found in [5] — the sets D_{U,a,k}, k ≥ 2, all miss infinitely many positive integers. Theorem 30 summarizes the various partial results of Section 5.

The proof that all D_{U,a,k} are of asymptotic density 1 when k ≥ 1 is established in Section 6 and finalized in Theorem 37. One of the findings that comes out of the proof of Theorem 37 is that for each triple (U, a, k), U regular, a ≥ 2 and k ≥ 1, there is a minimal integer m ≥ 1 such that

\frac{m}{U_{(a−1)n+k}} \binom{an}{n}_{U} is integral for all n ≥ 1.  (12)

We may say that the triple (U, a, k) belongs to the integer m. Thus, amongst all regular U, the triples (U, a, 1), a ≥ 2, and the five Catalan-like triples are all the triples that belong to 1. The triple (F, 3, 2) is seen to belong to 3 as an outcome of the proof of Corollary 18 of Section 4. This observation raises numerous questions such as

Question 1. What are all triples (U, a, k), U regular, that belong to 3?

Question 2. Are there triples that belong to m for all m ≥ 1? If not, what is the set of m not represented by any triple?

Question 3. Can one find general criteria that describe the triples that belong to a given m?

One might consider a further more general research problem which we tentatively state below.

Problem 1. Can one obtain even broader theorems using the generalized Lucasnomial Fuss-Catalan numbers defined in (3)? Perhaps, the following problem, or a variant of it, would just do: Given a quadruple (U, a, r, k), a ≥ 2, r ≥ 1, k an integer, one could study the sets D_{U,a,r,k} of integers n ≥ 1 such that

\frac{U_{r}}{U_{(a−1)n+k}} \binom{an + r − 1}{n}_{U},  (13)

is an integer. What density would these sets obey? Would one find a corresponding cleavage between the cases k < r and k ≥ r? Could one find all Catalan-like quadruples (U, a, r, k) for which the numbers in (13) are always integers?

Some explicit Kummer rule was devised [11] for another whole class of generalized binomial coefficients, namely those generalized with respect to multiplicative arithmetic functions with range in the positive integers. Thus, one may consider a study comparable to ours in this context. Let us state the problem more precisely.

Problem 2. If (u_{n})_{n≥1} is a sequence of positive integers such that

u_{mn} = u_{m}u_{n}, if gcd(m, n) = 1,  (multiplicative)
u_{m} | u_{n},  if m | n,  (divisible)

then the generalized Fuss-Catalan numbers with respect to u

\frac{u_{r}}{u_{(a−1)n+r}} \binom{an + r − 1}{n}_{u}

are shown to be integers [11]. Studying, say when r = 1, the sets D_{u,a,k} of integers n ≥ 1 for which u_{(a−1)n+k} divides \binom{an}{n}_{u}, would be an interesting project. In particular and for instance, let u_{n} = φ(n), where φ is the Euler totient function, a sequence both multiplicative and divisible. Then for k ≠ 1, what can be said of the sets D_{u,2,k} of integers n ≥ 1 such that

\frac{1}{u_{n+k}} \binom{2n}{n}_{u} is an integer?

(Some authors [10, 19] have studied generalized binomial coefficients with respect to the Euler function φ.)

The paper is mostly very elementary, but draws on three main sources for its proofs. One source is the classification [1, 8] of all k-defective regular Lucas sequences. A prime p is said to be a primitive prime divisor (p.p.d.) of the nth term of a Lucas sequence U if and only if p | U_{n}, but p ∤ U_{m}, 1 < m < n. Given k ≥ 2, a regular Lucas sequence U(P, Q) of discriminant Δ ≠ 0 is said to be k-defective if and only if U_{k} does not have primitive prime divisors not dividing Δ. For instance, F is 6-defective as F_{6} = 8 and F_{3} = 2. The prime 5 is a p.p.d. of F_{5} = 5, but F is 5-defective as the discriminant Δ_{F} = 5. The primitive divisor theorem [8, Theorem 1.4] asserts that for regular nonzero-discriminant Lucas sequences U, U_{n} has a primitive prime divisor not dividing Δ, for all n > 30. So there are no k-defective regular Lucas sequences U, U ≠ I, for k > 30. Moreover, tables of all k-defective regular U were made [8] for all values of k, 1 < k < 31. Some errors remained and were later corrected [1]. The tables [1, 8] list Lucas sequences U in terms of P and Δ. For convenience, and so the readers can better follow some of the arguments in Section 5, we added a table, Table A, in an appendix in Section 7. Table A gathers together the various tables [8, Tables 1 and 3, pp. 78–79], [1, p. 312], but indexes Lucas sequences with the parameters P and Q instead. We note here that our arguments use primitive divisors so that primes dividing Δ may occasionally help to conclude a particular argument case.

Note that in Section 5, Proposition 29, we could not show the sets D_{I,a,k}, for k ≥ 2, missed infinitely many integers using the primitive divisor theorem or the tables of k-defective regular Lucas sequences, and we had to come up with specific arguments.

Another extensive source of proofs throughout the paper are the Kummer rules for determining the p-adic valuation of binomial coefficients or Lucasnomials when p is a prime. Kummer’s rule [18] gives the p-adic valuation of the binomial coefficient \binom{m+n}{n} as the number of carries in the addition of m and n performed in base p. Kummer-like theorems were obtained [17] for generalized binomial coefficients with respect to regular sequences of positive integers, i.e., sequences satisfying property (10), and an explicit theorem for Fibonomial coefficients [17, Theorem 2]. An explicit theorem for Lucasnomials with respect to a generic NFLS U(P, Q) is given in [3, Theorem 4.2] and repeated below in Proposition 4.

As for the two preceding papers [5, 22], a key point is that n ∈ D_{U,a,k} if and only if for each prime p, the p-adic valuation of \binom{an}{n}_{U} is at least that of U_{(a−1)n+k}.

The p-adic valuation of the terms U_{n} (or U_{(a−1)n+k}) of a Lucas sequence has been known to obey certain rules since at least the time of Lucas [20, Section XIII], but is being reproved every now and then in various guises (one of the latest appeared in a recent issue of the Fibonacci Quarterly [26]). The theory of Lucas sequences is the third main source of our proofs with which we assume some familiarity from the readers. Chapter 4 of the book [31] can serve as a valuable introduction. Still we recall some basic facts for completeness’ sake. The rank ρ_{U}(p), or ρ, of a prime p in a Lucas sequence U(P, Q) is the smallest positive index t such that p divides U_{t}. It is guaranteed to exist when p ∤ Q.

By [3, Eq. (4.4) and Theorem 4.1, Section 4], we next state a proposition that gives the p-adic valuation of all terms of a NFL-sequence U(P, Q) for all primes p ∤ Q. The content of Proposition 3 is what classically constitutes the Lucas laws of appearance and repetition for primes and prime powers in Lucas sequences.

Proposition 3. Let U(P, Q) be a nondegenerate fundamental Lucas sequence and p ∤ Q be a prime of rank ρ in U. Then, for all positive integers m and n, we have

ρ divides p − (Δ | p), if p is odd,
p | U_{n} if and only if ρ | n,
ν_{p}(U_{mρ}) = ν_{p}(m) + ν_{p}(U_{ρ}) + δ · [2 | m] := x + ν + δ_{x},

where Δ = P^{2} − 4Q, (∗ | ∗) is the Legendre symbol, x = ν_{p}(m), ν = ν_{p}(U_{ρ}),

δ = ν_{2}((P^{2} − 3Q)/2) · [p = 2] · [2 ∤ P Q],

and δ_{x} = δ · [x > 0].

The notation x, ν, δ and δ_{x} is used consistently with the utilization of Proposition 3 throughout the paper. In Proposition 3, we used the Iverson symbol [−], defined by:

[P] = \begin{cases}1, & if P is a true statement; \\ 0, & if not. \end{cases}

Here is the explicit Kummer rule obtained in [2, Section 4].

Proposition 4. (Kummer’s rule for Lucasnomials) Let U(P, Q) be a nondegenerate Lucas sequence and p ∤ Q be a prime of rank ρ in U. Let m and n be two positive integers. Then the p-adic valuation of the Lucasnomial \binom{m+n}{n}_{U} is equal to the number of carries that occur to the left of the radix point when m/ρ and n/ρ are added in base-p notation, plus ν_{p}(U_{ρ}) if a carry occurs across the radix point, plus δ if a carry occurs from the first to the second digit to the left of the radix point, where δ was defined in Proposition 3.

This proposition suggests we distinguish carries across or to the left of the radix point from the other carries. Thus, as in [3, 5], when adding m/ρ + n/ρ in base p, we call a carry relevant when it occurs across or to the left of the radix point.

Here is an illustrative example of the use of Proposition 4 with U(1, −5) in order to determine the 2-adic valuation of \binom{20}{5}_{U}. We see that U_{3} = 6 so that ρ(2) = 3 and ν = 1. Also, P^{2} − 3Q = 16 so that δ = 3. Now, using some self-evident base-2 writing, we find that

\frac{15}{ρ} = 5 = (101)_{2},
\frac{5}{ρ} = 1 + \frac{2}{3} = (1.\overline{10}^{∞})_{2}.

Hence, there is only one relevant carry from first to second digit left of the radix point in the base-2 sum of 15/ρ and 5/ρ. Thus, by our Kummerian rule, ν_{2}\binom{20}{5}_{U} = 1 + 0 + δ = 4. Using Proposition 3 one can directly check that

ν_{2}\binom{20}{5}_{U} = ν_{2}(\frac{U_{20} · U_{19} · U_{18} · U_{17} · U_{16}}{U_{5} · U_{4} · U_{3} · U_{2} · U_{1}} ) = ν_{2}(\frac{U_{18}}{U_{3}} ).

However, ν_{2}(U_{18}) = ν_{2}(U_{3·2^{1}·ρ}) = 1 + ν_{2}(U_{3}) + δ.

We won’t always mention the Propositions 3 and 4 when using them.

The letter p invariably denotes a prime number except in Lemma 33. Although we usually write the p-adic valuation of an integer m, i.e., the highest exponent e ≥ 0 of p such that p^{e} divides m, as ν_{p}(m), we omit the parentheses when m is a Lucasnomial coefficient \binom{ℓ}{k}_{U} and write instead ν_{p}\binom{ℓ}{k}_{U}. We also occasionally use the alternative notation p^{e}||m.

Given a subset S of the natural numbers, we write S(z) for the elements of S not exceeding z and #S(z) for the cardinality of S(z). We say S has asymptotic density d to mean that the ratios #S(z)/z tend to d as z tends to infinity. The sentence “almost all positive integers” means all but a set of asymptotic density 0. The upper asymptotic density of S is the upper limit of the ratios #S(z)/z as z tends to infinity.

2 Integrality of Lucasnomial Fuss-Catalan numbers and other Lucasnomial extensions of classical numbers

The forthcoming lemma leads to an unconditional algebraic proof of the integrality of Lucasnomial Fuss-Catalan numbers. As for the integrality of generalized Lucasnomial Fuss-Catalan numbers, we provide an arithmetic proof, alas conditional to the regularity of the Lucas sequence.

Lemma 5. Let U be a nondegenerate fundamental Lucas sequence and a ≥ 2, r ≥ 1 be integers. Then the generalized Lucasnomial Fuss-Catalan numbers satisfy, for all n ≥ 1, the identity

C_{U,a,r}(n) = U_{r} · \binom{an + r − 2}{n − 1}_{U} − Q\frac{U_{r}U_{(a−1)n+r−1}}{U_{n}} · \binom{an + r − 2}{n − 2}_{U}.  (14)

Proof. Replacing m by an + r − 1 and n by (a − 1)n + r − 1 in (11), we obtain

\binom{an + r − 1}{(a − 1)n + r − 1}_{U} = U_{(a−1)n+r}\binom{an + r − 2}{(a − 1)n + r − 1}_{U} − QU_{n−1}\binom{an + r − 2}{(a − 1)n + r − 2}_{U}.

That is, using the symmetry of the Lucasnomial triangle,

\binom{an + r − 1}{n}_{U} = U_{(a−1)n+r}\binom{an + r − 2}{n − 1}_{U} − QU_{n−1}\binom{an + r − 2}{n}_{U}.

Multiplying through by U_{r}/U_{(a−1)n+r}, we find that

C_{U,a,r}(n) = U_{r}\binom{an + r − 2}{n − 1}_{U} − Q\frac{U_{r}U_{n−1}}{U_{(a−1)n+r}} \binom{an + r − 2}{n}_{U}.

But

\frac{U_{n−1}}{U_{(a−1)n+r}} \binom{an + r − 2}{n}_{U} = \frac{U_{n−1}}{U_{(a−1)n+r}} · \frac{U_{an+r−2} ⋯ U_{(a−1)n+r−1}}{U_{n} ⋯ U_{1}}
= \frac{U_{(a−1)n+r−1}}{U_{n}} · \frac{U_{an+r−2} ⋯ U_{(a−1)n+r+1}}{U_{n−2} ⋯ U_{1}}
= \frac{U_{(a−1)n+r−1}}{U_{n}} · \binom{an + r − 2}{n − 2}_{U},

which yields equation (14).

Theorem 6. Let U be a nondegenerate fundamental Lucas sequence and a ≥ 2 be an integer. Then the Lucasnomial Fuss-Catalan numbers

C_{U,a,1}(n) = \frac{1}{U_{(a−1)n+1}} \binom{an}{n}_{U} are integers for all n ≥ 1.

Proof. As U_{n} divides U_{(a−1)n}, setting r = 1 in identity (14) we readily see that C_{U,a,1}(n) is an integer.

We will use the next small lemma a few times.

Lemma 7. Let U(P, Q) be a fundamental Lucas sequence and p be a prime. If p ∤ gcd(P, Q), then either p ∤ Q, or p does not divide any term U_{n}, n ≥ 1, i.e., p has no rank.

Proof. Suppose p | Q. Then p ∤ P. Using (8) inductively, one finds U_{n} ≡ P^{n−1} (mod p) for all n ≥ 1. Therefore, p ∤ U_{n}.

Here is a straightforward observation about generalized Lucasnomial Fuss-Catalan numbers.

Remark 8. Ordinary Catalan numbers C_{I,2,1}(n) = \frac{1}{n+1} \binom{2n}{n} have the well-known alternative representations

\frac{1}{2n + 1}\binom{2n + 1}{n} and \frac{1}{n}\binom{2n}{n − 1},

which carry over to generalized Lucasnomial Fuss-Catalan numbers. That is,

C_{U,a,r}(n) = \frac{U_{r}}{U_{an+r}} \binom{an + r}{n}_{U} = \frac{U_{r}}{U_{n}} \binom{an + r − 1}{n − 1}_{U}.  (15)

Using the last form of C_{U,a,r}(n) in (15), we produce an arithmetic proof of the integrality of C_{U,a,r}(n). However, it assumes the regularity of U.

Theorem 9. Let U(P, Q) be a regular fundamental Lucas sequence. Let r ≥ 1 and a ≥ 2 be integers. Then the generalized Lucasnomial Fuss-Catalan numbers

\frac{U_{r}}{U_{(a−1)n+r}} \binom{an + r − 1}{n}_{U} are integral for all n ≥ 1.

Proof. By (15),

C_{U,a,r}(n) = \frac{U_{r}}{U_{n}} \binom{an + r − 1}{n − 1}_{U}.

We claim that for all primes p the p-adic valuation of U_{r}\binom{an+r−1}{n−1}_{U} is at least that of U_{n}. If p | Q, then, by Lemma 7, p ∤ U_{n} and our claim holds. Now suppose p ∤ Q and p divides U_{n}. Then, by Proposition 3, n = λρp^{x} for some x ≥ 0 and some λ prime to p, where ρ is the rank of p, and ν_{p}(U_{n}) = x + ν + δ_{x}. Let us divide r by ρ and write r = qρ + r_{1} with 0 ≤ q and 0 ≤ r_{1} < ρ. Then

\frac{n − 1}{ρ} = λp^{x} − \frac{1}{ρ} = (λp^{x} − 1) + \frac{ρ − 1}{ρ},
\frac{(a − 1)n + r}{ρ} = λ(a − 1)p^{x} + q + \frac{r_{1}}{ρ} .

If the sum of the fractional parts of (n − 1)/ρ and ((a − 1)n + r)/ρ is at least 1, then a carry occurs across the radix point which ensures, independently of the value of q, a minimum of x carries left of the radix point in the base-p addition of (n − 1)/ρ and ((a − 1)n + r)/ρ. Indeed, the first x base-p digits of (n − 1)/ρ left of the radix point are all p − 1. Therefore, by Kummer’s rule for Lucasnomials, ν_{p}\binom{an+r−1}{n−1}_{U} ≥ x + ν + δ_{x} = ν_{p}(U_{n}).

If the fractional parts add up to less than 1, i.e., if (ρ − 1) + r_{1} < ρ, then r_{1} = 0 and r = qρ. Let p^{i}, i ≥ 0, be the exact p-power dividing q. Then p^{i+ν+δ_{i}}||U_{r}. If i ≥ x then p^{x+ν+δ_{x}} divides U_{r} and our claim holds. If i < x, then the base-p addition of p^{x} − 1 to q produces x − i carries. Note that, using the Iverson symbol, δ_{x} = δ_{i} + δ_{x} · [i = 0]. Hence,

ν_{p}(U_{r}) + ν_{p}\binom{an + r − 1}{n − 1}_{U} ≥ (i + ν + δ_{i}) + (x − i + δ · [i = 0] · [x > 0]) = x + ν + δ_{x} = ν_{p}(U_{n}).

Thus, C_{U,a,r}(n) is always an integer.

Remark 10. We could have stated a stronger theorem by dropping the regularity assumption on U(P, Q) and instead stating that for all primes p ∤ gcd(P, Q), the p-adic valuation of the numbers C_{U,a,r}(n) is nonnegative, for all n ≥ 1.

We do not resist giving another related theorem with a different simple proof technique that partially implies Theorem 6 and Theorem 9.

Theorem 11. Let U(P, Q) be a regular fundamental Lucas sequence. Let r ≥ 1 and m ≥ n ≥ 1 be integers with gcd(m + r, n) = 1. Then the generalized Lucasnomial Fuss-Catalan numbers

T_{m,n,r} := \frac{U_{r}}{U_{m+r}} \binom{m + n + r − 1}{n}_{U} are integers.

Proof. We see that U_{m+r}T_{m,n,r} is an integer and that

U_{n}T_{m,n,r} = U_{r}\binom{m + n + r − 1}{n − 1}_{U},

is also integral. Since U is regular and gcd(m+r, n) = 1, we find that gcd(U_{m+r}, U_{n}) = 1 and immediately infer that T_{m,n,r} is the greatest common divisor of the two integers U_{m+r}T_{m,n,r} and U_{n}T_{m,n,r}. Hence, T_{m,n,r} is an integer.

Putting m = (a − 1)n in T_{m,n,r}, we see that Theorem 9 holds albeit with the restriction that gcd(r, n) = 1. If r = 1, then we obtain Theorem 6 though only for U regular.

Lobb numbers L_{m,s} = L_{m,s}^{2} and generalized Lobb numbers L_{m,s}^{a} are defined by the expression

L_{m,s}^{a} := \frac{as + 1}{(a − 1)m + s + 1}\binom{am}{(a − 1)m + s};

see [9, Eq. (11)].

The integrality of generalized Lucasnomial Lobb numbers (5) which are a natural Lucasnomial extension of the generalized Lobb numbers is the object of the next theorem.

Theorem 12. If U is a regular Lucas sequence, a ≥ 1, m > s ≥ 0 are integers, then the generalized Lucasnomial Lobb numbers

L_{m,s}^{U,a} = \frac{U_{as+1}}{U_{(a−1)m+s+1}} \binom{am}{(a − 1)m + s}_{U}

are integers.

Proof. Putting r = as + 1 and n = m − s in the expression (3) for C_{U,a,r}(n) yields L_{m,s}^{U,a}, so that, by Theorem 9, the numbers L_{m,s}^{U,a} are integral. Indeed,

C_{U,a,r}(n) = \frac{U_{as+1}}{U_{(a−1)(m−s)+as+1}} · \binom{a(m − s) + (as + 1) − 1}{m − s}_{U}
= \frac{U_{as+1}}{U_{(a−1)m+s+1}} · \binom{am}{m − s}_{U}
= \frac{U_{as+1}}{U_{(a−1)m+s+1}} · \binom{am}{(a − 1)m + s}_{U} = L_{m,s}^{U,a}.

Similarly, the natural Lucasnomial extension of ballot numbers is shown to always yield integers. Ordinary ballot numbers are defined by B(m, n) = \frac{m−n}{m+n} \binom{m+n}{n}; see (14) in [9].

Theorem 13. If U is a regular Lucas sequence, m > n ≥ 0 are integers, then the Lucasnomial ballot numbers

B_{U}(m, n) = \frac{U_{m−n}}{U_{m+n}} \binom{m + n}{n}_{U}

are integers.

Proof. If m and n have different parities, then replacing m by (m + n − 1)/2 and s by (m − n − 1)/2 in L_{m,s}^{U,2} precisely yields B_{U}(m, n).

However, to obtain a proof for all m > n ≥ 0, we first notice that

B_{U}(m, n) = \frac{U_{m−n}}{U_{m+n}} \binom{m + n}{n}_{U} = \frac{U_{m−n}}{U_{n}} \binom{m + n − 1}{n − 1}_{U}.  (16)

So, if B_{U}(m, n) is a nonintegral rational number, there must exist a prime number p with respect to which B_{U}(m, n) has negative p-adic valuation. In particular, p divides both U_{m+n} and U_{n}. By Lemma 7, p ∤ Q. Thus, m = μp^{y}ρ and n = ηp^{z}ρ with p ∤ μη, where ρ is the rank of p. If y ≠ z, then ν_{p}(m−n) = ν_{p}(m+n) and so ν_{p}(U_{m−n}) = ν_{p}(U_{m+n}), which would contradict the negativity of ν_{p}(B_{U}(m, n)). Therefore, y = z and ν_{p}(U_{n}) = z+ν+δ_{z} ≤ ν_{p}(U_{m−n}), because m − n = (μ − η)p^{z}ρ. But, by the last expression in (16), this contradicts the negativity of the p-adic valuation of B_{U}(m, n).

3 The smallness of D_{U,a,k} when k ≤ 0

We provide two main theorems to assess the smallness of D_{U,a,k} when k ≤ 0 and U(P, Q) is regular. The first theorem treats sequences U with P^{2} ≠ 4Q, while the second treats the zero-discriminant case.

Our first theorem extends [5, Theorem 5.1], which treated the case a = 2, to all values of a ≥ 2.

Theorem 14. Suppose U(P, Q) is a regular Lucas sequence with P^{2} − 4Q ≠ 0. Assume a ≥ 2 and k ≥ 0 are fixed integers. Then there are at most finitely many integers n ≥ 1 such that U_{(a−1)n−k} divides \binom{an}{n}_{U}.

Proof. Since the case a = 2 corresponds to [5, Theorem 5.1], we may assume a ≥ 3. Put

M := max \{\frac{2k}{a − 2}, \frac{30 + k}{a − 1} \}.

Suppose n > M. Since n is larger than (30 + k)/(a − 1), the primitive divisor theorem [8, Theorem 1.4, p. 80] ensures that U_{(a−1)n−k} has a primitive prime divisor, say p. That is, ρ = ρ_{U}(p) = (a − 1)n − k. Thus, we find that

\frac{n}{ρ} = 0 + \frac{n}{(a − 1)n − k} ,
\frac{(a − 1)n}{ρ} = \frac{(a − 1)n}{(a − 1)n − k} = 1 + \frac{k}{(a − 1)n − k} .

Observe that n > 2k/(a−2) implies that (a−1)n−k > 0 and that (n+k)/((a−1)n−k) < 1. Thus, we see that n/((a−1)n−k) and k/((a−1)n−k) are the fractional parts of, respectively, n/ρ and (a − 1)n/ρ, and they add up to less than 1. Hence, in the base-p addition of n/ρ and (a − 1)n/ρ, there is no relevant carry as 0 + 1 < p. By Kummer’s rule for Lucasnomials, p does not divide \binom{an}{n}_{U}. Therefore, for all n > M, we find that U_{(a−1)n−k} does not divide \binom{an}{n}_{U}.

We now look at the case of regular Lucas sequences with null discriminant, which essentially corresponds to U_{n} = I_{n} and ordinary binomial coefficients. Theorem 15 below extends [22, Theorem 3] that covered the case a = 2.

Theorem 15. Suppose U(P, Q) is a regular Lucas sequence with P^{2} − 4Q = 0, i.e., U_{n} = n for all n ≥ 1, or U_{n} = (−1)^{n−1}n for all n ≥ 1. Assume a ≥ 2 and k ≥ 0 are fixed integers. Then the upper asymptotic density of the set of integers n ≥ 1 such that U_{(a−1)n−k} divides \binom{an}{n}_{U} is at most 1 − log 2.

Proof. It suffices to consider the case U = I. The proof we give is an adaptation of the proof of [22, Theorem 3]. Moreover, this adapted proof yields the same upper bound of 1 − log 2 for the upper asymptotic density of D_{I,a,k}, k ≤ 0, as the one obtained when a = 2. We begin by observing that if (a − 1)n − k has a prime factor p > \sqrt{2(a − 1)n} and p > ak, then ν_{p}((a − 1)n − k) > ν_{p}\binom{an}{n} so that n ∉ D_{I,a,−k}. Indeed, say (a − 1)n − k = cp. Then

c ≤ \frac{(a − 1)n}{p} < \frac{(a − 1)n}{\sqrt{2(a − 1)n}} = \frac{\sqrt{2(a − 1)n}}{2} < \frac{p}{2}.

Hence, (a − 1)n = cp + k with c < p/2 and k < p/a < p. Dividing c by a − 1, we write c = q(a−1)+r with 0 ≤ r ≤ a−2. Thus, n = qp+(rp+k)/(a−1). Noting that q ≤ c < p/2 and that

\frac{rp + k}{a − 1} + k = \frac{rp + ak}{a − 1} < \frac{(r + 1)p}{a − 1} ≤ p,

we find that no carry occurs in the base-p addition of (a−1)n and n. By the rule of Kummer, p ∤ \binom{an}{n}.

We now fix a sufficiently large z > 0 and estimate the number of n in (ak^{2}, z] that have a prime factor p > \sqrt{2(a − 1)z}. The lower bound ak^{2} for n is sufficient to imply p > ak. In the interval (ak^{2}, z], there are z/p + O(1) multiples of a prime p > \sqrt{2(a − 1)z}. As p > \sqrt{z} ≥ \sqrt{n}, no integer n may have two such prime factors. Hence, we find that

#\overline{D}_{I,a,−k}(z) ≥ ∑_{\sqrt{2(a−1)z}<p≤z} \frac{z}{p} + O(π(z)),

which using Mertens’ estimate ∑_{p≤z} \frac{1}{p} = log log z + M + o(1), where M is a small constant, leads to

#\overline{D}_{I,a,−k}(z) ≥ z( log log z − ( log \frac{1}{2} + log log(2(a − 1)z))) + o(z) ≥ z log 2 + o(z).

This readily implies the upper density of D_{I,a,−k} is bounded above by 1 − log 2.

We conjecture that the set D_{I,a,−k} is nevertheless always infinite. Given a ≥ 2, we only prove the infinitude of D_{I,a,−k} for infinitely many values of k all multiples of a − 1. For this, we extend an idea found in [30, Theorems 2.2 and 3.2] and also in [22], where the infinitely many integers n of the form pq +k, where p and q are both primes, p > k and 3p/2 < q < 2p, are shown to belong to D_{I,2,−k}.

Theorem 16. Let a ≥ 2 and m ≥ 0 be integers with gcd(a−1, m+1) = 1. Put k = m(a−1). Then the set D_{I,a,−k} is infinite. Furthermore, there is a positive constant c_{a} such that for all large enough z

#D_{I,a,−k}(z) ≥ \frac{c_{a}z}{log^{2} z} .

Proof. For a ≥ 2 and k = m(a − 1), we consider integers n of the form pq + m, where p and q are primes, p > k, and

q = p + d with \frac{p}{a} < d < \frac{p}{a − 1}.  (17)

Therefore, (a − 1)n − k = (a − 1)pq. Since n = qp + m = p^{2} + dp + m and (a − 1)n = (a − 1)p^{2} + (a − 1)dp + k, we see that the base-p addition of n and (a − 1)n produces at least one carry. Similarly, n = pq + m and (a − 1)n = (a − 1)pq + k = (a − 2)q^{2} + d_{q}q + k with q − p < d_{q} < q. Indeed, (a − 1)p = (a − 1)(q − d) > (a − 1)(q − p/(a − 1)) = (a − 2)q + (q − p) and (a − 1)p < (a − 1)q < (a − 2)q + q. Thus, the base-q addition of n and (a − 1)n produces at least one carry. Hence, pq divides \binom{an}{n}. From the lemmas of Section 6, one has that a − 1 divides \binom{an}{n} for almost all n. However, here, the integers n we consider have a special form.

So, in addition to p and q satisfying (17), we further impose the condition that p ≡ m+1 (mod (a − 1)^{2}) and q ≡ −1 (mod (a − 1)^{2}). Suppose r is a prime factor of a − 1 and a − 1 = r^{α}λ, where r and λ are coprime. Then p ≡ m + 1 (mod r^{2α}) and q ≡ −1 (mod r^{2α}). Thus, pq + m ≡ −1 (mod r^{2α}), which says that the r-ary expansion of n terminates with 2α digits all r − 1. Furthermore, the base-r expansion of (a − 1)n = r^{α} · λ(pq + m) ends with a nonzero digit followed by α zero digits. Therefore, the base-r addition of n and (a − 1)n generates a minimum of α carries. By the Kummer rule, r^{α} divides \binom{an}{n}. As it is true of all prime factors r of a − 1, a − 1 divides \binom{an}{n}. We conclude that for all such integers n, (a − 1)pq = (a − 1)n − k divides \binom{an}{n}.

Therefore, for all large enough real numbers z ≥ 1, we find that

#D_{I,a,−k}(z) ≥ ∑_{k<p≤\sqrt{z}/2} S_{p} ≥ S_{z} := ∑_{\sqrt{z}/3<p≤\sqrt{z}/2} S_{p},

where the sum

S_{p} := ∑_{\frac{a+1}{a} p<q< \frac{a}{a−1} p} 1, is taken over all primes q ≡ −1 (mod (a − 1)^{2}),

and the primes p satisfy p ≡ m + 1 (mod (a − 1)^{2}).

Using the prime number theorem for primes in arithmetic progressions and the fact that a/(a − 1) is larger than (a + 1)/a, each inner sum S_{p} in S_{z} is seen to be at least c_{1}\sqrt{z}/ log z, for some positive constant c_{1}. Indeed, if π(x; a, b) denotes the number of primes p ≤ x with p ≡ a (mod b), then, as z → ∞,

S_{p} = π(\frac{a}{a − 1}p; −1, (a − 1)^{2}) − π(\frac{a + 1}{a}p; −1, (a − 1)^{2})
= \frac{1}{φ((a − 1)^{2})} \frac{p}{log p}(\frac{a}{a − 1}(1 + o(1)) − \frac{a + 1}{a}(1 + o(1)))
∼ c\frac{p}{log p} ≥ \frac{2}{3}c\frac{\sqrt{z}}{log z} (1 + o(1)),

where c = (φ((a − 1)^{2})a(a − 1))^{−1}, φ is the Euler totient function and where, in the last inequality, we lavishly used p > \sqrt{z}/3 and log p ≤ log(\sqrt{z}/2).

Thus, as z tends to infinity, S_{z} is at least equivalent to

\frac{2}{3}c\frac{\sqrt{z}}{log z} ∑_{\frac{\sqrt{z}}{3} <p≤ \frac{\sqrt{z}}{2}} 1,

where the sum is over primes p ≡ m+1 (mod (a−1)^{2}). Now, using again the prime number theorem for primes in arithmetic progressions, we see that, as z tends to infinity,

∑_{\frac{\sqrt{z}}{3} <p≤ \frac{\sqrt{z}}{2}} 1 = π(\frac{\sqrt{z}}{2} ; m + 1, (a − 1)^{2}) − π(\frac{\sqrt{z}}{3} ; m + 1, (a − 1)^{2})

= \frac{1}{φ((a − 1)^{2})}(\frac{\sqrt{z}}{log z} (1 + o(1)) − \frac{2}{3} \frac{\sqrt{z}}{log z} (1 + o(1)))
= \frac{1}{3φ((a − 1)^{2})} \frac{\sqrt{z}}{log z} (1 + o(1)).

Hence, we obtain that, as z → ∞, #D_{I,a,−k}(z) is at least asymptotically equivalent to c_{a}z/(log z)^{2}, where

c_{a} = \frac{2}{9a(a − 1)(φ(a^{2} − 2a + 1))^{2}} .

To conclude the section, the bound of 1 − log 2 found in Theorem 15 being less than 1/3 amply demonstrates that the cleavage observed for ordinary binomial coefficients by Pomerance [22] between the cases k ≤ 0 and k ≥ 1 persists for all a ≥ 2 and, by Theorem 14, for all regular Lucas sequences U. However, a smaller upper asymptotic density for D_{I,2,0} was sought after by Sanna [25], who successfully brought it down from 1 − log 2 to 1 − log 2 − 0.05551. Recall that, as a consequence of [22, Theorem 4], the lower and upper densities of D_{I,2,k} are identical for all k ≤ 0, so we may as well assume k = 0. Actually, sequence \underline{A014847} in the OEIS [27] is an enumeration of the set D_{I,2,0}, and, in 2002, Cloitre observed on numerical evidence that it seemed that the quotient of the nth term of this sequence over n tended to a limit between 9 and 10. If that were true this would indicate a density between 1/10 and 1/9. According to the data in [30, Table 5], #D_{I,2,0}(2^{26}) = 8,225,813 which yields a quotient #D_{I,2,0}(x)/x of about 0.1226 for x = 2^{26}. The existence of a positive lower asymptotic density for D_{I,2,0} was conjectured by Pomerance [22, bottom of page 7]. At the West Coast Number Theory Conference of 2016, Pomerance asked whether this set has a positive lower density and whether it has a density, and, on that occasion, Stănică [21, Problem 016:04] conjectured that, for z ≥ 3700, we actually would have

\frac{z}{(log log z)^{3}} ≤ #D_{I,2,0}(z) ≤ \frac{z}{(log log z)^{2}} ,

implying, in particular, a zero density. Note that these bounds are quite a notch higher than the cz/ log^{2} z lower bound mentioned in [22, Section 6] or proven in Theorem 16.

4 Preliminaries to the study of the case k ≥ 1

Once a Lucas sequence U and the integers a ≥ 2 and k ≥ 1 have been fixed, we define, for every prime p, the set

A_{p} = A_{p}(U, a, k) := \{n ≥ 1 : ν_{p}(U_{(a−1)n+k}) > ν_{p}\binom{an}{n}_{U}\}.  (18)

Note that

\overline{D}_{U,a,k} = ⋃_{p} A_{p},  (19)

where the union is over all primes. We proceed to show that A_{p} is empty except, possibly, for the finitely many primes p of rank less than ak.

Lemma 17. Suppose U(P, Q) is a nondegenerate fundamental Lucas sequence, while a ≥ 2 and k ≥ 1 are fixed integers. Assume p ∤ Q is a prime of rank ≥ ak. Then, A_{p} is empty. That is, for all n ≥ 1,

ν_{p}\binom{an}{n}_{U} ≥ ν_{p}(U_{(a−1)n+k}).

Proof. Note that

\frac{1}{U_{(a−1)n+k}} \binom{an}{n}_{U} = \frac{∏_{j=1}^{k−1} U_{(a−1)n+j}}{∏_{i=0}^{k−1} U_{n−i}} \binom{an}{n − k}_{U}.

Thus, if our claim is wrong, then p must divide some factor, say U_{n−e}, 0 ≤ e ≤ k − 1, in the product ∏_{i=0}^{k−1} U_{n−i}. Thus, ρ divides n − e, where ρ is the rank of p in U. But p must also divide U_{(a−1)n+k}, that is, ρ divides (a − 1)n + k. As n ≡ e (mod ρ), we see that ρ divides (a−1)e+k. However, 0 < (a−1)e+k < ak and ρ ≥ ak. Hence, we have a contradiction.

We begin by putting to use Lemma 17 to obtain a complete description of a particular set D_{U,a,k} with a ≥ 3 and k ≥ 2. An example with a = 2 had already been explicitly computed in [5, Proposition 4.2].

Corollary 18. The set \overline{D}_{F,3,2} of integers n ≥ 1 such that F_{2n+2} does not divide \binom{3n}{n}_{F} is precisely the set

{2 · 3^{x} − 1; x ≥ 0}.

Proof. By Lemma 17, \overline{D}_{F,3,2} is the union of the A_{p} over all primes p of rank less than 6. Only the primes 2, 3 and 5 have rank less than 6 in the Fibonacci sequence. Let p denote one of the primes 2, 3 or 5, and ρ ≥ 3 denote its rank. For an integer n ≥ 1 to be in A_{p}, we need p to divide F_{2n+2}. Thus, 2n + 2 is of the form λρp^{x} with x ≥ 0 and λ ≥ 1 two integers, where we assume λ prime to p. Hence, we find that

\begin{aligned}\frac{2n}{ρ} & = (λ − 1)p^{x} + p^{x} − 1 + \frac{ρ − 2}{ρ}, \\ \frac{n}{ρ} & = ⌊\frac{n}{ρ}⌋ + \{\frac{n}{ρ}\}. \end{aligned}  (20)

Because ρ > 2, we see that (ρ − 2)/ρ is the fractional part of 2n/ρ. Moreover, ρ | 2n + 2 implies ρ ∤ n. Thus, \{\frac{n}{ρ}\} ≥ \frac{1}{ρ}.

If \{\frac{n}{ρ}\} ≥ \frac{2}{ρ}, then there is a carry across the radix point and, due to the x consecutive p − 1 digits in the p-ary expansion of p^{x} − 1, this carry over the radix point guarantees at least x further carries left of that point in the base-p addition of 2n/ρ to n/ρ. Thus, by the Kummer rule for Lucasnomials, the p-adic valuation of \binom{3n}{n}_{F} is at least x + 1 + δ_{x}, which is ν_{p}(F_{2n+2}). We conclude that if \{\frac{n}{ρ}\} ≥ \frac{2}{ρ}, then n ∉ A_{p}.

Hence, \{\frac{n}{ρ}\} = \frac{1}{ρ}, i.e., an n ∈ A_{p} must be of the form qρ+1. In particular, 2n+2 = 2qρ+4 so that ρ | 4, and, as F_{2} = 1, ρ = 4. But F_{4} = 3. Therefore, A_{2} and A_{5} are empty and we now assume p = 3. Since n = 4q + 1, equations (20) become

\begin{aligned}\frac{2n}{ρ} & = 2q + \frac{1}{2}, \\ \frac{n}{ρ} & = q + \frac{1}{4}. \end{aligned}  (21)

Since 2n + 2 = λ · 4 · 3^{x} = 4(2q + 1), we see that 2q + 1 = (3j + i)3^{x}, where we set λ = 3j + i with i = 1 or 2. Therefore,

\begin{aligned}2q & = (3j + i − 1) · 3^{x} + (22 ⋯ 2)_{3}, (x 2’s) \\ q & = \frac{3j + i − 1}{2} · 3^{x} + (11 ⋯ 1)_{3}, (x 1’s) \end{aligned}  (22)

where (dd ⋯ d)_{3} with x d’s stands for d(3^{x−1} + 3^{x−2} + ⋯ + 1). If the integer ℓ = (3j + i − 1)/2 ≠ 0, then we obtain from (22) that the base-3 addition of 2q and q produces at least ν_{3}(F_{2n+2}) = x + 1 carries. Indeed, as easily seen, and as shown in [3, Lemma 2.2], adding ℓ ≥ 1 and (p − 1)ℓ in base p, p a prime, yields at least one carry. However, if 3j + i − 1 = 0, the base-3 addition “ 2q + q ” only produces x carries so that n belongs to A_{3}. But then 2q + 1 = 3^{x} and n = 2 · 3^{x} − 1. This proves the corollary.

Remark 19. The proof of Corollary 18 shows that \frac{3}{F_{2n+2}} \binom{3n}{n}_{F} is an integer for all n ≥ 1. We also note that D_{F,3,2} has asymptotic density one in the positive integers, but that it misses infinitely many integers. Do these facts hold in general?

We will provide answers in due course, but we begin with the latter fact, which is that \overline{D}_{F,3,2} is infinite.

The only regular Lucas sequences U(P, Q) with P > 0 for which there exists a k ≥ 2 such that \overline{D}_{U,2,k} is finite — it is in fact empty — corresponds to (P, Q) = (1, 2) [5, Theorem 3.5]. We want to find out whether, when a ≥ 3, such examples occur. We say a triple (U, a, k), with k ≥ 2, is a Catalan-like triple if and only if, for all natural numbers n,

\frac{1}{U_{(a−1)n+k}} \binom{an}{n}_{U} is an integer.

We proceed with a lemma which states conditions sufficient to guarantee the infinitude of A_{p}(U, a, k). It gives a minimal infinite subset of A_{p} when p satisfies some rank condition. Actually, the set A_{3} in Corollary 18 is equal to that minimal subset.

Lemma 20. Let U(P, Q) be a nondegenerate fundamental Lucas sequence and a ≥ 2, k ≥ 2 be integers. Assume there exists a prime p ∤ Q of rank ρ in U, where

ρ = k + ℓ(a − 1),

for some ℓ, 1 ≤ ℓ ≤ k − 1. Then A_{p}(U, a, k) is infinite and contains all integers n of the form

\frac{ρp^{x} − k}{a − 1} , for all x divisible by φ(a − 1),

where φ denotes the Euler totient function.

Proof. As ρ ≥ 2 + (a − 1) = a + 1 and p ≥ ρ − 1, we have p ≥ a. Hence, p ∤ a − 1. Thus, the condition φ(a − 1) divides x guarantees that p^{x} − 1 is divisible by a − 1. Also, because ρ ≡ k (mod a − 1), for each x ≥ 0 divisible by φ(a − 1), there is a unique n = n_{x} ≥ 1 such that

(a − 1)n + k = ρp^{x}.

Therefore, for these integers n, we find that

\begin{aligned}\frac{(a − 1)n}{ρ} & = p^{x} − 1 + \frac{ρ − k}{ρ} , \\ \frac{n}{ρ} & = \frac{p^{x} − 1}{a − 1} + \frac{ℓ}{ρ}, \end{aligned}  (23)

where we see that (ρ − k)/ρ and ℓ/ρ are the fractional parts of, respectively, (a − 1)n/ρ and n/ρ. The sum of these two fractional parts is less than 1 since ρ−(k−ℓ) < ρ. By the Kummer rule for Lucasnomials, we see that ν_{p}\binom{an}{n}_{U} ≤ x + δ_{x}. (In fact, it is x + δ_{x} since, if x > 0, the integer (p^{x} − 1)/(a − 1) is prime to p and the base-p addition of (a − 1)n/ρ and n/ρ produces exactly x carries left of the radix point.) But, ν_{p}(U_{(a−1)n+k}) = x + ν + δ_{x} > x + δ_{x}.

We add some power to Lemma 20 by observing that if U_{k} possesses a primitive prime divisor p prime to Q, then the equations in (23) remain valid. Thus, if p ∤ a − 1, then, again, for all integers n of the form k(p^{x} − 1)/(a − 1), x a multiple of φ(a − 1), U_{(a−1)n+k} does not divide \binom{an}{n}_{U}. However, the condition p ∤ a − 1 is no longer necessarily true. We state this observation as an additional lemma.

Lemma 21. Let U(P, Q) be a nondegenerate fundamental Lucas sequence and a ≥ 2, k ≥ 2 be integers. Assume there exists a prime p ∤ Q(a − 1) of rank k. Then A_{p}(U, a, k) is an infinite set.

One can see that the hypotheses of Lemma 20 are the weakest when k = 2. Indeed, for k = 2, we need a prime of rank a + 1 to assert that A_{p} is infinite. Some lemmas will help reach a conclusion whenever there are no primes of rank a + 1. Inspired by the proof of Corollary 18, we establish a first supplementary lemma for the case k = 2.

Lemma 22. Let U(P, Q) be a nondegenerate fundamental Lucas sequence and a ≥ 2 be an integer. If p ∤ Q is a prime of rank ρ, with ρ > 2 and ρ ∤ a + 1, then A_{p}(U, a, 2) is empty.

Proof. The argument is close to that of Corollary 18 so we abbreviate it. If n ∈ A_{p}, then there is an x ≥ 0 and a λ ≥ 1 not divisible by p such that (a − 1)n + 2 = λρp^{x}. Hence,

\frac{(a − 1)n}{ρ} = (λ − 1)p^{x} + p^{x} − 1 + \frac{ρ − 2}{ρ}.

In the base-p addition of n/ρ to (a − 1)n/ρ a carry across the radix point generates at least x carries left of that point. As a consequence ν_{p}\binom{an}{n}_{U} ≥ ν_{p}(U_{(a−1)n+2}) and n ∉ A_{p}. Since n ∈ A_{p}, either ρ | n or n = qρ + 1 for some integer q. As ρ | (a − 1)n + 2, if ρ | n, then ρ = 2. If n = qρ + 1, then

(a − 1)n + 2 = (a − 1)qρ + (a + 1) = λρp^{x},

so that ρ | a + 1.

This, together with Lemma 7, yields the immediate corollary.

Corollary 23. With the hypotheses of Lemma 22 and k = 2, if P = 1 and U_{a+1} = ±1, then \overline{D}_{U,a,2} is empty. On the other hand, if |U_{a+1}| > 1 and ρ(p) = a + 1, then, by Lemma 20, \overline{D}_{U,a,2} is infinite. If a and P are even and Q is odd, then \overline{D}_{U,a,2} is infinite by Lemma 21.

Here is a theorem, which under fairly broad hypotheses, tells us that A_{p} cannot be a finite nonempty set.

Theorem 24. Let U(P, Q) be a NFL-sequence and a ≥ 2, k ≥ 1 be integers. Let p ∤ Q(a−1) be a prime of rank at least k. Then A_{p} is either empty or infinite.

Proof. Denoting as usual the rank of p by ρ, suppose A_{p} is not empty. Then there is an integer n_{0} ≥ 1 in A_{p} and integers λ ≥ 1, p ∤ λ, x_{0} ≥ 0 such that

(a − 1)n_{0} + k = λρp^{x_{0}}.  (24)

In particular, ν_{p}(U_{(a−1)n_{0}+k}) = x_{0} + ν + δ_{x_{0}}.

As n_{0} ∈ A_{p} and (a − 1)n_{0}/ρ = λp^{x_{0}} − 1 + (ρ − k)/ρ, it must be, by the Kummer rule for Lucasnomials, that

\{\frac{n_{0}}{ρ} \} + \frac{ρ − k}{ρ} < 1.

We are about to show that, with the same integer λ which appears in (24), there are infinitely many integers n ≥ 1 such that (a−1)n+k = λρp^{x}, for some x ≥ 0, which satisfy \{\frac{n}{ρ}\} = \{\frac{n_{0}}{ρ} \}. By the above analysis for n_{0}, this implies all such n are in A_{p}. Now (a − 1)n + k = λρp^{x} if and only if

(a − 1)(n − n_{0}) = λρ(p^{x} − p^{x_{0}})  (25)

As p ∤ a − 1, p^{x} ≡ p^{x_{0}} (mod a − 1) occurs for all x satisfying x ≡ x_{0} (mod h), where h is the multiplicative order of p (mod a − 1). For each s ≥ 0, put x_{s} = x_{0} + sh and define t_{s} by p^{x_{s}} = p^{x_{0}} + t_{s}(a − 1). Note that (t_{s})_{s≥0} is an increasing sequence of integers. Putting p^{x_{s}} −p^{x_{0}} = t_{s}(a−1) into (25) we find that n = n_{s} = n_{0}+t_{s}λρ satisfies (25) with the fractional part of n/ρ equal to that of n_{0}/ρ.

Theorem 24 will come in handy in the next section, but mostly in the guise of the next corollary.

Corollary 25. Suppose U(P, Q) is regular, a ≥ 2 and k = 2. Let p ∤ a − 1 be a prime. If p | U_{a+1}, then A_{p}(U, a, 2) is infinite.

Proof. By (10), if p | U_{a+1}, then p ∤ U_{a}. Hence, ν_{p}(U_{(a−1)+2}) > ν_{p}\binom{a}{1}_{U} and 1 ∈ A_{p}(U, a, 2). By Lemma 7, p ∤ Q. So by Theorem 24, A_{p} is infinite.

5 Chasing all Catalan-like triples (U, a, k), k ≥ 2, and a proof that \overline{D}_{U,a,k} is otherwise infinite

We first study the case k ≥ 3.

Proposition 26. Let a ≥ 3 and k ≥ 3. Then for all nonzero-discriminant regular Lucas sequences U(P, Q), there are infinitely many integers n ≥ 1 for which U_{(a−1)n+k} does not divide \binom{an}{n}_{U}.

Proof. Suppose first k ≥ 4. To have a chance at finding a counterexample to our proposition, we need, by Lemma 20, to find regular sequences U that are n-defective for at least three indices n in arithmetic progression, namely at least at k + a − 1, k + 2(a − 1) and k + 3(a − 1) knowing that k + a − 1 ≥ 6. Inspecting Table A of Section 7, we discover only two such instances, namely the sequence U(1, 2) which is n-defective at 6, 12 and 18 and also at n = 8, 13 and 18. In the case of 6, 12 and 18, the common difference is 6. So a − 1 = 6 and k + a − 1 = 6. This yields k = 0, a contradiction. In the second case, as U(1, 2) is not 23-defective, there is no counter-example if k ≥ 5. So assume k = 4. Solving k + a − 1 = 8 for a − 1 yields a − 1 = 4. However, as the three indices n = 8, 13 and 18 are 5 apart, we would have needed a − 1 = 5.

So we now assume k = 3. Using Table A, we now search for sequences that are both (a+2) and (2a+1)-defective. For a = 3, again the sequence U(1, 2) is both 5 and 7-defective. But U_{7} has the primitive prime divisor 7, which was discarded from Table A because 7 divides the discriminant P^{2} − 4Q. But that p divides Δ does not invalidate Lemma 20. Examining all values of a, 4 ≤ a ≤ 14, we only find one candidate sequence when a = 6, i.e., again U(1, 2), which is 8 and 13-defective as seen earlier. To show that \overline{D}_{U,6,3}, with U = U(1, 2), is infinite, it suffices to prove that the set A_{3}(U, 6, 3), defined in (18), is infinite. Note that 3 ∤ a − 1. Moreover, U_{6} = \binom{6}{1}_{U} = 5 is not divisible by U_{(a−1)·1+3} = U_{8} = −3. That is, 1 ∈ A_{3}. By Theorem 24, A_{3} is infinite.

We now study the case k = 2.

Theorem 27. The four triples (U(1, 2), a, 2), for a = 4 and a = 12, (U(1, 3), 4, 2) and (U(1, 5), 6, 2) are all four Catalan-like triples. That is,

\frac{1}{U_{(a−1)n+k}} \binom{an}{n}_{U},

is integral for all natural numbers n.

Proof. The first few terms of the most frequently defective Lucas sequence U(1, 2) are

0, 1, 1, −1, −3, −1, 5, 7, −3, −17, −11, 23, 45, −1, −91, −89, 93, 271 and 85.

The first terms up to U_{7} are

\begin{cases}0, 1, 1, −2, −5, 1, 16, 13, & for U(1, 3); \\ 0, 1, 1, −4, −9, 11, 56, 1, & for U(1, 5). \end{cases}

For U(1, 2) and U(1, 3), we see that U_{5} = ±1. Therefore, by Corollary 23, \overline{D}_{U,4,2} is empty. For U(1, 5), U_{7} = 1 so \overline{D}_{U,6,2} is empty by the same Corollary 23. Similarly, for U(1, 2), we find that U_{13} = −1 so \overline{D}_{U,12,2} is empty.

Proposition 28. Let U(P, Q) be a nonzero-discriminant regular Lucas sequence, a ≥ 3 be an integer and k = 2. Then, except for the four exceptions of Theorem 27, there exist infinitely many integers n ≥ 1 for which U_{(a−1)n+k} does not divide \binom{an}{n}_{U}.

Proof. We display the terms U_{2}, U_{3}, U_{4} and U_{6} of U(P, Q) as polynomials in P and Q:

U_{2} = P , U_{3} = P^{2} − Q, U_{4} = P (P^{2} − 2Q), U_{6} = P (P^{2} − Q)(P^{2} − 3Q).

We proceed case by case depending on the value of a. By Lemma 20, the only values of a to consider are those for which there is some U with U_{a+1} free of primitive prime divisors.

Case a = 3. If U_{4} has a primitive prime divisor, then, as a + 1 = 4, we obtain that \overline{D}_{U,3,2} is infinite as a consequence of Lemma 20. (Note that the hypothesis p ∤ Q holds by Lemma 7.) If U_{4} has no p.p.d., then P^{2} − 2Q = ±1. So P is odd ≥ 1. If P = 1, then Q = 1, so that P^{2} − Q = U_{3} = 0, which contradicts the nondegeneracy of U. Hence, P is odd > 1 and U_{2} = U_{k} admits a p.p.d. p ≥ 3. As p ∤ a − 1 = 2, we reach the result sought by applying Lemma 21.

Case a = 4. Since a + 1 = 5 we need only consider the seven sequences listed as 5-defective in Table A for, by Lemma 20, they are the only ones for which \overline{D}_{U,4,2} could be finite. But of these seven sequences three have a discriminant divisible by 5. Thus, 5 is a primitive divisor of U_{a+1} and we may discard them by Lemma 20. Two others are U(1, 2) and U(1, 3) for which, as seen in Theorem 27, \overline{D}_{U,4,2} is empty. The remaining two are U(12, 55) and U(12, 377) for which p = 2 has rank 2 with 2 ∤ a − 1 so that Lemma 21 ensures our claim holds.

Case a = 5. This might be the most intricate case because there are four infinite families of regular Lucas sequences that are (a + 1)-defective, i.e., 6-defective, according to Table A. However, for two of these four infinite families 3 | P. Hence, p = 3 has rank k and p ∤ a − 1 so that, by Lemma 21, \overline{D}_{U,5,2} is infinite. The two remaining families are 1. (P, Q) = (P, (P^{2} − 1)/3) for all P > 3, 3 ∤ P, and 2. (P, Q) = (P, (P^{2} − (−2)^{i})/3), where i ≥ 1, P ≡ ±1 (mod 6), (P, i) ≠ (1, 1). In both families, if P has an odd prime divisor p, then, as p ∤ a − 1, \overline{D}_{U,5,2} is infinite by Lemma 21. If not, then for the family 1. P = 2^{α} for some α ≥ 2. Thus, Q = (P^{2} − 1)/3 is odd. Moreover, P^{2} − 3Q = 1 and 4^{α} − 3Q = 1 implies that Q ≡ 1 (mod 4). Thus, U_{3} = P^{2} − Q = (2P^{2} + 1)/3 is ≥ 11 and ≡ 3 (mod 4). Hence, there exists a prime p ≥ 3, p ≡ 3 (mod 4) of rank 3. Thus, we obtain an infinite sequence of integers (n_{x})_{x≥1} defined by 4n_{x} + 2 = 2 · 3 · p^{x}. Putting n = n_{x} we see that 4n/3 = 2p^{x} − 1 + 1/3. Noting that 2p^{x} − 1 = 4q + 1 for some integer q, we find that n/3 = q + 1/4 + 1/12 = q + 1/3. Therefore, the base-p addition of (a − 1)n/ρ and n/ρ generates exactly x carries left of the radix point and none across that point. Therefore, n_{x} ∈ A_{p} for all x ≥ 1 and \overline{D}_{U,5,2} is infinite. Now for the second family 2., if U_{2} does not have an odd p.p.d., then P = 1. Thus, as (P, i) ≠ (1, 1), we have i ≥ 2 and, putting j = i − 2, we find that U_{3} = 1−Q = (2+(−2)^{j+2})/3, j ≥ 0, is divisible by 2. We prove that A_{2} is infinite. For each λ ≥ 1 odd, ν_{2}(U_{6λ}) = j + 3. Indeed, ν_{2}(U_{6λ}) = ν_{2}(U_{6}). But U_{6} = (1 − Q)(1 − 3Q) and 1 − Q = (2 + (−2)^{j+2})/3 has 2-adic valuation 1, whereas 1 − 3Q = (−2)^{j+2}.

For each t ≥ 1 define the odd integer λ = (2 · 8^{t} + 5)/7, which may be written in terms of the base-2 representation of λ − 1 as

λ = (λ − 1) + 1 = (\overline{010}^{t})_{2} + 1,

where \overline{010}^{t} = 010 010 ⋯ 010 (the string 010 being repeated t times). To each such λ, corresponds a unique integer n ≥ 1 such that 4n + 2 = 6λ. Since 4n/3 = 2λ − 1 + 1/3 = (\overline{100}^{t})_{2} + 1 + 1/3 and, thus, n/3 = (\overline{001}^{t})_{2} + 1/4 + 1/12 = (\overline{001}^{t})_{2} + 1/3, we see that the base-2 addition of (a − 1)n/ρ and n/ρ creates a single carry from position 1 to position 2 left of the radix point. Therefore, ν_{2}\binom{5n}{n}_{U} = 1 + δ = j + 2, whereas ν_{2}(U_{6λ}) = j + 3. Thus, A_{2} is infinite.

The only values of a left for consideration are: 6, 7, 9, 11, 12, 17 and 29. For the other values, there are no (a + 1)-defective sequences U.

Case a = 6. The only 7-defective sequences according to Table A, Section 7, are (P, Q) = (1, 2) and (1, 5). However, 7 is a primitive divisor of U_{7} = U_{a+1} for the first sequence since 7 | Δ. So A_{7} is infinite by Lemma 20. The second sequence U has parameters (P, Q) = (1, 5) and (U, 6, 2) was identified as a Catalan-like triple in Theorem 27.

Case a = 7. There are only two 8-defective regular Lucas sequences U(2, 7) and U(1, 2). For (P, Q) = (2, 7), U_{2} = 2 and U_{8} = −40 so that, by Lemma 22, we need only consider A_{2} and A_{5}. Since 5 ∤ a − 1, but 5 | U_{a+1}, A_{5} is infinite by Corollary 25. (In fact, A_{2} is infinite as well. Indeed, for each even x ≥ 2, there is an n ≥ 1 which solves the equation 6n + 2 = 2 · 2^{x}. Since for all such x and n we find that 6n/2 = 2^{x} − 1 is integral, the base-2 addition of (a − 1)n/ρ and n/ρ does not produce a carry across the radix point so that ν_{2}\binom{7n}{n}_{U} ≤ x < 1 + x = ν_{2}(U_{6n+2}).) For (P, Q) = (1, 2), we show that A_{3} contains {1+4·3^{t}, t ≥ 0}. Indeed, ρ(3) = 4 and, for n = 1+4·3^{t}, we see that 6n/4 = 2·3^{t+1} +1+1/2 while n/4 = 3^{t} + 1/4. Their base-3 addition raises no carry at all. So 3 ∤ \binom{7n}{n}_{U}. However, 4 divides 6n + 2 implies that ν_{3}(U_{6n+2}) ≥ 1.

Case a = 9. As usual if U_{a+1} has a p.p.d. then \overline{D}_{U,a,2} is infinite by Lemma 20. So we look at Table A for the 10-defective sequences. There are three: (P, Q) = (2, 3), (5, 7) and (5, 18). For the last two P = 5 so the prime 5 has rank 2 and does not divide a − 1. Hence, by Lemma 21, A_{5} is infinite. For U(2, 3), U_{5} = −11. So 11 | U_{a+1}, but 11 ∤ a − 1. Hence, A_{11} is infinite by Corollary 25.

Case a = 11. There are six 12-defective sequences corresponding to (P, Q) = (1, −1), (1, 2), (1, 3), (1, 4), (1, 5) and (2, 15). For (1, −1), (1, 2), (1, 4) and (1, 5), 3 ∤ Q. So, as ρ(3) is either 2, 3 or 4, we see that 3 | U_{12}. As 3 ∤ a − 1, we conclude that A_{3} is infinite by Corollary 25. For U(1, 3), U_{3} = −2 and U_{6} = 16. Although 2 | a − 1, we claim that A_{2} contains

\{\frac{3 · 2^{4t+1} − 1}{5} ; t ≥ 0\}.

Indeed, if n = (3 · 2^{4t+1} − 1)/5, then 10n + 2 = 3 · 2^{4t+2}. Thus, ν_{2}(U_{10n+2}) = (4t + 2) + 1 + δ = 4t + 5. But 10n/3 = 2^{4t+2} − 1 + 1/3, while n/3 = (2^{4t+2} − 1)/10 + 1/30 ≡ 3/10 + 1/30 = 1/3 (mod 1). Therefore, by the Kummer rule for Lucasnomials, ν_{2}\binom{11n}{n}_{U} ≤ (4t+2)+δ = 4t+4 < ν_{2}(U_{10n+2}). For U(2, 15), U_{3} = −11. Hence, 11 | U_{12} and 11 ∤ a − 1, so that A_{11} is infinite by Corollary 25.

Case a = 12. The only 13-defective sequence is U(1, 2). We saw in Theorem 27 that (U(1, 2), 12, 2) is a Catalan-like triple.

Cases a = 17 and a = 29. The sequence U(1, 2) is the only 18-defective and the only 30-defective regular Lucas sequence. As U_{6} = 5, we see that 5 | U_{18} and 5 | U_{30}. Since 5 ∤ 17 − 1 and 5 ∤ 29 − 1, we conclude, with the help of Corollary 25, that A_{5}(U, 17, 2) and A_{5}(U, 29, 2) are both infinite sets.

For the sake of completeness, we now address the case of zero-discriminant regular Lucas sequences U, i.e., of U_{n} = I_{n} or U_{n} = (−1)^{n−1}I_{n}. Clearly it suffices to study the case of U = I.

Proposition 29. The sets \overline{D}(I, a, k) are infinite for all a ≥ 2 and all k ≥ 2.

Proof. Let a and k be integers exceeding 1. Let g = gcd(a − 1, k). The argument is split into three complementary cases.

Case 1. Suppose g > 1. Let p be a prime factor of g and put n = p^{x} for some x ≥ 0. Then the p-ary expansion of (a − 1)n ends with x + 1 zeros, while n has a single digit 1 at position x. Thus, there is no carry in the base-p addition of (a − 1)n and n. By Kummer’s rule, p does not divide \binom{an}{n}. But p divides (a − 1)n + k. So (a − 1)n + k does not divide \binom{an}{n}. Therefore, for all x ≥ 0, p^{x} belongs to \overline{D}(I, a, k).

Case 2. Assume g = 1 and k ∤ a. Then there is a prime p such that p^{κ}||k, p^{u}||a for some κ > u. We write a = p^{u}a′. Put n = p^{x} for some x > κ. Then

(a − 1)n = an − n = a′p^{x+u} − p^{x} = (a′ − 1)p^{x+u} + (p − 1)p^{x+u−1} + ⋯ + (p − 1)p^{x}
n = p^{x}.

Their base-p addition creates exactly u carries since the carry into position x + u does not propagate any further to the left. Indeed, p ∤ a′ ⟹ a′ − 1 ≢ p − 1 (mod p). By the rule of Kummer, p^{u}||\binom{an}{n}. However, p^{κ} divides (a − 1)n + k. Therefore, all p^{x}, x > κ, are in \overline{D}(I, a, k).

Case 3. Assume a = kℓ for some ℓ ≥ 1. Thus, g = 1. Let p be a prime factor of k and write k = p^{κ}k′, p ∤ k′. Let h be the multiplicative order of p modulo a − 1. Let t > 0 be an integer large enough so that p^{x} > k, where x = κ + ht. Then k′p^{x} − k = k(p^{ht} − 1) is a multiple of a − 1. Define n = n_{t} as (a − 1)n = k′p^{x} − k. The p-ary expansion of k′p^{x} − k has the form

(k′ − 1)p^{x} + d_{x−1}p^{x−1} + ⋯ + d_{κ}p^{κ},

where the d_{i}’s are p-ary digits. If d_{x} is the (x+1)-st p-ary digit of k′p^{x} −k, i.e., if (k′ −1)p^{x} ≡ d_{x}p^{x} (mod p^{x+1}), then d_{x} ≠ p − 1, because d_{x} = p − 1 would imply that p | k′. Moreover, (a − 1)n < k′p^{x} = kp^{x−κ} ≤ kp^{x−1} implies that

n < \frac{k}{a − 1}p^{x−1} ≤ \frac{k}{k − 1}p^{x−1} ≤ 2p^{x−1} ≤ p^{x}.

The p-ary expansion of n has at most x significant digits. Thus, the base-p addition of n and (a − 1)n generates at the most x − κ carries since the least significant κ digits of (a − 1)n are all zero. Thus,

ν_{p}\binom{an}{n} ≤ x − κ < x = ν_{p}((a − 1)n + k).

Hence, n_{t} ∈ A_{p}, for all t large enough.

Gathering together Propositions 26, 28 and 29, the theorems of Sections 2 and 3 and [5, Theorem 3.5], we state a general theorem.

Theorem 30. Suppose U(P, Q) is a regular Lucas sequence and a ≥ 2 and k are integers. Then there are infinitely many natural numbers n such that

U_{(a−1)n+k} does not divide \binom{an}{n}_{U},

unless either k = 1 or, k = 2, P = ±1 and (Q, a) is one of the five ordered pairs (2, 2), (2, 4), (2, 12), (3, 4) or (5, 6), in which cases

U_{(a−1)n+k} divides \binom{an}{n}_{U}, for all n ≥ 1.

We derive a couple of corollaries, one for the sequence U(1, 2) which stands out conspicuously, as had already been noted in [5, Corollary 3.6 and the subsequent remark], and one for the Fibonacci sequence.

Corollary 31. For the two Lucas sequences U(±1, 2) = (U_{n})_{n≥0}, we see that for all n ≥ 1

U_{n+1}U_{n+2} | \binom{2n}{n}_{U}, U_{3n+1}U_{3n+2} | \binom{3n}{n}_{U} and U_{11n+1}U_{11n+2} | \binom{12n}{n}_{U}.

The next corollary is an extension of [5, Proposition 3.2]. It would also hold if we replaced F by I. Indeed, Fibonomial Fuss-Catalan numbers bear the same singular status as Fuss-Catalan numbers do.

Corollary 32. Let a ≥ 2 and k be integers. Let F denote the Fibonacci sequence. Then there are infinitely many n ≥ 1 for which the numbers

\frac{1}{F_{(a−1)n+k}} \binom{an}{n}_{F}

are not integers, unless k = 1 when they are integers for all a ≥ 2 and n ≥ 1.

6 The density of D_{U,a,k} when k ≥ 1

Our objective is to show that D_{U,a,k} has asymptotic density 1 in the set of positive integers whenever k ≥ 1. Here is an indicative roadmap of the route we intend to follow. As in [5, Section 4], where we proved the case a = 2, we proceed by showing that the complementary set of D_{U,a,k} in the positive integers, \overline{D}_{U,a,k}, has asymptotic density 0. By Lemma 17, there are only at most finitely many primes p for which A_{p} is not empty. Thus, by (19), we only need to prove that A_{p} is of density zero for each prime p. We will establish an estimate for the number of words of length ℓ over an alphabet of p letters which miss a given block of b consecutive identical letters, as ℓ tends to infinity. This result is then converted into an upper bound for the number of integers n ≤ z for which the base-p addition of n/ρ and (a − 1)n/ρ generates less than a given number of carries. This upper bound turns out to be o(z), as z tends to infinity. Integers n in A_{p} may be viewed as generating few carries in the addition of n/ρ and (a − 1)n/ρ, at least fewer than the p-adic valuation of U_{(a−1)n+k}. We split A_{p} into the union of all A_{p}^{x}, where A_{p}^{x} is the subset of A_{p} of integers n for which x is the exact exponent of p in the equation (a − 1)n + k = λρp^{x}, p ∤ λ. For x smaller than a bound u, integers in A_{p} are easily seen to generate less than a_{p} carries in the base-p addition of n/ρ and (a − 1)n/ρ, where a_{p} is a fixed bound that depends on p and u. So there are no more than o(z) such integers as z tends to infinity. For x > u, we will see that the form of (a − 1)n/ρ generally induces a minimum of x − u carries right of position x and left of the radix point. Thus, no matter how large x we only need a bounded fixed number of carries left of position x to guarantee n is not A_{p}. This gives the desired conclusion.

It is well-known [16, Theorem 143, p. 120] that almost all natural numbers, when expressed in any scale, contain every possible sequence of digits. But we need to quantify somewhat this ‘almost all’ statement. The editor-in-chief mentioned the work of Guibas and Odlyzko ([15] and their further papers) whose general results may well imply our lemma.

Lemma 33. Let p ≥ 2 and b ≥ 1 be integers. Let x_{n} be the number of strings of p-ary digits of length n which do not contain a block of b consecutive digits all equal to p − 1. Then, as n tends to infinity,

x_{n} ∼ c · ø^{n}p^{n},

for some ø ∈ (0, 1) and some positive constant c.

Proof. The sequence (x_{n}) forms a linear recurrent sequence with annihilating polynomial

P (X) = X^{b} − (p − 1)X^{b−1} − (p − 1)X^{b−2} − ⋯ − (p − 1).  (26)

To see that (x_{n}) is linear recurrent, we only consider the case b = 3 as an example, but the reasoning may be carried out in all generality. We say that a string is admissible if it does not contain a block of three consecutive digits equal to p − 1. Define y_{n} as the number of length-n admissible strings that end with two consecutive p − 1 digits, z_{n} as the number of length-n admissible strings ending with only one p − 1 digit and t_{n} for those ending with a digit at most p − 2. Then we readily see that for n ≥ 2, z_{n} = t_{n−1} and t_{n} = (p − 1)x_{n−1}. Consequently we see that for n ≥ 3

x_{n+1} = (p − 1)y_{n} + p(z_{n} + t_{n})
= (p − 1)(y_{n} + z_{n} + t_{n}) + (t_{n} + t_{n−1})
= (p − 1)x_{n} + (p − 1)x_{n−1} + (p − 1)x_{n−2}.

Noting that x_{i} = p^{i} for 0 ≤ i ≤ b − 1 and x_{b} = p^{b} − 1, we see that the polynomial P in (26) must be the characteristic polynomial of (x_{n}), i.e., its minimal annihilating polynomial. Indeed suppose to the contrary that there is an 1 ≤ s < b and constants a_{i}, 1 ≤ i ≤ s, such that x_{n+s} = ∑_{i=1}^{s} a_{i}x_{n+s−i} for all n ≥ 0. Then

x_{b} = ∑_{i=1}^{s} a_{i}x_{b−i} = p ∑_{i=1}^{s} a_{i}x_{b−i−1} = px_{b−1} = p^{b},

contradicting the fact that x_{b} = p^{b} − 1.

Using for instance [4, Lemma 3], we know the polynomial P in (26) has a unique simple dominant real zero α > 1. Because P is the characteristic polynomial of (x_{n}), the closedform expression of x_{n} must contain a nonzero term in α^{n}. Therefore, x_{n} ∼ cα^{n}, as n tends to infinity, where c is some positive constant that depends only on p and b. Note that P (x) is increasing for x > p. Indeed, the derivative P′ is positive, since for x > p

P′(x) = bx^{b−1} − (p − 1)((b − 1)x^{b−2} + (b − 2)x^{b−3} + ⋯ + 1)
> bx^{b−1} − (p − 1)(b − 1)(x^{b−2} + x^{b−3} + ⋯ + 1)
= bx^{b−1} − (p − 1)(b − 1)\frac{x^{b−1} − 1}{x − 1}
> bx^{b−1} − (b − 1)(x^{b−1} − 1) = x^{b−1} + b − 1 > 0.

Since P (p) = 1 > 0, the polynomial P has no zero larger than p. Thus, α < p. Our claim holds with ø = α/p.

Lemma 34. Let p be a prime, ρ ≥ 1, a ≥ 2 and a_{p} ≥ 1 be integers. Then the set C_{<a_{p}} of integers n such that the base-p addition of n/ρ and (a − 1)n/ρ produces less than a_{p} relevant carries satisfies

#C_{<a_{p}}(z) ≪ z · ø^{D}, as z → ∞,

for some positive ø < 1 and D = 1 + ⌊log_{p} z⌋. In particular, #C_{<a_{p}}(z) is o(z), as z tends to infinity.

Proof. Let z ≥ 1 be a large real number. Thus, if n ≤ z, then the number of p-ary digits of n/ρ is at most D. Let b ≥ a_{p} + θ, where the integer θ ≥ 1 satisfies p^{θ} > a − 1, but p^{θ−1} ≤ a − 1. If n belongs to C_{<a_{p}}, then the p-adic expansion of ⌊n/ρ⌋ cannot contain a block of b consecutive p − 1 digits. Indeed, otherwise there exist i, l ≥ 0 such that

⌊n/ρ⌋ = lp^{i+b} + (p − 1)(p^{i+b−1} + p^{i+b−2} + ⋯ + p^{i}) + m
= lp^{i+b} + (p^{i+b} − p^{i}) + m = (l + 1)p^{i+b} − m′,

with m < p^{i} and 1 ≤ m′ = p^{i}−m ≤ p^{i}. Therefore there are integers c_{1} ≥ 1 and 0 ≤ c_{2} ≤ a−2 and an ϵ ∈ [0, 1) such that

(a − 1)n/ρ = c_{1}p^{i+b} − m′(a − 1) + c_{2} + ϵ

with m′(a−1) < p^{i+θ}. Hence, 1 ≤ m′(a−1)−c_{2} < p^{i+θ} so that the base-p digits of (a−1)n/ρ at all positions i + b − 1, i + b − 2, down to position i + θ, are all positive. Therefore, the addition of n/ρ and (a − 1)n/ρ would produce at least b − θ ≥ a_{p} carries. Note that there are ρ values of n for which ⌊n/ρ⌋ is the same positive integer m. Thus, #C_{<a_{p}}(z) is at most equal to ρ times the number of p-ary strings of length D not containing a_{p} + θ consecutive p − 1 digits. By Lemma 33, there exist ø < 1 and a positive c such that

#C_{<a_{p}}(z) ≤ ρc(1 + o(1))p^{D}ø^{D} ≪ zø^{D}.

Remark 35. The number #C_{<a_{p}}^{[x,D]}(z) of integers n ≤ z for which less than a_{p} carries occur between positions x and D in the base-p addition of n/ρ and (a − 1)n/ρ is seen from the proof of Lemma 34 to be ≪ ø^{D−x+1}z. Indeed, the presence of a_{p} + θ consecutive p − 1 digits at positions i, i + 1, …, i + b − 1, with i ≥ x, generates at least a_{p} carries left of position x. By Lemma 33, #C_{<a_{p}}^{[x,D]}(z) ≪ ρ · cø^{D−x+1}p^{D−x+1} · p^{x} ≪ ø^{D−x+1}z, where the constant implied by the Vinogradov symbol “≪” does not depend on x.

Lemma 36. Let U(P, Q) be a regular Lucas sequence and a ≥ 2, k ≥ 1 be integers. Given a prime p we let A_{p} denote the set of natural numbers n for which the p-adic valuation of U_{(a−1)n+k} is larger than that of \binom{an}{n}_{U}. Then the asymptotic density of A_{p} is zero.

Proof. If n belongs to A_{p}, then there is a unique x ≥ 0 such that (a − 1)n + k = λρp^{x}, with p ∤ λ and ρ the rank of p. We define A_{p}^{x} as the subset of A_{p} of integers n which correspond to that x. Also, for an integral constant c ≥ 0, we use the notation A_{p}^{<c} and A_{p}^{≥c} to denote the union of the A_{p}^{x} over, respectively, all x < c, or all x ≥ c.

We divide k by ρ, say k = qρ + r with 0 ≤ r < ρ. Define u as the smallest positive integer t that satisfies p^{t} > q + 1. Then A_{p} splits into the two subsets A_{p}^{<u} and A_{p}^{≥u}. We begin with showing that A_{p}^{<u} has zero density. Define a_{p} as u + ν + δ. We show the inclusion A_{p}^{<u} ⊂ C_{<a_{p}}, where C_{<a_{p}} was defined in Lemma 34. Suppose n ∈ A_{p}^{<u}. Thus, there is an x, 0 ≤ x < u, such that

ν_{p}\binom{an}{n}_{U} < ν_{p}(U_{(a−1)n+k}) ≤ x + ν + δ < a_{p},  (27)

so that, by the Kummer rule for Lucasnomials, n is in C_{<a_{p}}. But, by Lemma 34, C_{<a_{p}} has zero density. Hence, A_{p}^{<u} is a zero-density set as well.

We take note, for later use, that if we had defined a_{p} as u + v + ν + δ, where v ≥ 0 is some integer, then the same reasoning would have led to #A_{p}^{<u+v}(z) = o(z).

We now turn our attention to the case when x ≥ u. Since

\frac{(a − 1)n}{ρ} = (λ − 1)p^{x} + p^{x} − q − 1 + \frac{ρ − r}{ρ}  (28)

and p^{x} − q − 1 = (p^{x} − p^{u}) + (p^{u} − q − 1), we see that p^{x} − q − 1 has a string of x − u consecutive p − 1 digits at the positions x − 1, x − 2, …, u. If the u-th digit of n/ρ, d_{u}(n/ρ), is ≥ 1, then a minimum of x − u carries occur in the addition of (a − 1)n/ρ and n/ρ, and they occur before reaching the position x. Therefore, with the notation of Lemma 34, if n belongs to A_{p}^{x}(z), then there are no a_{p} + θ consecutive p − 1 digits in-between positions x and D in the base-p expansion of n/ρ, where again a_{p} = u + ν + δ. Thus, by Remark 35, we obtain an upper bound for #A_{p}^{x}(z), namely

#A_{p}^{x}(z) ≪ zø^{D−x+1},

where 0 < ø < 1 and the constant implied by the symbol ≪ depends only on U, a, k and p. We now estimate the size of A_{p}^{≥u} by first considering its subset B := ∪A_{p}^{x} over all x’s in [u, D/2]. Thus, we obtain

#B(z) ≤ ∑_{x=u}^{⌊D/2⌋} #A_{p}^{x}(z) ≪ z ∑_{x=u}^{⌊D/2⌋} ø^{D−x+1} ≤ z \frac{ø^{⌈D/2⌉+1}}{1 − ø} ,

which is a o(z)-function, as z tends to infinity.

Let us now fix an integer x > D/2. For all n in A_{p}^{x}, there is a unique λ satisfying (a − 1)n + k = λρp^{x}. Thus, we get an upper estimate for #A_{p}^{x}(z) by bounding above the corresponding number of λ’s. Indeed,

λ ≤ \frac{(a − 1)n + k}{ρp^{x}} ≤ \frac{(a − 1)z + k}{ρp^{D/2}} ≪ z^{1/2},

as z tends to infinity. Hence,

∑_{D/2<x≤D} #A_{p}^{x}(z) = O(D\sqrt{z}) = O(z^{1/2} log z) = o(z).

Therefore, #A_{p}^{≥u}(z) = o(z).

But what if d_{u}(n/ρ) = 0? We will see that the above reasoning remains valid provided we make some adjustment. The euclidean division of λ − 1 in (28) by a − 1 gives λ − 1 = Q(a − 1) + R with 0 ≤ R ≤ a − 2. Thus,

\frac{(a − 1)n}{ρ} = Q(a − 1)p^{x} + (R + 1)p^{x} − q − 1 + \frac{ρ − r}{ρ},
\frac{n}{ρ} = Qp^{x} + S,

where S < ((a−1)p^{x}−q)/(a−1) ≤ p^{x}. Let v and w be the respective numbers of p-ary digits of a−1 and R. We have w ≤ v. Assume x ≥ u+v. Again p^{x} −q −1 = (p^{x} −p^{u})+(p^{u} −q −1) so that the base-p expansion of (R + 1)p^{x} − q − 1 has the shape

\underbrace{∗ ⋯ ∗}_{w digits} \underbrace{(p − 1)(p − 1) ⋯ (p − 1)}_{x − u times} \underbrace{∗ ⋯ ∗}_{u digits}

When one performs the division algorithm most of us learn in elementary school, although here in base p rather than 10, of (R + 1)p^{x} − q − 1 by a − 1, the quotient has, to the left of the radix point, v or v − 1 digits less than the dividend. That is, ⌊S⌋ must have w + x − v or w + x − v + 1 p-ary digits. Moreover, in that string of digits two nonzero digits are separated by at most v zero digits so that the quotient has to have at least one nonzero digit in every string of v + 1 digits. Because of the x − u ≥ v consecutive p − 1 digits in (R + 1)p^{x} − q − 1, with a moment of thought one sees that the addition of S to (R+1)p^{x} −q −1 has to generate a minimum of x − u − v carries left of the radix point. Thus, we now have a deficit of at most u + v + ν + δ carries to fill in in the addition of (a − 1)n/ρ and n/ρ left of position x to ensure that n is not in A_{p}. Hence, defining a_{p} as u + v + ν + δ, we can argue that #A_{p}^{<u+v}(z) and #A_{p}^{≥u+v}(z) are both o(z), as z tends to infinity, in the same respective ways we argued that #A_{p}^{<u}(z) and #A_{p}^{≥u}(z) were each o(z).

Theorem 37. Let U(P, Q) be a regular Lucas sequence and a ≥ 2, k ≥ 1 be integers. Then for almost all integers n ≥ 1, we find that

\frac{1}{U_{(a−1)n+k}} \binom{an}{n}_{U}is an integer.

Proof. The set \overline{D}_{U,a,k} is the union of the A_{p}’s over all primes p. However, by Lemma 17, all but finitely many of them are empty. Since each of the finitely many nonempty ones have density zero by Lemma 36, we see that \overline{D}_{U,a,k} itself has zero density.

Incidentally, the proof of Lemma 36 provides an answer to one of the three questions posed in Remark 19. We state the answer as a theorem.

Theorem 38. Let U(P, Q) be a regular Lucas sequence and a ≥ 2, k ≥ 1 be integers. Then there exists an integer m = m(U, a, k), m ≥ 1, such that for all integers n ≥ 1

\frac{m}{U_{(a−1)n+k}} \binom{an}{n}_{U}is an integer.  (29)

Proof. By Lemma 17, for all but finitely many primes p, A_{p} is empty. But if A_{p} is empty, then ν_{p}(U_{(a−1)n+k}) ≤ ν_{p}\binom{an}{n}_{U} for all n ≥ 1. Thus, the existence of an m, for which (29) holds for all n, depends on whether for the remaining finitely many primes p the difference ν_{p}(U_{(a−1)n+k}) − ν_{p}\binom{an}{n}_{U} is bounded above. By the proof of Lemma 36 this is true. Indeed, with the notation of the lemma, given A_{p}, we saw (27) that for n ∈ A_{p}^{<u+v}, the p-adic valuation of U_{(a−1)n+k} is bounded above by a_{p} = u + v + ν + δ. If n ∈ A_{p}^{≥u+v}, then we found that at least x − u − v carries occurred in the base-p addition of n/ρ and (a − 1)n/ρ prior to reaching position x. Thus the difference ν_{p}(U_{(a−1)n+k}) − ν_{p}\binom{an}{n}_{U} is at most equal to a_{p}. if α_{p} ≥ 0 is the least e for which ν_{p}(U_{(a−1)n+k}) − ν_{p}\binom{an}{n}_{U} ≤ e for all n ≥ 1, then m = ∏ p^{α_{p}}, the product being over all primes of rank less than ak, is the least integer to satisfy (29).

7 Appendix: The table of n-defective Lucas sequences

Here is a table of n-defective nonzero-discriminant regular Lucas sequences U(P, Q), with P > 0, for all n ≥ 2. We did nothing more than concatenate in one table the data contained in the three tables [8, Tables 1 and 3, pp. 78–79], [1, p. 312], except for parametrizing the sequences in terms of P and Q rather than P and Δ.

Semi-columns are used to separate different parametric families of n-defective sequences, while commas are used to specify constraints on the parameters. Parameters i and j are integers. The case n = 6 has three lines. To alleviate the table we did not repeat at various lines that whenever a parametrization yields the sequence I = U(2, 1), it should be discarded.

n  (P, Q), P > 0, (P, Q) ≠ (2, 1)
2  (1, Q), Q ≠ −3;  (2^{i}, 2j + 1), i ≥ 1
3  (P, P^{2} ± 1);  (P, P^{2} ± 3^{i}), 3 ∤ P
4  (P, (P^{2} ± 1)/2), P odd;  (2i, 2i^{2} ± 1)
5  (1, −1) (1, 2) (1, 3) (1, 4) (2, 11) (12, 55) (12, 377)

(P, (P^{2} − 1)/3), 3 ∤ P, P ≥ 4; (P, (P^{2} ± 3)/3), 3 | P;

6  (P, (P^{2} − (−2)^{i})/3), P ≡ ±1 (mod 6), i ≥ 1, (P, i) ≠ (1, 1);

(P, (P^{2} ± 3 · 2^{i})/3), P ≡ 3 (mod 6), i ≥ 1

7  (1, 2) (1, 5)
8  (1, 2) (2, 7)
10  (2, 3) (5, 7) (5, 18)
12  (1, −1) (1, 2) (1, 3) (1, 4) (1, 5) (2, 15)
13  (1, 2)
18  (1, 2)
30  (1, 2)

TABLE A.

List of all n-defective regular Lucas sequences U(P, Q), n ≥ 2

8 Acknowledgments

We thank the referee for his fast return on a long paper and the referee and the editor-in-chief for their various inputs. We appreciated the remarks of J.-P. Bézivin on his reading of the former papers [5, 22]; Theorem 11 is derived from a remark of his. On a short private visit to Nicosia, Cyprus, last December, P. Damianou and E. Ieronymou kindly helped secure a fruitful office in the mathematics department for me.

References

[1] M. Abouzaid, Les nombres de Lucas et Lehmer sans diviseur primitif, J. Théor. Nombres Bordeaux, 18 (2006), 299–313.

[2] C. Ballot, The congruence of Wolstenholme for generalized binomial coefficients related to Lucas sequences, J. Integer Sequences, 18 (2015) Article 15.5.4.

[3] C. Ballot, Divisibility of Fibonomials and Lucasnomials via a general Kummer rule, Fibonacci Quart., 53 (2015) 194–205.

[4] C. Ballot, On the constant in the average digit sum for a recurrence-based numeration, Unif. Distrib. Theory, 11 (2016), 125–150.

[5] C. Ballot, Divisibility of the middle Lucasnomial coefficient, Fibonacci Quart., 55 (2017) 297–308.

[6] A. Benjamin and S. Plott, A combinatorial approach to Fibonomial coefficients, Fibonacci Quart., 46/47 (2008/09) 7–9.

[7] A. Benjamin and E. Reiland, Combinatorial proofs of Fibonomial identities, Fibonacci Quart., Conference Proceedings, 52 (2014), no. 5, 28–34.

[8] Y. Bilu, G. Hanrot, P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers. With an appendix by M. Mignotte, J. Reine Angew. Math., 539 (2001), 75– 122.

[9] W. S. Chou, T. X. He and P. Shiue, On the Primality of the Generalized Fuss-Catalan Numbers, J. Integer Sequences, 21 (2018) Article 18.2.1.

[10] T. Edgar, Totienomial coefficients, Integers, 14 (2014), Paper A62.

[11] T. Edgar and M. Spivey, Multiplicative functions, generalized binomial coefficients, and generalized Catalan numbers, J. Integer Sequences, 19 (2016) Article 16.1.6.

[12] S. Ekhad, The Sagan-Savage Lucas-Catalan polynomials have positive coefficients. Preprint, January 21 2011. Available at http://arxiv.org/abs/1101.4060.

[13] H. W. Gould, Fibonomial Catalan numbers: arithmetic properties and a table of the first fifty numbers, Abstract 71T-A216, Notices Amer. Math. Soc., (1971), 938.

[14] H. W. Gould, A new primality criterion of Mann and Shanks and its relation to a theorem of Hermite with extension to Fibonomials, Fibonacci Quart., 10 (1972) 355– 364, 372.

[15] L. J. Guibas and A. M. Odlyzko, Long repetitive patterns in random sequences, Z. Wahrsch. Verw. Gebiete, 53 (1980), 241–262.

[16] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fourth Edition, Oxford at the Clarendon Press, 1960.

[17] D. Knuth and H. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math., 396 (1989), 212–219.

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

[19] F. Luca and P. Stănică, Monotonic phinomial coefficients, Bull. Aust. Math. Soc., 95 (2017), 365–372.

[20] É. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math., 1 (1878), 184–240, 289–321.

[21] G. Myerson, ed., with notes by K. Wooding, Western Number Theory Problems, 17 & 19 December 2016. Available at

    https://wcnt.files.wordpress.com/2017/09/wcnt-problems-2016.pdf.

[22] C. Pomerance, Divisibility of the middle binomial coefficient, Amer. Math. Monthly, 122 (2015), 636–644.

[23] B. Sagan and C. Savage, Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences, Integers, 10 (2010), A52, 697–703.

[24] B. Sagan, Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences, Part 5 of a Talk at Rutgers University videotaped by Edinah Gnang,

    December 9 2010, available at http://www.youtube.com/watch?v=Fdn890jg2U0.

[25] C. Sanna, Central binomial coefficients divisible by or coprime to their indices, Int. J. Number Theory, 14 (2018), 1135–1142.

[26] C. Sanna, The p-adic valuation of Lucas sequences, Fibonacci Quart., 54 (2016) 118– 124.

[27] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Published electroni-

    cally at https://oeis.org.

[28] R. P. Stanley, Catalan Numbers, Cambridge University Press, New York, 2015.

[29] B. Sury, Generalized Catalan numbers: linear recursion and divisibility, J. Integer Sequences, 12 (2009) Article 09.7.5.

[30] M. Ulas, A note on Erdős-Straus and Erdős-Graham divisibility problems (with an appendix by Andrzej Schinzel), Int. J. Number Theory, 9 (2013), 583–599.

[31] H. C. Williams, Édouard Lucas and Primality Testing, Wiley, Canadian Math. Soc. Series of Monographs and Advanced Texts, 1998.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 11B65, 11B39, 05A10. Keywords: generalized binomial coefficient, Lucasnomial, generalized Fuss-Catalan number, Lobb number, ballot number, Lucas sequence, carry, Kummer’s rule, asymptotic density, integrality, divisibility.

(Concerned with sequences \underline{A001764}, \underline{A003150}, \underline{A014847}, \underline{A107920}.)

Received March 6 2018; revised version received June 6 2018. Published in Journal of Integer Sequences, August 22 2018.

Return to Journal of Integer Sequences home page.