The p-Adic Valuation of Lucasnomials

When p is a Special Prime

Christian Ballot Normandie Université UNICAEN, CNRS Laboratoire de Mathématiques Nicolas Oresme 14000 Caen France

              christian.ballot@unicaen.fr

Abstract

To determine the p-adic valuation of a Lucasnomial \binom{m}{n}_{U}, i.e., of a generalized binomial coefficient with respect to a fundamental Lucas sequence U = U(P, Q), there is an adequate Kummer rule if p is a regular prime. No such rule exists if p is a special prime, i.e., if p divides gcd(P, Q). We provide a complete description of the p-adic valuation of Lucasnomials when p is special, with some numerical examples. Applications to the integrality of generalized Lucasnomial Fuss-Catalan numbers, Lucasnomial ballot and Lucasnomial Lobb numbers are also given.

1 Introduction

A fundamental Lucas sequence U = U(P, Q) = (U_{n})_{n≥0}, where P and Q are nonzero integral parameters, is a second-order linear recurring sequence with initial conditions U_{0} = 0 and U_{1} = 1, which satisfies

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

for all n ≥ 0. The fundamental Lucas sequence together with its companion sequence, V (P, Q), which won’t intervene in this paper, form a pair of sequences which derive their name from the famous memoir of Lucas of 1878 [13], and have a long history of studies and applications. Later, Lucas also dedicated a chapter of his number theory book [14] to these sequences. Readers may consult [18, Chap. 4] for a good introduction to their properties. The Lucas sequence U is a divisible sequence. That is, if m | n, then U_{m} | U_{n}. If no term U_{t}, t ≥ 1, is zero, then U is said to be nondegenerate.

For U nondegenerate and m and n two positive integers, one defines the Lucasnomial, or Lucasnomial coefficient, \binom{m+n}{n}_{U} as

\frac{U_{m+n}U_{m+n−1} ⋯ U_{1}}{(U_{m}U_{m−1} ⋯ U_{1})(U_{n}U_{n−1} ⋯ U_{1})} = \frac{U_{m+n} ⋯ U_{m+1}}{U_{n} ⋯ U_{1}} .

Lucasnomials have been proved to be integers in various ways, algebraic, arithmetic and combinatorial. One of the quickest ways to show their integrality is by the Lucasnomial identity

\binom{r}{s}_{U} = U_{s+1}\binom{r − 1}{s}_{U} − QU_{r−s−1}\binom{r − 1}{s − 1}_{U},

followed by an induction, which is the way many papers have used (e.g., [3, eq. (11)], [10, Lemma 1, eq. (6)]). If U = U(2, 1), then U_{n} = n for all n ≥ 0, so that \binom{m+n}{n}_{U} is the binomial coefficient \binom{m+n}{n}.

Given a prime p, the p-adic valuation of an integer x is the largest exponent t ≥ 0 such that p^{t} divides x. It is denoted by ν_{p}(x). For a binomial coefficient or a Lucasnomial, we write ν_{p}\binom{∗}{∗}_{U} instead of

ν_{p}(\binom{∗}{∗}_{U}),

to alleviate notation.

By the well-known Kummer rule [12], the p-adic valuation of the binomial coefficient \binom{m+n}{n} is equal to the number of carries that come up when you add m and n in base p. For instance, in base 3, 16 = (121)_{3} and 5 = (012)_{3}. Exactly two carries occur when adding 16 and 5 in base 3. Thus ν_{3}\binom{21}{5} = 2.

The p-adic valuation of a rational number x/y is ν_{p}(x) − ν_{p}(y). A prime p is said to be special in relation to the Lucas sequence U(P, Q) whenever p | gcd(P, Q). A prime is said to be regular if it does not divide Q. Primes that divide Q, but not P, do not divide any U_{n}, n ≥ 1.

For regular primes p with respect to a Lucas sequence U, there is a Kummer rule to help determine the p-adic valuation of Lucasnomials \binom{m+n}{n}_{U} ([1, Section 4], [11]). The rank, ρ, of p is the least positive integer t such that p | U_{t}. If p is regular, then the rank of p exists and is either p, or a divisor of p ± 1. The valuation of \binom{m+n}{n}_{U} is the number of carries that occur to the left of the radix point when adding m/ρ and n/ρ in base p, plus ν_{p}(U_{ρ}) if a carry occurs across the radix point. However, if p = 2, a carry occurring inbetween the first two places left of the radix point, everything else being equal, bears a weight of ν_{2}(P^{2} − 3Q) instead of 1.

There are a few additional results for the p-adic valuation of Lucasnomials of the form \binom{p^{b}}{p^{a}}_{U} [1, Thm. 7.1] as well as for various Fibonomial coefficients [15]. Fibonomials are the Lucasnomials that correspond to the Fibonacci sequence F = U(1, −1).

There is no Kummer rule for special primes. Our main theorem, Theorem 1, provides formulas to express in a concise and useful manner this valuation. Theorem 1 is based on the complete description [4] of the p-adic valuation of the terms of a Lucas sequence when p is a special prime. If p is special, then we write P = p^{a}P′ and Q = p^{b}Q′, where a and b are positive integers and p ∤ P′Q′. Note that the prime p is a regular prime with respect to the Lucas sequence U′ = U(P′, Q′), with a rank ρ′ ≥ 3 since U′_{2} = P′. Define the condition P_{0} as

P_{0} : 2 ≤ p ≤ 3 and 2a = b + 1.  (1)

If p is special, we will often refer to the following four equalities, which, gathered together, form the content of [4, Thm 1.2].

If b ≥ 2a, then ν_{p}(U_{k}) = \begin{cases}(k − 1)a, & if b > 2a; \\ (k − 1)a + ν_{p}(U′_{k}), & if b = 2a, \end{cases}  (2)

while, if b < 2a, then

\begin{aligned}ν_{p}(U_{2k+1}) & = bk, \\ ν_{p}(U_{2k}) & = bk + (a − b) + ν_{p}(k) + ν_{p}(P^{′2} − Q′) · [P_{0}] · [p | k], \end{aligned}  (3)

where P_{0} is defined in (1) and [−] denotes the Iverson symbol.

We recall that, given a condition P, the Iverson function evaluated at P is defined as

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

We are now ready to state our theorem.

Theorem 1. Let U = U(P, Q) be a nondegenerate fundamental Lucas sequence, p be a special prime where we set P = p^{a}P′, Q = p^{b}Q′, a and b positive integers with p ∤ P′Q′. Suppose m and n are two positive integers. Let r_{m} = (m mod 2p) and r_{n} = (n mod 2p), i.e., r_{m} and r_{n} are the respective remainders of the euclidean division of m and n by 2p. Let P_{1} and P_{2} be the following conditions:

• P_{1}: m and n are odd;

• P_{2}: 2 ≤ p ≤ 3 and 2a = b + 1 and r_{m} + r_{n} ≥ 2p.

Then

ν_{p}\binom{m + n}{n}_{U} = \begin{cases}amn, & if b > 2a; \\ amn + ν_{p}\binom{m+n}{n}_{U′}, & if b = 2a; \\ b⌊\frac{mn}{2}⌋ + ν_{p}(\begin{matrix}⌊ & \frac{m+n}{2} & ⌋ \\ ⌊ & \frac{n}{2} & ⌋ \end{matrix}) + (a + ν_{p}(\frac{m+1}{2})) · [P_{1}] + c · [P_{2}], & if b < 2a, \end{cases}

where U′ is the Lucas sequence U(P′, Q′), c = ν_{p}(P^{′2} − Q′) and [−] denotes the Iverson symbol.

Remark 2. The expression of the valuation of \binom{m+n}{n}_{U} when b < 2a reduces much if at least one of m or n is even and p ≥ 5 or 2a > b + 1. In those cases, this valuation is

b\frac{mn}{2} + ν_{p}(\begin{matrix}⌊ & \frac{m+n}{2} & ⌋ \\ ⌊ & \frac{n}{2} & ⌋ \end{matrix}).  (4)

Section 2 contains a proof of Theorem 1. In Section 3 we present three examples of calculations of a Lucasnomial valuation using the main theorem. In doing so we use the classical rule of Kummer to evaluate the p-adic valuation of some binomial coefficients, and its generalizations to Lucasnomials [1, 11], which we recalled earlier. We are pleased to apply Theorem 1 to complete the arithmetic proof of the integrality of generalized Lucasnomial Fuss-Catalan numbers given in [3]. This is done in Theorem 6 of Section 4, together with an introduction to these numbers. Immediate corollaries are proved which complete earlier proofs of the integrality of the generalized Lucasnomial Lobb numbers and of the Lucasnomial ballot numbers.

2 Proof of Theorem 1

There are three cases to examine.

Case 1: b > 2a. In this case, (2) says that, for all k ≥ 1, ν_{p}(U_{k}) = (k − 1)a. Thus ν_{p}(U_{ℓ}U_{ℓ−1} ⋯ U_{1}) = ∑_{i=1}^{ℓ−1} ia = a\frac{(ℓ−1)ℓ}{2}. Hence,

ν_{p}\binom{m + n}{n}_{U} = \frac{a}{2}((m + n − 1)(m + n) − (n − 1)n − (m − 1)m) = amn.  (5)

Case 2: b = 2a. By (2), and more precisely by [4, Proof of Thm 2.2], we have U_{k} = p^{(k−1)a}U′_{k}, where U′ = U(P′, Q′). Thus, using (5), we find that

\binom{m + n}{n}_{U} = p^{amn}\binom{m + n}{n}_{U′},  (6)

and the result we seeked follows.

Case 3: b < 2a. By (3) and writing c = ν_{p}(P^{′2} − Q′), we find that

ν_{p}(U_{ℓ} ⋯ U_{1}) = ∑_{i=1}^{⌊ \frac{ℓ−1}{2} ⌋} ν_{p}(U_{2i+1}) + ∑_{i=1}^{⌊ \frac{ℓ}{2} ⌋} ν_{p}(U_{2i})

= b ∑_{i=1}^{⌊ \frac{ℓ−1}{2} ⌋} i + b ∑_{i=1}^{⌊ \frac{ℓ}{2} ⌋} i + (a − b)⌊\frac{ℓ}{2}⌋ + ν_{p}(⌊\frac{ℓ}{2}⌋!) + ⌊\frac{⌊\frac{ℓ}{2}⌋}{p}⌋ · c · [P_{0}],

which by combining the two sums on the RHS of the previous equation and using the fact [9, pp. 71–72] that ⌊\frac{⌊ \frac{ℓ}{2} ⌋}{p}⌋ = ⌊\frac{ℓ}{2p}⌋, yields

ν_{p}(U_{ℓ} ⋯ U_{1}) = b⌊\frac{ℓ − 1}{2}⌋⌊\frac{ℓ + 1}{2}⌋ + \frac{bℓ}{2} · [2 | ℓ] + (a − b)⌊\frac{ℓ}{2}⌋ + ν_{p}(⌊\frac{ℓ}{2}⌋!) + ⌊\frac{ℓ}{2p}⌋ · c · [P_{0}]. (7)

Note that ν_{p}\binom{m+n}{n}_{U} = ν_{p}(U_{m+n} ⋯ U_{1}) − ν_{p}(U_{m} ⋯ U_{1}) − ν_{p}(U_{n} ⋯ U_{1}). Guided by equation (7), we first take care of the first two terms of the RHS of (7). An elementary calculation gives

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

+ (\frac{m + n}{2} · [2 | m + n] − \frac{m}{2} · [2 | m] − \frac{n}{2} · [2 | n])

= \begin{cases}\frac{mn+1}{2}, & if m and n are both odd; \\ \frac{mn}{2}, & otherwise. \end{cases}

Since

⌊\frac{m + n}{2}⌋ − ⌊\frac{m}{2}⌋ − ⌊\frac{n}{2}⌋ = \begin{cases}1, & if m and n are both odd; \\ 0, & otherwise, \end{cases}  (8)

the contribution of the third terms of the RHS of (7) to ν_{p}\binom{m+n}{n}_{U} is nil unless m and n are both odd when it is a − b. Hence, so far, the contribution of the first three terms of the RHS of (7) is

a · [P_{1}] + b \begin{cases}\frac{mn−1}{2}, & if m and n are odd; \\ \frac{mn}{2}, & otherwise; \end{cases} = a · [P_{1}] + b · ⌊\frac{mn}{2}⌋ .

The contribution of the fourth terms ν_{p}(⌊\frac{ℓ}{2}⌋!) to ν_{p}\binom{m+n}{n}_{U} is

C_{4} := ν_{p}(⌊\frac{m + n}{2}⌋!) − ν_{p}(⌊\frac{m}{2}⌋!) − ν_{p}(⌊\frac{n}{2}⌋!).  (9)

By (8), if m and n are not each odd, then the contribution C_{4} is exactly equal to

ν_{p}(\begin{matrix}⌊ & \frac{m+n}{2} & ⌋ \\ ⌊ & \frac{n}{2} & ⌋ \end{matrix}).

If m and n are odd, then, by (8),

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

In particular, \frac{m+1}{2}! = ⌊\frac{m}{2}⌋! · \frac{m+1}{2}. Hence, in this case, the contribution, C_{4}, of the fourth terms in (9) is

ν_{p}(⌊\frac{m + n}{2}⌋!) − ν_{p}(⌊\frac{n}{2}⌋!) − ν_{p}(\frac{m + 1}{2}!) + ν_{p}(\frac{m + 1}{2})

= ν_{p}(\begin{matrix}⌊ & \frac{m+n}{2} & ⌋ \\ ⌊ & \frac{n}{2} & ⌋ \end{matrix}) + ν_{p}(\frac{m + 1}{2}).

It remains to evaluate the contribution of the fifth terms in (7). It is

(⌊\frac{m + n}{2p}⌋ − ⌊\frac{m}{2p}⌋ − ⌊\frac{n}{2p}⌋) · c · [P_{0}].

Since for two real numbers x and y, we have

⌊x + y⌋ − ⌊x⌋ − ⌊y⌋ = \begin{cases}0, & if \{x\} + \{y\} < 1; \\ 1, & otherwise, \end{cases}

where {−} denotes the fractional part, we see that this contribution is nonzero provided the sum of the fractional parts of \frac{m}{2p} and of \frac{n}{2p} is at least 1, i.e., if r_{m} + r_{n} ≥ 2p. We conclude by observing that [P_{2}] = [P_{0}] · [r_{m} + r_{n} ≥ 2p], where P_{2} was defined in Theorem 1.

3 Examples

We compute the p-adic valuation of a few Lucasnomials via Theorem 1.

Example 3. Suppose U = U(33, 30) and p = 3. Then a = 1, b = 1, P′ = 11, Q′ = 10 and P^{′2} − Q′ = 111. Note that b < 2a. We want to compute, say, ν_{3}\binom{36}{13}_{U}. Thus m = 23 and n = 13. Hence, following Theorem 1, we obtain

ν_{3}\binom{36}{13}_{U} = 1 · ⌊\frac{23 × 13}{2}⌋ + ν_{3}\binom{\frac{36}{2}}{⌊\frac{13}{2}⌋} + (1 + ν_{3}(\frac{23 + 1}{2})) · 1 + ν_{3}(111) · [P_{2}].

Since m = 3 · 6 + 5 and n = 2 · 6 + 1, the sum r_{m} + r_{n} = 5 + 1 = 2p. Also, 2 ≤ p ≤ 3 and 2a = 2 = b + 1. Hence, [P_{2}] = 1. It follows that

ν_{3}\binom{36}{13}_{U} = 149 + ν_{3}\binom{12 + 6}{6} + (1 + 1) + 1.

But 12 = 9 + 3 = (110)_{3} and 6 = 2 · 3 = (020)_{3} so there is a unique carry in the base-3 addition of 12 and 6. Thus, by Kummer’s rule [12], we find that ν_{3}\binom{18}{6} = 1. Hence,

ν_{3}\binom{36}{13}_{U} = 153.

Example 4. Consider the Lucas sequence U = U(4, −2) and compute the 2-adic valuation of \binom{22}{7}_{U}. We find that a = 2 and b = 1 so that b < 2a. Here m = 15 and n = 7. Also P^{′2} − Q′ = 2. Thus, by Theorem 1,

ν_{2}\binom{22}{7}_{U} = ⌊\frac{7 × 15}{2}⌋ + ν_{2}\binom{11}{3} + (2 + ν_{2}(\frac{15 + 1}{2})) · 1 + ν_{2}(2) · [P_{2}].

By Kummer’s rule [12], we have ν_{2}\binom{11}{3} = 0 because there are no carries in the base-2 addition of 8 = (1000)_{2} and 3 = (11)_{2}. Also, [P_{2}] = 0 because, of the three sub-conditions that make up P_{2}, one is false, namely 2a = 4 ≠ b + 1 = 2. Hence,

ν_{2}\binom{22}{7}_{U} = 52 + 0 + (2 + 3) + 0 = 57.

Example 5. Let U = U(20, 25) and let us evaluate the 5-adic valuation of the Lucasnomial \binom{25}{11}_{U}. Here m = 14, n = 11, p = 5, a = 1, b = 2 and U′ = U(4, 1). Since b = 2a, we must have

ν_{5}\binom{25}{11}_{U} = amn + ν_{5}\binom{25}{11}_{U′} = 14 × 11 + ν_{5}\binom{25}{11}_{U′}.

The initial values of U′ are 0, 1, 4 and 15. Thus, ρ′, the rank of 5 in U′, is 3. To compute ν_{5}\binom{25}{11}_{U′}, as explained in the introduction, we tally carries in the base-5 addition of m/ρ′ and n/ρ′ [1, Thm. 4.2]. Now

\frac{14}{ρ′} = 4 + \frac{2}{3} = (4)_{5} + \frac{2}{3},
\frac{11}{ρ′} = 3 + \frac{2}{3} = (3)_{5} + \frac{2}{3},

so there are two carries, one across the radix point which accounts for ν_{5}(U_{ρ′}) = ν_{5}(15) = 1 in the valuation of ν_{5}\binom{25}{11}_{U′} and another since 1 + 4 + 3 > 5, which accounts for 1. Hence,

ν_{5}\binom{25}{11}_{U} = 154 + 2 = 156.

4 Applications

Given two natural numbers r ≥ 2 and s ≥ 1, one defines for all integers t ≥ 1 the generalized Fuss-Catalan numbers as

C_{r,s}(t) = \frac{s}{(r − 1)t + s}\binom{rt + s − 1}{t}.  (10)

When s = 1, we find the Fuss-Catalan numbers, and when in addition r = 2, we end up with the well-known Catalan numbers

C(t) = \frac{1}{t + 1}\binom{2t}{t},

with their many occurrences and combinatorial interpretations [17]. The generalized Fuss-Catalan numbers possess at least one combinatorial interpretation counting Raney sequences [9, pp. 359–363]. So, in particular, they are integers.

Given a nondegenerate Lucas sequence U = U(P, Q), the generalized Lucasnomial Fuss-Catalan numbers, C_{U,r,s}(t), are defined in an analogous manner [3], i.e.,

C_{U,r,s}(t) = \frac{U_{s}}{U_{(r−1)t+s}} \binom{rt + s − 1}{t}_{U}.  (11)

In fact, this is more than a definition by analogy, since for the Lucas sequence U = U(2, 1) we fall back on the generalized Fuss-Catalan numbers defined in (10). Lucasnomial Fuss-Catalan numbers [3] correspond to the case s = 1, while if s = 1 and r = 2, then we find numbers considered much earlier, the Lucasnomial Catalan numbers [2, 7, 8, 16]. Only very recently has a combinatorial interpretation of the Lucasnomial Fuss-Catalan numbers

C_{U,r,1}(t) = \frac{1}{U_{(r−1)t+1}} \binom{rt}{t}_{U},

been discovered [5, 6] for all r ≥ 2. The Lucasnomial Fuss-Catalan numbers were shown to be always integers by an algebraic argument [3, Thm. 6]. This proof did not seem to extend to generalized Lucasnomial Fuss-Catalan numbers. But, we were nearly able to prove their integrality via an arithmetic argument. That is, for all regular primes p, i.e., primes p not dividing gcd(P, Q), the p-adic valuation of C_{U,r,s}(t) is nonnegative [3, Thm. 9 and Rmk. 10, p. 11]. Consequently, if U(P, Q) is regular, i.e., if gcd(P, Q) = 1, then the generalized Lucasnomial Fuss-Catalan numbers C_{U,r,s}(t) are already known to be integral. With the help of Theorem 1, we are able to prove their integrality in all cases, by showing that if p | gcd(P, Q), then ν_{p}(C_{U,r,s}(t)) ≥ 0.

Theorem 6. The generalized Lucasnomial Fuss-Catalan numbers

C_{U,r,s}(t) = \frac{U_{s}}{U_{(r−1)t+s}} \binom{rt + s − 1}{t}_{U}

are integral for all nondegenerate fundamental Lucas sequences U = U(P, Q), all integers r ≥ 2, s ≥ 1 and t ≥ 1.

Proof. If s = 1, then C_{U,r,s}(t) is a Lucasnomial Fuss-Catalan number which, as mentioned prior to stating the theorem, is known to be an integer [3, Thm. 6]. Thus, our proof assumes s ≥ 2. Furthermore, we readily see that

C_{U,r,s}(t) = \frac{U_{s}}{U_{t}} \binom{rt + s − 1}{t − 1}_{U}.  (12)

Since U_{t} = 1 for t = 1, we also assume t ≥ 2.

As mentioned earlier, by [3, Thm. 9], it suffices to show the p-adic valuation of C_{U,r,s}(t) is nonnegative if p | gcd(P, Q). We continue using the notation of Theorem 1 and, in particular, the exponents of p in P and Q are respectively denoted by a and b. The letter c denotes the constant ν_{p}(P^{′2} − Q′). Using (12), we see that

ν_{p}(C_{U,r,s}(t)) = ν_{p}(U_{s}) − ν_{p}(U_{t}) + ν_{p}\binom{rt + s − 1}{t − 1}_{U}.  (13)

We will use Theorem 1 to evaluate the p-adic valuation of the above Lucasnomial \binom{rt+s−1}{t−1}_{U}. Thus, in the notation of Theorem 1,

m = (r − 1)t + s  and  n = t − 1.  (14)

Case I: b > 2a. Then, by equation (2) and Theorem 1

ν_{p}(C_{U,r,s}(t)) = (s − 1)a − (t − 1)a + a((r − 1)t + s)(t − 1) := aN(s, t).

This valuation is clearly positive since (r − 1)t + s ≥ 2 + 2 = 4. Hence, Case 1 is proved.

Case II: b = 2a. Since U_{k} = p^{a(k−1)}U′_{k}, we readily see, by (13), that

ν_{p}(C_{U,r,s}(t)) = aN(s, t) + ν_{p}(U′_{s}) − ν_{p}(U′_{t}) + ν_{p}\binom{rt + s − 1}{t − 1}_{U′}
= aN(s, t) + ν_{p}(C_{U′,r,s}(t)),

where N(s, t) was shown to be positive in Case 1. Since p is a regular prime with respect to U′, we know that ν_{p}(C_{U′,r,s}(t)) ≥ 0 by [3, Rmk. 10]. Case III: b < 2a. By equations (3), Theorem 1 and (13), we see that the quantity

M(s, t) := ⌊\frac{s}{2}⌋ − ⌊\frac{t}{2}⌋ + ⌊\frac{((r − 1)t + s)(t − 1)}{2}⌋  (15)

will appear in the calculation. So we begin with inequalities true in all parity cases for s and t.

M(s, t) ≥ \frac{s − 1}{2} − \frac{t}{2} + \frac{((r − 1)t + s)(t − 1) − 1}{2}

≥ \frac{s − t − 1}{2} + \frac{t(t − 1)}{2} + \frac{s(t − 1)}{2} − \frac{1}{2}

≥ \frac{s − t − 1}{2} + \frac{t}{2} + (t − 1) − \frac{1}{2}

= \frac{s − 1}{2} + t − \frac{3}{2} ≥ 1,

since s ≥ 2 and t ≥ 2. In fact, we also have

M(s, t) ≥ \frac{s − 1}{2} + t − \frac{3}{2} ≥ \frac{t}{2} + \frac{t}{2} − 1 ≥ \frac{t}{2}.  (16)

We break up the argument into four subcases depending on the parity of s and t.

Subcase 1: s and t are odd. Then we see by (3) and Theorem 1 that

ν_{p}(C_{U,r,s}(t)) ≥ b · M(s, t) ≥ b > 0.

Subcase 2: s is even and t is odd. Again with the use of (3) and Theorem 1, we find that ν_{p}(C_{U,r,s}(t)) satisfies the lower bound

ν_{p}(C_{U,r,s}(t)) ≥ b · M(s, t) + (a − b) ≥ a > 0.

Subcase 3: s is odd and t even. By (3), Theorem 1, and noting that m = (r − 1)t + s and n = t − 1 are both odd, we obtain, using (13) again,

ν_{p}(C_{U,r,s}(t)) ≥ bM(s, t) − (a − b) − ν_{p}(t/2) − c · [P_{0}] · [p | t/2]

+ ν_{p}\binom{(m + n)/2}{(n − 1)/2} + (a + ν_{p}((m + 1)/2)) + c · [P_{0}] · [r_{m} + r_{n} ≥ 2p]

= bM(s, t) + b + ν_{p}\binom{(m + n)/2}{(n − 1)/2} + ν_{p}((m + 1)/2) − ν_{p}((n + 1)/2)

+ c · [P_{0}] · ([r_{m} + r_{n} ≥ 2p] − [p | t/2])

≥ 2b,

because M(s, t) ≥ 1 and

ν_{p}\binom{(m + n)/2}{(n − 1)/2} + ν_{p}((m + 1)/2) − ν_{p}((n + 1)/2) ≥ 0,

since this is the valuation of the binomial coefficient

\frac{(m + 1)/2}{(n + 1)/2}\binom{(m + n)/2}{(n − 1)/2} = \binom{(m + n)/2}{(n + 1)/2}.

Also the quantity H(s, t) := [P_{0}] · ([r_{m} + r_{n} ≥ 2p] − [p | t/2]) is nonnegative. Indeed, if H(s, t) < 0, then 2 ≤ p ≤ 3 and p | t/2. We are about to check these two conditions imply r_{m} + r_{n} ≥ 2p so that H(s, t) ≥ 0, a contradiction. Assume first p = 2. Then p | t/2 implies 4 | t. But n = t − 1 implies r_{n} = 3 since 2p = 4. Since m = (r − 1)t + s and s is odd, r_{m} = 1 or 3. Hence, r_{m} + r_{n} ≥ 4 = 2p.

Now suppose that p = 3. Then 3 | t/2 implies 6 | t. Since n = t − 1, the remainder, r_{n}, of the division of n by 2p, is 5. But m = (r − 1)t + s so m ≡ s (mod 6). Now s is odd so r_{m} ≠ 0. Hence, r_{m} + r_{n} ≥ 6 = 2p.

Subcase 4: s and t are both even. Thus m is even and n = t − 1 is odd. Using equations (3) and Theorem 1, we see that

ν_{p}(C_{U,r,s}(t)) ≥ bM(s, t) + ν_{p}(s/2) − ν_{p}(t/2) + ν_{p}\binom{(m + n − 1)/2}{(n − 1)/2}
+ c · [P_{0}] · ([ p | (s/2) ] − [ p | (t/2) ] + [r_{m} + r_{n} ≥ 2p])
≥ bM(s, t) + ν_{p}(s/2) − ν_{p}(t/2) ≥ M(s, t) − ν_{p}(t/2).

The second inequality above holds because the quantity

G(s, t) := [P_{0}] · ([p | s/2] − [p | t/2] + [r_{m} + r_{n} ≥ 2p]),

is nonnegative. If not, p = 2 or 3, p | t/2 and p ∤ s/2. But these conditions imply r_{m}+r_{n} ≥ 2p so that G(s, t) ≥ 0. Indeed, if p = 2, then 4 | t. Since n = t − 1, r_{n} = 3. Moreover, 2 ∤ s/2 implies s ≡ 2 (mod 4). Now m = (r − 1)t + s so r_{m} = 2. So r_{m} + r_{n} is 5 and exceeds 2p = 4. If p = 3, then 6 | t and r_{n} = 5. Moreover, 3 ∤ s implies r_{m} ≠ 0. Again, r_{m} + r_{n} ≥ 2p = 6 as claimed.

Now, from (16), we know M(s, t) ≥ t/2. Say ν_{p}(t/2) = u. If u = 0, then ν_{p}(C_{U,r,s}(t)) ≥ M(s, t) > 0. If u ≥ 1, then

t/2 ≥ p^{u} ≥ 2^{u} ≥ (1 + 1)^{u} = ∑_{k=0}^{u} \binom{u}{k} ≥ 1 + \binom{u}{1} = 1 + u.

Hence, ν_{p}(C_{U,r,s}(t)) ≥ t/2 − u ≥ 1.

Remark 7. Actually, if p is special, then all generalized Lucasnomial Fuss-Catalan numbers C_{U,r,s}(t) have a positive p-adic valuation if st > 1. Indeed, the proof of Theorem 1 shows that for s ≥ 2 and t ≥ 2, ν_{p}(C_{U,r,s}(t)) > 0. If t = 1 and s ≥ 2, then, from (12), we see that ν_{p}(C_{U,r,s}(t)) ≥ ν_{p}(U_{s}), and ν_{p}(U_{s}) ≥ ⌊s/2⌋ > 0 by (2) or (3). If s = 1 and t ≥ 2, then, by [3, eq. (14)],

C_{U,r,s}(t) = \binom{rt − 1}{t − 1}_{U} − Q\frac{U_{(r−1)t}}{U_{t}} \binom{rt − 1}{t − 2}_{U}.  (17)

Noting that Theorem 1 implies that, for m and n positive, \binom{m+n}{n}_{U} has positive valuation, the first Lucasnomial on the RHS of (17) has positive p-valuation. Moreover, U being a divisible sequence U_{(r−1)t}/U_{t} is an integer and ν_{p}(Q) > 0. Hence, the second term on the RHS of (17) also has positive valuation.

Generalized Lucasnomial Lobb numbers and generalized Lucasnomial ballot numbers were shown to be integers under the hypothesis that U(P, Q) be regular [3]. The restriction that U be regular can now be removed. Thus, we have the two corollaries.

Corollary 8. The generalized Lucasnomial Lobb numbers

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

are integral for all nondegenerate fundamental Lucas sequences U = U(P, Q), all integers a ≥ 1 and m > s ≥ 0.

Proof. As shown in the proof of [3, Thm. 12], each Lobb number is a generalized Lucasnomial Fuss-Catalan number.

Corollary 9. The generalized Lucasnomial ballot numbers

B_{U}(s, t) = \frac{U_{s−t}}{U_{s+t}} \binom{s + t}{t}_{U}

are integral for all nondegenerate fundamental Lucas sequences U = U(P, Q) and all integers s > t ≥ 0.

Proof. Setting v = s − t we see that

B_{U}(s, t) = \frac{U_{s−t}}{U_{s+t}} \binom{s + t}{t}_{U} = \frac{U_{s−t}}{U_{t}} \binom{s + t − 1}{t − 1}_{U}

= \frac{U_{v}}{U_{t}} \binom{2t + v − 1}{t − 1}_{U},

which, by (12), is the generalized Lucasnomial Fuss-Catalan number C_{U,2,v}(t). Thus the result follows from Theorem 1.

5 Acknowledgments

We thank the referee and the editor-in-chief for their formal recommendations which hopefully will have helped make this calculatory paper more reader-friendly.

References

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

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

[3] C. Ballot, Lucasnomial Fuss-Catalan numbers and related divisibility questions, J. Integer Sequences 21 (2018), Article 18.6.5.

[4] C. Ballot, The p-adic valuation of Lucas sequences when p is a special prime, Fibonacci Quart. 57 (2019), 265–275, 366.

[5] C. Bennett, J. Carrillo, J. Machacek, and B. Sagan, Combinatorial interpretations of Lucas analogues of binomial coefficients and Catalan numbers, preprint, 2018. Available

at http://arxiv.org/abs/1809.09036.

[6] C. Bennett, J. Carrillo, J. Machacek, and B. Sagan, Combinatorial interpretations of Lucas analogues of binomial coefficients and Catalan numbers, Ann. Comb. 24 (2020), 503–530.

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

[8] H. 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.

[9] R. Graham, D. Knuth and O. Patashnik, Concrete Mathematics, Second Edition, Addison-Wesley Publishing Company, 1989 (June 2013 Printing).

[10] H. Hu and Z.-W. Sun, An extension of Lucas’ theorem, Proc. Amer. Math. Soc. 129 (2001), 3471–3478.

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

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

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

[14] É. Lucas, Théorie des Nombres, Éditions Jacques Gabay, 1991. (Authorized re-edition of the original 1891 Gauthier-Villars edition.)

[15] P. Phunphayap and P. Pongsriiam, Explicit formulas for the p-adic valuations of Fibonomial coefficients, J. Integer Sequences 21 (2018), Article 18.3.1.

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

[17] R. Stanley, Catalan Numbers, Cambridge University Press, 2015.

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

2010 Mathematics Subject Classification: Primary 11B65; Secondary 11B39. Keywords: generalized binomial coefficient, p-adic valuation, Lucas sequence, generalized Catalan number, Kummer’s rule.

Received July 3 2020; revised versions received December 12 2020; December 31 2020. Published in Journal of Integer Sequences, December 31 2020.

Return to Journal of Integer Sequences home page.