On Divisibility of Fibonomial Coefficients by 3

Diego Marques Departamento de Matemática Universidade de Brasília Brasília, DF Brazil

                   diego@mat.unb.br

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

                pavel.trojovsky@uhk.cz

Abstract

Let F_{n} be the nth Fibonacci number. For 1 ≤ k ≤ m − 1 let

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

be the corresponding Fibonomial coefficient. In this paper, we present some divisibility properties of \left[{sn \atop n}\right]_{F} by 3, for some positive integers n and s. In particular, among other things, we prove that 3 | \left[{3^{a+1} \atop 3^{a}}\right]_{F} , for all a ≥ 1.

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 [7] together with its very extensive annotated bibliography for additional references and history).

In 1915 Fontené published a one–page note [3] 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 1964, there has been an accelerated interest in the Fibonomial coefficients \left[{m \atop k}\right]_{F}, which correspond to the choice A_{n} = F_{n}, thus are defined, for 1 ≤ k ≤ m, in the following way

\left[{m \atop k}\right]_{F} = \frac{F_{m}F_{m−1} ⋯ F_{m−k+1}}{F_{1} ⋯ F_{k}} .

It is surprising that this quantity will always take integer values. This can be shown by an induction argument and the recursion formula

\left[{m \atop k}\right]_{F} = F_{k+1}\left[{m − 1 \atop k}\right]_{F} + F_{m−k−1}\left[{m − 1 \atop k − 1}\right]_{F} ,

which is a consequence of the formula F_{m} = F_{k+1}F_{m−k} + F_{k}F_{m−k−1}.

Several authors became interested in the divisibility properties of binomial coefficients. Among several interesting results on this subject, we mention the following facts:

• An integer n ≥ 2 is prime if and only if all the binomial coefficients \binom{n}{1}, …, \binom{n}{n−1} are divisible by n.

• A surprising result, proved by D. Singmaster [13], is that any integer divides almost all binomial coefficients. More precisely, let d be an integer and let f(N) be the number of binomial coefficients \binom{n}{k} divisible by d, with n < N. Then

lim_{N→∞} \frac{f(N)}{N(N + 1)/2} = 1.

Since there are N(N + 1)/2 binomial coefficients \binom{n}{k}, with n < N, the density of the set of binomial coefficients divisible by d is 1.

• Recently Zhi-Wei Sun [16] proved, for example, that for any positive integers k, ℓ and n the following holds

ℓn + 1 | k\binom{kn + ℓn}{ℓn}.

Other interesting results concerning divisibility properties of binomial coefficients can be found in [2, 4]. For example the following holds: 3 | \binom{sn}{n}, for all n ≥ 1 if and only if 3 | s.

In a very recent paper, the authors [10] proved, among other things, that 2 | \left[{2n \atop n}\right]_{F} for all integers n > 1. However, the same is not valid when we replace 2 by 3, as can be seen by the example 3 ∤ \left[{3·2 \atop 2}\right]_{F} = 40.

In this paper, we shall study similar problems for the Fibonomial coefficients. Thus we shall deal with the divisibility of \left[{sn \atop n}\right]_{F} by 3 for some positive integers n and s.

Our first result gives a necessary and sufficient condition for that 3 | \left[{3n \atop n}\right]_{F}.

Theorem 1. We have 3 ∤ \left[{3n \atop n}\right]_{F} if and only if n = 1 or n = 2 · 3^{k} for k ≥ 0.

As we said before, we have 3 | \binom{sn}{n} for all n ≥ 1 if and only if 3 | s. Our next theorem gives a related result in the Fibonomial context.

Theorem 2. Let s > 0 be an integer. The number \left[{sn \atop n}\right]_{F} is a multiple of 3 for all n ≥ 1 if and only if s ≡ 0 (mod 12).

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 3-adic order of F_{n}. Sections 3 and 4 are devoted to the proof of Theorems 1 and 2, respectively.

2 Auxiliary results

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

Lemma 3. We have

(a) F_{n} | F_{m} if and only if n | m.

(b) If m > k > 1, then

\left[{m \atop k}\right]_{F} = \frac{F_{m}}{F_{k}} \left[{m − 1 \atop k − 1}\right]_{F} .

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) follows directly from definition (1). We refer the reader to [1, 6, 15, 11] for more properties and additional bibliography.

The p-adic order (or valuation) of r, ν_{p}(r), is the exponent of the highest power of a prime p which divides r. The p-adic order of Fibonacci numbers was completely characterized, see [5, 9, 12, 14]. For instance, from the main results of Lengyel [9], we extract the following result.

Lemma 4. For n ≥ 1, we have

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

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

Lemma 5. For any integer k ≥ 1 and p prime, we have

\frac{k}{p − 1} − ⌊\frac{log k}{log p}⌋ − 1 ≤ ν_{p}(k!) ≤ \frac{k − 1}{p − 1},  (2)

where, as usual, ⌊x⌋ denotes the largest integer less than or equal to x.

Proof. Recall the well-known Legendre formula [8]:

ν_{p}(k!) = \frac{k − s_{p}(k)}{p − 1},  (3)

where s_{p}(k) is the sum of digits of k in base p. Since k has ⌊log k/ log p⌋ + 1 digits in base p, and each digit is at most p − 1, we get

1 ≤ s_{p}(k) ≤ (p − 1) (⌊\frac{log k}{log p}⌋ + 1) .  (4)

Therefore, the inequality in (2) follows from (3) and (4).

Now we are ready to deal with the proofs of our theorems.

3 Proof of Theorem 1

In order to make our proof clearer, we shall split the statement of Theorem 1 in four propositions.

Proposition 6. (The “if” part) For all integers k ≥ 0, we have that 3 ∤ \left[{2·3^{k+1} \atop 2·3^{k}}\right]_{F}.

Proof. Using the definition of the Fibonomial coefficients, we have

\left[{2 · 3^{k+1} \atop 2 · 3^{k}}\right]_{F} = ∏_{i=1}^{2·3^{k}} \frac{F_{2·3^{k+1}−2·3^{k}+i}}{F_{i}} = ∏_{i=1}^{2·3^{k}} \frac{F_{4·3^{k}+i}}{F_{i}}

and hence

ν_{3} (\left[{2 · 3^{k+1} \atop 2 · 3^{k}}\right]_{F} ) = ν_{3} (∏_{i=1}^{2·3^{k}} \frac{F_{4·3^{k}+i}}{F_{i}} ) = ∑_{i=1}^{2·3^{k}} (ν_{3} (F_{4·3^{k}+i}) − ν_{3} (F_{i})).

Thus, for proving that the assertion holds, it suffices to show that ν_{3} (F_{i}) = ν_{3} (F_{4·3^{k}+i}) for all i = 1, 2, …, 2 · 3^{k}. Since 4 · 3^{k} + i ≡ i (mod 4) and 3 | F_{n} if and only if 4 | n (Lemma 3 (a)), we need only to consider the case when 4 | i, that is, when i = 4t_{i}, for some positive integer t_{i}. From this fact together with Lemma 4, we obtain

ν_{3}(F_{i}) = ν_{3}(F_{4t_{i}}) = ν_{3}(t_{i}) + 1

while

ν_{3}(F_{4·3^{k}+i}) = ν_{3}(F_{4(3^{k}+t_{i})}) = ν_{3}(3^{k} + t_{i}) + 1 = ν_{3}(t_{i}) + 1,

where in the last equality above, we used that t_{i} < 3^{k} (since 4t_{i} = i ≤ 2 · 3^{k}) and the clear identity ν_{p}(a + b) = min{ν_{p}(a), ν_{p}(b)}, when ν_{p}(a) ≠ ν_{p}(b), where p is any prime. This completes the proof.

For the “only if” part, we have

Proposition 7. For all integers a ≥ 2 and k ≥ 1, we have that 3 | \left[{2^{a}·3^{k+1} \atop 2^{a}·3^{k}}\right]_{F}.

Proof. By Lemma 3 (b), we can write

\left[{2^{a} · 3^{k+1} \atop 2^{a} · 3^{k}}\right]_{F} = \frac{F_{2^{a}·3^{k+1}}}{F_{2^{a}·3^{k}}} \left[{2^{a} · 3^{k+1} − 1 \atop 2^{a} · 3^{k} − 1}\right]_{F}

and so it suffices to prove that 3 | F_{2^{a}·3^{k+1}}/F_{2^{a}·3^{k}}. Indeed, using Lemma 4 and the fact that a ≥ 2 to get

ν_{3} (\frac{F_{2^{a}·3^{k+1}}}{F_{2^{a}·3^{k}}} ) = ν_{3}(F_{2^{a}·3^{k+1}}) − ν_{3}(F_{2^{a}·3^{k}}) = ν_{3}(2^{a} · 3^{k+1}) − ν_{3}(2^{a} · 3^{k}) = 1.

Proposition 8. For all integers a ≥ 1, we have that 3 | \left[{3^{a+1} \atop 3^{a}}\right]_{F}.

Proof. Let us suppose, without loss of generality, that a is even (the case of a odd can be handled in much the same way). Since 3 | \left[{27 \atop 9}\right]_{F}, we may assume that a > 2. By definition of the Fibonomial coefficient, we have

\left[{3^{a+1} \atop 3^{a}}\right]_{F} = \frac{F_{3^{a+1}} ⋯ F_{2·3^{a}+1}}{F_{1} ⋯ F_{3^{a}}} .

So we must to compare the 3-adic order of the numerator and denominator of the previous fraction. Since 3 | F_{n} if and only if 4 | n, we need only to consider the 3-adic order of the ⌊3^{a}/4⌋ numbers F_{4}, …, F_{3^{a}−1}, for the denominator, and F_{2·3^{a}+2}, …, F_{3^{a+1}−3}, for the numerator. So, in the first case, we use Lemma 4 to obtain

S_{1} := ν_{3}(F_{1} ⋯ F_{3^{a}})
= ν_{3}(F_{4}) + ν_{3}(F_{8}) + ⋯ + ν_{3}(F_{3^{a}−1})
= (ν_{3}(4) + 1) + (ν_{3}(8) + 1) + ⋯ + (ν_{3}(3^{a} − 1) + 1)
= ν_{3}(4) + ν_{3}(8) + ⋯ + ν_{3}(3^{a} − 1) + ⌊\frac{3^{a}}{4} ⌋ .  (5)

We note that (5) could be rewritten as

ν_{3}(F_{1} ⋯ F_{3^{a}}) = ν_{3}(12) + ν_{3}(24) + ⋯ + ν_{3} (12 ⌊\frac{3^{a} − 1}{12}⌋) + ⌊\frac{3^{a}}{4} ⌋
= ν_{3} (⌊\frac{3^{a} − 1}{12}⌋!) + ⌊\frac{3^{a} − 1}{12}⌋ + ⌊\frac{3^{a}}{4} ⌋ .

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

S_{2} := ν_{3}(F_{3^{a+1}} ⋯ F_{2·3^{a}+1}) = ν_{3}(F_{3^{a+1}−3}) + ⋯ + ν_{3}(F_{2·3^{a}+2})
= ν_{3}(3^{a+1} − 3) + ⋯ + ν_{3}(2 · 3^{a} + 2) + ⌊\frac{3^{a}}{4} ⌋
= ν_{3}(3(3^{a} − 1)) + ⋯ + ν_{3}(3(3^{a} − (3^{a−1} − 2))) + ⌊\frac{3^{a}}{4} ⌋
= ν_{3}(3^{a} − 1) + ⋯ + ν_{3}(3^{a} − (3^{a−1} − 2)) +
+ \frac{3^{a−1} + 1}{4} + ⌊\frac{3^{a}}{4} ⌋ .  (6)

Observe that there exist several common terms in sums (5) and (6), so combining them gives

S_{2} − S_{1} = \frac{3^{a−1} + 1}{4} − (ν_{3}(4) + ⋯ + ν_{3}(3^{a} − (3^{a−1} + 3)))
= \frac{3^{a−1} + 1}{4} − (ν_{3}(12) + ⋯ + ν_{3} (12 ⌊\frac{2 · 3^{a−1} − 3}{12}⌋))
= \frac{3^{a−1} + 1}{4} − ⌊\frac{2 · 3^{a−1} − 3}{12}⌋ − ν_{3} (⌊\frac{2 · 3^{a−1} − 3}{12}⌋!) .  (7)

Hence, when a is even, we have

ν_{3} (\left[{3^{a+1} \atop 3^{a}}\right]_{F} ) = \frac{3^{a−1} + 1}{4} − ⌊\frac{2 · 3^{a−1} − 3}{12}⌋ − ν_{3} (⌊\frac{2 · 3^{a−1} − 3}{12}⌋!) .  (8)

The fact that ⌊x⌋ ≤ x yields the following estimate

ν_{3} (\left[{3^{a+1} \atop 3^{a}}\right]_{F} ) ≥ \frac{3^{a−1} + 6}{12} − ν_{3} (⌊\frac{2 · 3^{a−1} − 3}{12}⌋!) .  (9)

By applying Lemma 5 to the 3-adic order in the right-hand side of (9), we obtain

ν_{3} (⌊\frac{2 · 3^{a−1} − 3}{12}⌋!) ≤ \frac{2 · 3^{a−1} − 15}{24}.  (10)

Now, we combine (9) and (10) to derive

ν_{3} (\left[{3^{a+1} \atop 3^{a}}\right]_{F} ) ≥ \frac{3^{a−1} + 6}{12} − \frac{2 · 3^{a−1} − 15}{24} = \frac{27}{24} > 0

as desired. Since 27/24 = 1.125, we actually proved that ν_{3} (\left[{3^{a+1} \atop 3^{a}}\right]_{F} ) ≥ 2, when a > 2 is even.

For the sake of completeness, we remark that the related formula to (8), for a odd is

ν_{3} (\left[{3^{a+1} \atop 3^{a}}\right]_{F} ) = \frac{3^{a−1} − 1}{4} − ⌊\frac{2 · 3^{a−1} − 2}{12}⌋ − ν_{3} (⌊\frac{2 · 3^{a−1} − 2}{12}⌋!) .  (11)

To finish the “only if” case, all that remains is to prove the following.

Proposition 9. For all integers k ≥ 1 and every prime p > 3, we have that 3 | \left[{3pk \atop pk}\right]_{F}.

Proof. To prove this assertion, we take the same approach as in the proof of Proposition 8. Instead of demonstrating the general case, which is notationally complicated, we restrict ourselves to a particular case that captures the exact essence of our idea. For that, we shall consider p ≡ k ≡ 1 (mod 12). Although there are several cases to consider (48 cases depending on the residue of p and k modulo 12), the proofs are very similar.

First, we write

\left[{3pk \atop pk}\right]_{F} = \frac{F_{3pk} ⋯ F_{2pk−1}}{F_{1} ⋯ F_{pk}} .

We note that again, by Lemma 3 (a) (for n = 4), we need to take care only of the following sequences of indexes: 4, 8, …, pk − 1 and 2pk + 2, …, 3pk − 3 which correspond to indexes of the denominator and numerator respectively, having non-zero 3-adic valuation. Thus

M_{1} := ν_{3}(F_{1}F_{2} ⋯ F_{pk}) = ν_{3}(F_{4}) + ν_{3}(F_{8}) + ⋯ + ν_{3}(F_{pk−1})
= (ν_{3}(4) + 1) + ⋯ + (ν_{3}(pk − 1) + 1)
= ν_{3}(4) + ⋯ + ν_{3}(pk − 1) + ⌊\frac{pk}{4} ⌋  (12)

and

M_{2} := ν_{3}(F_{3pk}F_{3pk−1} ⋯ F_{2pk+1})
= ν_{3}(F_{3pk−3}) + ν_{3}(F_{3pk−7}) + ⋯ + ν_{3}(F_{2pk+2})
= ν_{3}(3pk − 3) + ⋯ + ν_{3}(3pk − (pk − 2)) + ⌊\frac{pk}{4} ⌋
= ν_{3}(3(pk − 1)) + ⋯ + ν_{3} (3 (pk − \frac{pk − 10}{3})) + ⌊\frac{pk}{4} ⌋
= ν_{3}(pk − 1) + ⋯ + ν_{3} (pk − \frac{pk − 10}{3}) + \frac{pk − 1}{12} +
+ ⌊\frac{pk}{4} ⌋ .  (13)

Observe that there exist several common terms in sums (12) and (13), thus combining them

M_{2} − M_{1} = \frac{pk − 1}{12} − (ν_{3}(4) + ⋯ + ν_{3} (\frac{2pk + 2}{3}))
= \frac{pk − 1}{12} − (ν_{3}(12) + ⋯ + ν_{3} (12 ⌊\frac{2pk + 2}{36}⌋))
= \frac{pk − 1}{12} − ⌊\frac{2pk + 2}{36}⌋ − ν_{3} (⌊\frac{2pk + 2}{36}⌋!) .  (14)

Hence

ν_{3} (\left[{3pk \atop pk}\right]_{F} ) = \frac{pk − 1}{12} − ⌊\frac{2pk + 2}{36}⌋ − ν_{3} (⌊\frac{2pk + 2}{36}⌋!)
≥ \frac{pk − 5}{36} − ν_{3} (⌊\frac{2pk + 2}{36}⌋!)  (15)
≥ \frac{pk − 5}{36} − \frac{pk − 17}{36}  (16)
= \frac{1}{3} > 0,

where we used that ⌊x⌋ ≤ x (in (15)) and that ν_{3}(⌊(2pk+2)/36⌋!) ≤ (pk−17)/36, by Lemma 5 (in (16)). The proof is then complete.

4 Proof of Theorem 2

Proof. For the “if” part, we write s = 12k, then

\left[{sn \atop n}\right]_{F} = \left[{12kn \atop n}\right]_{F} = \frac{F_{12kn}}{F_{n}} \left[{12kn − 1 \atop n − 1}\right]_{F}.

Now, it suffices to prove that 3 | F_{12kn}/F_{n}. For that we use Lemma 4 to obtain

ν_{3} (\frac{F_{12kn}}{F_{n}} ) = ν_{3}(F_{12kn}) − ν_{3}(F_{n}) = ν_{3}(kn) + 2 − ν_{3}(F_{n})

and so

ν_{3} (\frac{F_{12kn}}{F_{n}} ) = \begin{cases}2 + ν_{3}(kn), & if 4 ∤ n; \\ 1 + ν_{3}(k), & if 4 | n. \end{cases}

Summarizing, we conclude that ν_{3} (F_{12kn}/F_{n}) ≥ 1 and this completes the proof of this case.

Let k be an integer belonging to {1, …, 11}. Suppose that s ≡ k (mod 12), in order to prove the “only if” part, it suffices to exhibit a positive integer N_{k} such that 3 ∤ \left[{sN_{k} \atop N_{k}}\right]_{F}. Of course, N_{k} = 1 is an example of such number for k = 1, 2, 3, 5, 6, 7, 9, 10, 11, because \left[{s \atop 1}\right]_{F} = F_{s} is not a multiple of 3, if 4 ∤ s. We claim that N_{4} = N_{8} = 4 are also examples. In fact, we have

ν_{3} (\left[{4s \atop 4}\right]_{F} ) = ν_{3} (\frac{F_{4s}F_{4s−1}F_{4s−2}F_{4s−3}}{F_{1}F_{2}F_{3}F_{4}} ) = ν_{3} (\frac{F_{4s}}{3} ) = (ν_{3}(4s) + 1) − 1 = 0,

where we used that 3 ∤ s when s ≡ 4, 8 (mod 12).

5 Conclusion

In this paper, we study divisibility properties of the Fibonomial coefficients \left[{m \atop k}\right]_{F} by 3. Among other things, we give necessary and sufficient conditions for \left[{sn \atop n}\right]_{F} being divisible by 3, for some integers s and n. Our method is effective and possibly can be used to work on divisibility by larger primes. However, it is important to get noticed that for each prime, this study brings a lot of particular technicalities.

6 Acknowledgements

The authors would like to express their gratitude to the anonymous referee for his/her corrections and comments. The first author thanks to DPP-UnB, FAP-DF, FEMAT and CNPq-Brazil for financial support. The second author is supported by Specific research 2103 UHKCZ.

References

[1] A. Benjamin and J. Quinn, The Fibonacci numbers—exposed more discretely. Math. Mag. 76 (2003), 182–192.

[2] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589–592.

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

[4] J. W. L. Glaisher., On the residue of a binomial-theorem coefficient with respect to a prime modulus, Quart. J. Pure Appl. Math 30 (1899), 150–156.

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

[6] D. Kalman and R. Mena, The Fibonacci numbers—exposed, Math. Mag. 76 (2003), 167–181.

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

[8] A. M. Legendre, Théorie des Nombres, Firmin Didot Frères, Paris, 1830.

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

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

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

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

[13] D. Singmaster, Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients. J. Lond. Math. Soc. (2) 8 (3) (1964), 555–560.

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

[15] N. N. Vorobiev, Fibonacci Numbers, Birkhäuser, 2003.

[16] Zhi-Wei Sun, On divisibility concerning binomial coefficients, preprint, May 6 2010,

    available at http://arxiv.org/abs/1005.1054.

2000 Mathematics Subject Classification: Primary 11B39. Keywords: Fibonacci number, Fibonomial coefficient, divisibility.

(Concerned with sequences \underline{A000045} and \underline{A144712}.)

Received March 1 2012; revised version received June 11 2012. Published in Journal of Integer Sequences, June 19 2012.

Return to Journal of Integer Sequences home page.