The p-adic Order of Some Fibonomial Coefficients

Diego Marques Departamento de Matemática Universidade de Brasília Brasília 70910-900 Brazil

                   diego@mat.unb.br

Pavel Trojovský Department of Mathematics Faculty of Science University of Hradec Králové Rokitanského 62 Hradec Králové 50003 Czech Republic

                pavel.trojovsky@uhk.cz

Abstract

In this paper, we consider the Fibonomial coefficients, a natural generalization of the binomial coefficients. We generalize a 2013 result of the authors and J. Sellers by proving an exact divisibility result for Fibonomial coefficients involving powers of primes and confirming a recent conjecture.

1 Introduction

Let (F_{n})_{n≥0} be the Fibonacci sequence given by the recurrence relation F_{n+2} = F_{n+1} + F_{n}, with F_{0} = 0 and F_{1} = 1. These numbers are well-known for possessing amazing properties (consult book [5] to find additional references and history).

In 1915, Fontené published a one-page note [1] suggesting a generalization of binomial coefficients, replacing the natural numbers by the terms of an arbitrary sequence (A_{n}) of real or complex numbers.

Since at least the 1960s, there has been much interest in the Fibonomial coefficients \left[{m \atop k}\right]_{F}, which correspond to the choice A_{n} = F_{n}. Hence Fibonomial coefficients are defined, for 1 ≤ k ≤ m, by

\left[{m \atop k}\right]_{F} := \frac{F_{m−k+1} ⋯ F_{m−1}F_{m}}{F_{1} ⋯ F_{k}} ,  (1)

and for k > m, \left[{m \atop k}\right]_{F} = 0. (For example, see Gould [2] as well as numerous papers referenced therein.) It is surprising that this quantity will always take integer values.

Some authors have been interested in searching for divisibility properties of Fibonomial coefficients. For instance, in 1974, Gould [3] proved several such properties where one of them is an analogous to Hermite’s identity for binomial coefficients.

In recent papers, the authors [13, 14] proved that p | \left[{p^{a+1} \atop p^{a}}\right]_{F} for all integers a ≥ 1 and

p ∈ \{2, 3\}. Subsequently, the authors and Sellers [15] proved that the number \left[{p^{a+1} \atop p^{a}}\right]_{F} is divisible by p for all primes p such that p ≡ −2 or 2 (mod 5) and for all integers a ≥ 1.

Here, we are interested in the highest power of p which divides \left[{p^{a+1} \atop p^{a}}\right]_{F}. Let δ_{i,j} denote the Kronecker delta, equal to 1 if i = j and 0 otherwise. As usual, a^{k} ∥ b means that a^{k} | b, but a^{k+1} ∤ b. Our first result is the following:

Theorem 1. Let p be a prime such that p ≡ −2 or 2 (mod 5). Then p^{⌈(a+δ_{p,2})/2⌉} ∥ \left[{p^{a+1} \atop p^{a}}\right]_{F} , for all integers a ≥ 1.

A paper of the authors and Sellers [15] contained the following conjecture about the remaining cases of p, suggested by the referee.

Conjecture 2. If p ≡ −1 or 1 (mod 5), then \left[{p^{a+1} \atop p^{a}}\right]_{F} is not divisible by p for any integer a ≥ 1.

Note that this conjecture, together with [15, Theorem 1.1] and [15, Proposition 2.4], leads to the following result for all odd primes p

p | \left[{p^{a+1} \atop p^{a}}\right]_{F} for all integers a ≥ 1 ⟺ p = 5 or p ≡ −2 or 2 (mod 5).

In this paper, we also confirm this conjecture. We shall state it for the sake of preciseness.

Theorem 3. Conjecture 2 is true.

We organize this paper as follows. In Section 2, we will recall some useful properties of the Fibonacci numbers such as a result concerning the p-adic order of F_{n}. Section 3 is devoted to the proof of these theorems.

2 Auxiliary results

Before proceeding further, we recall some facts for the convenience of the reader.

Lemma 4. We have

(a) For all primes p, F_{p−( \frac{5}{p})} ≡ 0 (mod p) where (\frac{a}{q}) denotes the Legendre symbol of a with respect to a prime q > 2.

(b) (De Polignac formula) For all n ≥ 1, we have

ν_{p}(n!) = ∑_{j=1}^{∞} ⌊\frac{n}{p^{j}} ⌋ ,

where the p-adic order (or valuation) of r, ν_{p}(r), is the exponent of the highest power of a prime p which divides r.

Item (a) can be proved by using the well-known Binet formula:

F_{n} = \frac{α^{n} − β^{n}}{α − β}, for n ≥ 0,

where α = (1 + \sqrt{5})/2 and β = (1 − \sqrt{5})/2. The proof of item (b) can be found in [16, Theorem 4.2].

Before stating the next lemma, we recall that for a positive integer n, the order (or rank) of appearance of n in the Fibonacci sequence, denoted by z(n), is defined as the smallest positive integer k, such that n | F_{k}. (Some authors also call it the order of apparition, as it was called by Lucas, or the Fibonacci entry point.) There are several results on z(n) in the literature; for example, recently, the first author [7, 8, 9, 10, 11, 12] found closed formulas for this function at some integers related to the Fibonacci and Lucas sequences.

Lemma 5. (Cf. [8, Lemma 2.2 (c)]) If n | F_{m}, then z(n) | m.

Note that Lemma 4 (a) together with Lemma 5 implies that z(p) | p − (\frac{5}{p}) for all primes p ≠ 5. Also, it is well-known that (\frac{5}{p}) = −1 or 1 according to the residue of p modulo 5. More precisely, we have that if p ≠ 5 is a prime, then z(p) | p + 1 if p ≡ −2 or 2 (mod 5) and z(p) | p − 1 otherwise.

Lemma 6. (Cf. [11, Lemma 2.3]) For all primes p ≠ 5, we have that gcd(z(p), p) = 1.

The p-adic order of Fibonacci numbers has been completely characterized, see [4, 6, 18, 19]. For instance, from the main results of Lengyel [6], we extract the following result.

Proposition 7. For n ≥ 1, we have

ν_{2}(F_{n}) = \begin{cases}0, & if n ≡ 1, 2 (mod 3); \\ 1, & if n ≡ 3 (mod 6); \\ 3, & if n ≡ 6 (mod 12); \\ ν_{2}(n) + 2, & if n ≡ 0 (mod 12) \end{cases}

and for any prime p > 2

ν_{p}(F_{n}) = \begin{cases}ν_{p}(n) + ν_{p}(F_{z(p)}), & if n ≡ 0 (mod z(p)); \\ 0, & if n ≢ 0 (mod z(p)). \end{cases}

A proof of a more general result can be found in [6, pp. 236–237 and Section 5].

Now we are ready to deal with the proof of the theorems.

3 Proofs

3.1 Proof of Theorem 1

In order to avoid unnecessary repetition, let us suppose that p > 2 and that a is even (the case p = 2 and when a is odd can be handled in much the same way).

Thus we want to prove that

ν_{p} (\left[{p^{a+1} \atop p^{a}}\right]_{F} ) = ⌈\frac{a}{2}⌉

holds for every odd prime p such that p ≡ −2 or 2 (mod 5) for all integer a ≥ 1.

We start the proof by proceeding exactly as in the beginning of the proof of [15, Theorem 1.1]. However, we shall repeat that argument for the convenience of the reader.

By the definition of the Fibonomial coefficient (1), we have

\left[{p^{a+1} \atop p^{a}}\right]_{F} = \frac{F_{(p−1)p^{a}+1} ⋯ F_{p^{a+1}}}{F_{1} ⋯ F_{p^{a}}} .  (2)

Our goal now is to compare the p-adic order of the numerator and denominator in (2). Since p | F_{n} if and only if z(p) | n (by Proposition 7), we need only to consider the p-adic order of the (p^{a} − 1)/z(p) numbers F_{z(p)}, F_{2z(p)}, F_{3z(p)}, …, F_{p^{a}−1} in the denominator and F_{(p−1)p^{a}+2}, F_{(p−1)p^{a}+2+z(p)}, F_{(p−1)p^{a}+2+2z(p)},…, F_{p^{a+1}−z(p)+1} in the numerator. So, in the first case, we use Proposition 7 to obtain

S_{1} := ν_{p}(F_{1} ⋯ F_{p^{a}})
= ν_{p}(F_{z(p)}) + ν_{p}(F_{2z(p)}) + ⋯ + ν_{p}(F_{p^{a}−1})
= (ν_{p}(z(p)) + ν_{p}(F_{z(p)})) + (ν_{p}(2z(p)) + ν_{p}(F_{z(p)})) + ⋯ + (ν_{p}(p^{a} − 1) + ν_{p}(F_{z(p)}))
= ν_{p}(z(p)) + ν_{p}(2z(p)) + ⋯ + ν_{p}(p^{a} − 1) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)}).  (3)

Note that a is even and z(p) | p + 1 (since p ≡ −2 or 2 (mod 5)). Thus (p^{a} − 1)/z(p) is an integer.

For the p-adic order of the numerator, we proceed as before to get

S_{2} := ν_{p}(F_{(p−1)p^{a}+1} ⋯ F_{p^{a+1}})
= ν_{p}(F_{(p−1)p^{a}+2}) + ⋯ + ν_{p}(F_{p^{a+1}−z(p)+1})
= ν_{p}((p − 1)p^{a} + 2) + ⋯ + ν_{p}(p^{a+1} − z(p) + 1) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)})
= ν_{p}(p(p^{a} − p^{a−1} + z(p) − 2)) + ⋯ + ν_{p}(p(p^{a} − 1)) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)})
= ν_{p}(p^{a} − p^{a−1} + z(p) − 2) + ⋯ + ν_{p}(p^{a} − 1) + \frac{p^{a−1} + 1}{z(p)} +
+ (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)}).  (4)

Observe that there exist several common terms in sums (3) and (4); so combining them we get

S_{2} − S_{1} = \frac{p^{a−1} + 1}{z(p)} − (ν_{p}(1z(p)) + ν_{p}(2z(p)) + ⋯ + ν_{p} (\frac{p^{a} − p^{a−1} − 2}{z(p)}z(p)))
= \frac{p^{a−1} + 1}{z(p)} − ν_{p} ((\frac{p^{a} − p^{a−1} − 2}{z(p)})!) .

Now we shall use the De Polignac formula together with some properties of the fractional part of x, defined by {x} = x − ⌊x⌋. Since, for j ≥ a, we have

p^{j}z(p) ≥ 3p^{a} > p^{a} − p^{a−1} − 2

and after a straightforward calculation, we arrive at

S_{2} − S_{1} = \frac{p^{a−1} + 1}{z(p)} − ∑_{j=1}^{a−1} ⌊\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}⌋

= \frac{p^{a−1} + 1}{z(p)} − ∑_{j=1}^{a−1} (\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}) + ∑_{j=1}^{a−1} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\}

= \frac{2(p^{a} − 1)}{z(p)(p − 1)p^{a−1}} + ∑_{j=1}^{a−1} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} .  (5)

Now let us see what happens with {(p^{a} − p^{a−1} − 2)/(p^{j}z(p))} depending on the parity of j. We have that

\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)} = p^{a−j−1} \frac{(p − 1)}{z(p)} − \frac{2}{p^{j}z(p)}.

Since p ≡ −1 (mod z(p)) and a is even, we obtain

p^{a−j−1}(p − 1) ≡ \begin{cases}2 (mod z(p)), & if 2 | j; \\ p − 1 (mod z(p)), & if 2 ∤ j. \end{cases}

Thus

\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)} ≡ \begin{cases}\frac{2}{z(p)} − \frac{2}{p^{j}z(p)} (mod 1), & if 2 | j; \\ \frac{p−1}{z(p)} − \frac{2}{p^{j}z(p)} (mod 1), & if 2 ∤ j. \end{cases}

Now we use that (p − 1)/z(p) ≡ −2/z(p) (mod 1) (because (p + 1)/z(p) is an integer) together with the facts that {x} = x, if 0 ≤ x < 1, {n + x} = {x} and {n − x} = 1 − {x}, for any positive integer n, to get

\{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} = \begin{cases}\frac{2}{z(p)} (1 − \frac{1}{p^{j}} ) , & if 2 | j; \\ 1 − \frac{2}{z(p)} (1 + \frac{1}{p^{j}} ) , & if 2 ∤ j. \end{cases}

Write A_{1} = {1, 3, 5, …, a − 1} and A_{2} = {2, 4, 6, …, a − 2}. Therefore, the summation in (5) can be written as follows:

∑_{j=1}^{a−1} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} = ∑_{j∈A_{1}} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} + ∑_{j∈A_{2}} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\}

= ∑_{j∈A_{1}} (1 − \frac{2}{z(p)} − \frac{2}{z(p)p^{j}} ) + ∑_{j∈A_{2}} (\frac{2}{z(p)} − \frac{2}{z(p)p^{j}} ) .

After some easy computations, we get

∑_{j=1}^{a−1} \{\frac{p^{a} − p^{a−1} − 2}{p^{j}z(p)}\} = \frac{a}{2} (1 − \frac{2}{z(p)}) − \frac{2p^{1−a} (p^{a} − 1)}{(p^{2} − 1) z(p)} + \frac{a − 2}{z(p)} − \frac{2p^{−a} (p^{a} − p^{2})}{(p^{2} − 1) z(p)}.

Combining this with equality (5) yields

ν_{p} (\left[{p^{a+1} \atop p^{a}}\right]_{F} ) = S_{2} − S_{1} = \frac{2(p^{a} − 1)}{z(p)(p − 1)p^{a−1}} + \frac{−4p + 4p^{1−a} + az(p)(p − 1)}{2z(p)(p − 1)} = \frac{a}{2}.

This completes the proof.

3.2 Proof of Theorem 3

Again, we must compare the p-adic order of the numerator and denominator in (2). Thus, we must only consider the p-adic order of the (p^{a} − 1)/z(p) numbers F_{z(p)}, F_{2z(p)}, …, F_{p^{a}−1} in the denominator and F_{(p−1)p^{a}+z(p)}, F_{(p−1)p^{a}+2z(p)}, …, F_{p^{a+1}−1} in the numerator. So, in the first case, we use Proposition 7 to obtain

S_{1} := ν_{p}(F_{1} ⋯ F_{p^{a}})
= ν_{p}(F_{z(p)}) + ν_{p}(F_{2z(p)}) + ⋯ + ν_{p}(F_{p^{a}−1})
= (ν_{p}(z(p)) + ν_{p}(F_{z(p)})) + (ν_{p}(2z(p)) + ν_{p}(F_{z(p)})) + ⋯ + (ν_{p}(p^{a} − 1) + ν_{p}(F_{z(p)}))
= ν_{p}(z(p)) + ν_{p}(2z(p)) + ⋯ + ν_{p}(p^{a} − 1) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)}).  (6)

Note that z(p) | p − 1 (since p ≡ −1 or 1 (mod 5)). Thus (p^{a} − 1)/z(p) is an integer. For the p-adic order of the numerator, we proceed as before to get

S_{2} := ν_{p}(F_{(p−1)p^{a}+1} ⋯ F_{p^{a+1}})
= ν_{p}(F_{(p−1)p^{a}+z(p)}) + ⋯ + ν_{p}(F_{p^{a+1}−1})
= ν_{p}((p − 1)p^{a} + z(p)) + ⋯ + ν_{p}(p^{a+1} − 1) + (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)})
= ν_{p}((p^{a} − p^{a−1} + z(p)) + ⋯ + ν_{p}(p^{a} − 1) + (\frac{p^{a−1} − 1}{z(p)})
+ (\frac{p^{a} − 1}{z(p)}) ν_{p}(F_{z(p)}).  (7)

Observe that there exist several common terms in sums (6) and (7), so combining them (and using that p ∤ z(p)) we get

S_{2} − S_{1} = \frac{p^{a−1} − 1}{z(p)} − (ν_{p}(z(p)) + ν_{p}(2z(p)) + ⋯ + ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} ) z(p)))
= \frac{p^{a−1} − 1}{z(p)} − (ν_{p}(1) + ⋯ + ν_{p} (\frac{p^{a} − p^{a−1}}{z(p)} ))
= \frac{p^{a−1} − 1}{z(p)} − ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} )!) .

Thus, in order to prove this theorem, it suffices to show that

\frac{p^{a−1} − 1}{z(p)} = ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} )!), for p ≡ ±1 (mod 5),

which yields ν_{p}(\left[{p^{a+1} \atop p^{a}}\right]_{F}) = S_{2} − S_{1} = 0. For that, we shall use Lemma 4 (b). Thus we obtain

ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} )!) = ∑_{j=1}^{∞} ⌊\frac{p^{a−1−j}(p − 1)}{z(p)}⌋ = ∑_{j=1}^{a−1} ⌊\frac{p^{a−1−j}(p − 1)}{z(p)}⌋ + ∑_{j=a}^{∞} ⌊\frac{p^{a−1−j}(p − 1)}{z(p)}⌋ .

Now note that for 1 ≤ j ≤ a − 1, the number p^{a−1−j}(p − 1)/z(p) is an integer. Furthermore, for j ≥ a, we have

0 < \frac{p^{a−1−j}(p − 1)}{z(p)} ≤ \frac{p − 1}{pz(p)} ≤ \frac{p − 1}{3p} < 1,

where we used that z(p) ≥ 3 for any prime p. In conclusion, we get

ν_{p} ((\frac{p^{a} − p^{a−1}}{z(p)} )!) = ∑_{j=1}^{a−1} (\frac{p^{a−1−j}(p − 1)}{z(p)}) = \frac{p^{a−1} − 1}{z(p)}

as desired. The proof is therefore complete.

4 Acknowledgments

The authors wish to thank the referee for helpful comments.

This research was supported by the project Prifino EU CZ. This work was done during a very enjoyable visit of the first author to the Department of Mathematics at University of Hradec Králové. He thanks the people of this institution for their hospitality. He was also supported in part by CNPq (Conselho Nacional de Pesquisa) and FAP-DF (Fundação de Apoio a Pesquisa do Distrito Federal).

References

[1] G. Fontené, Généralisation d’une formule connue, Nouv. Ann. Math. 4 (1915), 112.

[2] H. W. Gould, The bracket function and Fontené–Ward generalized binomial coefficients with application to Fibonomial coefficients, Fibonacci Quart. 7 (1969), 23–40.

[3] H. W. Gould, Generalization of Hermite’s divisibility theorems and the Mann-Shanks primality criterion for s-Fibonomial arrays, Fibonacci Quart. 12 (1974), 157–166.

[4] J. H. Halton, On the divisibility properties of Fibonacci numbers, Fibonacci Quart. 4 (1966), 217–240.

[5] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, 2001.

[6] T. Lengyel, The order of the Fibonacci and Lucas numbers, Fibonacci Quart. 33 (1995), 234–239.

[7] D. Marques, On integer numbers with locally smallest order of appearance in the Fibonacci sequence, Internat. J. Math. Math. Sci. 2011 (2011), Article ID 407643.

[8] D. Marques, On the order of appearance of integers at most one away from Fibonacci numbers, Fibonacci Quart. 50 (2012), 36–43.

[9] D. Marques, The order of appearance of product of consecutive Fibonacci numbers, Fibonacci Quart. 50 (2012), 132–139.

[10] D. Marques, The order of appearance of powers of Fibonacci and Lucas numbers, Fibonacci Quart. 50 (2012), 239–245.

[11] D. Marques, Fixed points of the order of appearance in the Fibonacci sequence, Fibonacci Quart. 51 (2013), 346–351.

[12] D. Marques, Sharper upper bounds for the order of appearance in the Fibonacci sequence. Fibonacci Quart. 51 (2013), 233–238.

[13] D. Marques and P. Trojovský, On parity of Fibonomial coefficients, Util. Math., to appear.

[14] D. Marques and P. Trojovský, On divisibility properties of Fibonomial coefficients by 3, J. Integer Seq. 15 (2012), Article 12.6.4.

[15] D. Marques, J. Sellers, and P. Trojovský, On divisibility properties of certain Fibonomial coefficients by p, Fibonacci Quart. 51 (2013) 78–83.

[16] I. Niven, H. S. Zuckermann, and H. L. Montgomery, An Introduction to the Theory of Numbers, Wiley, 1991.

[17] P. Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory, Springer-Verlag, 2000.

[18] D. W. Robinson, The Fibonacci matrix modulo m, Fibonacci Quart. 1 (1963), 29–36.

[19] J. Vinson, The relation of the period modulo m to the rank of apparition of m in the Fibonacci sequence, Fibonacci Quart. 1 (1963), 37–45.

2010 Mathematics Subject Classification: Primary 11B39. Keywords: generalized binomial coefficient, Fibonacci number, Fibonacci coefficient, order of appearance, p-adic order, divisibility.

Received June 4 2014; revised versions received November 29 2014; December 16 2014; January 16 2015. Published in Journal of Integer Sequences, January 26 2015.

Return to Journal of Integer Sequences home page.