The 2-adic Order of the Tribonacci Numbers and the Equation T_{n} = m!

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

                   diego@mat.unb.br

Tamás Lengyel Occidental College 1600 Campus Road Los Angeles, CA 90041 USA

                    lengyel@oxy.edu

Abstract

Let (T_{n})_{n≥0} be the Tribonacci sequence defined by the recurrence T_{n+2} = T_{n+1} + T_{n} + T_{n−1}, with T_{0} = 0 and T_{1} = T_{2} = 1. In this paper, we characterize the 2-adic valuation of T_{n} and, as an application, we completely solve the Diophantine equation T_{n} = m!.

1 Introduction

Let (F_{n})_{n≥0} be the Fibonacci sequence given by F_{n+2} = F_{n+1} + F_{n}, for n ≥ 0, where F_{0} = 0 and F_{1} = 1. The first few terms of this sequence are

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

The p-adic order, ν_{p}(r), of r is the exponent of the highest power of a prime p which divides r. The p-adic order of a Fibonacci number was completely characterized; see [9, 17, 18, 26, 28]. For instance, from the main theorem of Lengyel [17], we extract the following facts:

ν_{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}

To prove this, many congruences involving Fibonacci numbers were used (see for instance [10]).

Among the several generalizations of Fibonacci numbers, one of the most known is the Tribonacci sequence (T_{n})_{n≥0}, which is defined by the recurrence T_{n+1} = T_{n} + T_{n−1} + T_{n−2}, with initial values T_{0} = 0 and T_{1} = T_{2} = 1. The first few terms of this sequence are

0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, …

Recall that the Tribonacci numbers have a long history. They were first studied in 1914 by Agronomof [1] and subsequently by many others. The name “Tribonacci” was coined in 1963 by Feinberg [6]. The basic properties of Tribonacci numbers can be found in [11, 22, 27, 29]. For recent papers, we refer the reader to [2, 12, 13, 24, 25] and to a collection [14, 15, 16].

In this paper, we provide a complete description of the 2-adic order of Tribonacci numbers. More precisely, we prove the following result:

Theorem 1. For n ≥ 1, we have

ν_{2}(T_{n}) = \begin{cases}0, & if n ≡ 1, 2 (mod 4); \\ 1, & if n ≡ 3, 11 (mod 16); \\ 2, & if n ≡ 4, 8 (mod 16); \\ 3, & if n ≡ 7 (mod 16); \\ ν_{2}(n) − 1, & if n ≡ 0 (mod 16); \\ ν_{2}(n + 4) − 1, & if n ≡ 12 (mod 16); \\ ν_{2}((n + 1)(n + 17)) − 3, & if n ≡ 15 (mod 16). \end{cases}

A number of mathematicians have been interested in Diophantine equations involving factorial and Fibonacci numbers. For example, in 1999, Luca [19] proved that F_{n} is a product of factorials only when n = 1, 2, 3, 6, 12. Also, the largest product of distinct Fibonacci numbers which is a product of factorials is F_{1}F_{2}F_{3}F_{4}F_{5}F_{6}F_{8}F_{10}F_{12} = 11!; see [21] (a proof of this fact can be achieved by applying the primitive divisor theorem [5]).

Also, in [8] it is shown that if k is fixed, then there are only finitely many positive integers n such that

F_{n} = m_{1}! + m_{2}! + ⋯ + m_{k}!

holds for some positive integers m_{1}, …, m_{k}; furthermore, all the solutions for the case k ≤ 2 have been determined. Later the case k = 3 was also solved; see [3]. In a recent paper, Luca and Siksek [20] found all factorials expressible as the sum of at most three Fibonacci numbers.

However, we point out that, to the best of the authors’ knowledge, the problem of finding all factorials among Tribonacci numbers has not yet been solved. For this problem, the approach of using the primitive divisor theorem does not work, simply because such a theorem for higher order recurrence sequences seems to be out of reach.

Here we use Theorem 1 to solve completely the equation T_{n} = m!. We have

Theorem 2. The only solutions of the Diophantine equation

T_{n} = m!  (1)

in positive integers n, m are

(n, m) ∈ {(1, 1), (2, 1), (3, 2), (7, 4)}.

2 Auxiliary results

Before proceeding further, some considerations will be needed for the convenience of the reader.

From [4, Lemma 1], we can extract the following result.

Lemma 3. For all n ≥ 1, we have that

ϕ^{n−2} ≤ T_{n} ≤ ϕ^{n−1},  (2)

where ϕ = 1.839286 · · ·.

The next result provides an addition formula for Tribonacci numbers (see [7, Section 3]); it plays a crucial role in proving Theorem 1.

Lemma 4. For all integers n, m, with n ≥ 0 and m ≥ 2, we have that

T_{n+m} = T_{m−2}T_{n} + (T_{m−3} + T_{m−2})T_{n+1} + T_{m−1}T_{n+2}.

We require one last fact about ν_{p} in order to complete our proof of Theorem 2.

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},  (3)

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

We refer the reader to [23, Lemma 2.4] for a proof of this result.

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

3 Proof of Theorem 1

In order to prove the first 4 cases of the 2-adic valuation, it suffices to prove the following congruences

(i) T_{n} ≡ 1 (mod 2), if n ≡ 1, 2 (mod 4).

(ii) T_{n} ≡ 2 (mod 4), if n ≡ 3, 11 (mod 16).

(iii) T_{n} ≡ 4 (mod 8), if n ≡ 4, 8 (mod 16).

(iv) T_{n} ≡ 8 (mod 16), if n ≡ 7 (mod 16).

To avoid unnecessary repetitions we shall prove only that T_{n} ≡ 4 (mod 8) if n ≡ 4 (mod 16) (the other cases can be handled in much the same way and we leave them as an exercise to the reader).

Thus, we want to prove that T_{16t+4} ≡ 4 (mod 8), for all t ≥ 0. For that, we shall proceed by induction on t. The basis case, t = 0, follows because T_{4} = 4. Thus, we may suppose that T_{16t+4} ≡ 4 (mod 8). Therefore, we use Lemma 4 to T_{16(t+1)+4} = T_{(16t+4)+16} to obtain

T_{16(t+1)+4} = 1705T_{16t+4} + 2632T_{16t+5} + 3136T_{16t+6}.

Then T_{16(t+1)+4} ≡ 1705 · 4 ≡ 4 (mod 8), where we used that 8 divides both 2632 and 3136. Now, we shall split our proof into three cases:

Case 1. n ≡ 0 (mod 16). To deal with this case, we shall prove the following result:

Lemma 6. For all s ≥ 1 and t ≥ 6, we have that T_{2^{t−3}s} ≡ s2^{t−4} (mod 2^{t−3}).

Proof. We shall use induction on s to prove simultaneously the following congruences

T_{2^{t−3}s} ≡ s2^{t−4} (mod 2^{t−3}), T_{2^{t−3}s−1} ≡ 0 (mod 2^{t−3}), T_{2^{t−3}s+1} ≡ 1 (mod 2^{t−3}). (4)

First, let us deal with the basis case s = 1. So, we desire to prove that, for all t ≥ 6, we have that

T_{2^{t−3}} ≡ 2^{t−4} (mod 2^{t−3}), T_{2^{t−3}−1} ≡ 0 (mod 2^{t−3}), T_{2^{t−3}+1} ≡ 1 (mod 2^{t−3}). (5)

We will use again induction on t. Clearly the congruences hold for t = 6. So, suppose that they are true for t. Then we use Lemma 4 for T_{2^{t−2}} = T_{(2^{t−3}−1)+(2^{t−3}+1)} to obtain

T_{2^{t−2}} = T_{2^{t−3}−1}^{2} + (T_{2^{t−3}−2} + T_{2^{t−3}−1})T_{2^{t−3}} + T_{2^{t−3}}T_{2^{t−3}+1}.  (6)

By using the Tribonacci recurrence, we obtain T_{2^{t−3}−2} ≡ 2^{t−4} + 1 (mod 2^{t−3}). Now, we write T_{2^{t−3}−2} = 1 + 2^{t−4} + a2^{t−3}, T_{2^{t−3}−1} = b2^{t−3}, T_{2^{t−3}} = 2^{t−4} + c2^{t−3} and T_{2^{t−3}+1} = 1 + d2^{t−3}. Then, we get

T_{2^{t−2}} = b^{2}2^{2t−6} + (1 + 2^{t−4} + (a + b)2^{t−3})(2^{t−4} + c2^{t−3}) + (2^{t−4} + c2^{t−3})(1 + d2^{t−3})
≡ 2^{t−4} + c2^{t−3} + 2^{t−4} + c2^{t−3} (mod 2^{t−2})
≡ 2^{t−3} (mod 2^{t−2}),

as desired. Here we used that 2t − 8 ≥ t − 2, since t ≥ 6. We proceed similarly to prove the other congruences in (5). Now, by induction hypothesis, we suppose that the congruences in (4) hold for s. Then, we use exactly the same procedure as before (and Lemma 4) for T_{2^{t−3}(s+1)} = T_{(2^{t−3}s−1)+(2^{t−3}+1)}. We omit the details.

Since 16 | n, then n = 2^{t−3}s, with s odd and t ≥ 7. By Lemma 6, we obtain that ν_{2}(T_{2^{t−3}s}) = t − 4 and then

ν_{2}(T_{n}) = ν_{2}(T_{2^{t−3}s}) = t − 4 = ν_{2}(2^{t−3}s) − 1 = ν_{2}(n) − 1

as desired.

Case 2. n ≡ 12 (mod 16). By (4) together with the Tribonacci recurrence we obtain that T_{2^{t−3}s−4} ≡ s2^{t−4} (mod 2^{t−3}) holds for all s ≥ 1 and t ≥ 6. Since n ≡ −4 (mod 16), then we can write n = 2^{t−3}s − 4, for some t ≥ 7 and s ≡ 1 (mod 2). Then, we apply the previous congruence to get

ν_{2}(T_{n}) = t − 4 = ν_{2}(2^{t−3}s − 4 + 4) − 1 = ν_{2}(n + 4) − 1.

Case 3. n ≡ 15 (mod 16). In this case, we know that 32 divides exactly one among n + 1 and n + 17. Suppose that 32 | n + a, for some a ∈ {1, 17}. Then ν_{2}(n + b) = 4, for b ∈ {1, 17}\{a}, and so, we desire to prove that

ν_{2}(T_{n}) = ν_{2}(n + a) + 1.

For that, we proceed as in the other cases to prove that the following congruence holds, for all s ≥ 1, t ≥ 8 and a ∈ {1, 17}:

T_{2^{t−3}s−a} ≡ s2^{t−2} (mod 2^{t−1})

with n being in the form n = 2^{t−3}s − a. Therefore,

ν_{2}(T_{n}) = ν_{2}(T_{2^{t−3}s−a}) = t − 2 = ν_{2}(n + a) + 1.

This completes the proof. Remark 7. We note that as a starting point one can use a multisection approach (cf. [18]) to discover the underlying structure of the above analysis. Here we applied the 4-section of the ordinary generating function of the sequence (T_{n})_{n≥0}.

We conclude with a

Conjecture 8. For n ≥ n(p) with some multiple π′(p) of the modulo p period π(p) of the Tribonacci sequence T_{n} and some integer constants n(p) > 0, 0 ≤ r = r(p) ≤ p, n_{i} = n_{i}(p), c′_{i} = c′_{i}(p), c_{i,j} = c_{i,j}(p), 1 ≤ i ≤ π′(p), 1 ≤ j ≤ r, we have that

ν_{p}(T_{n}) = c′_{i} + ν_{p} (∏_{j=1}^{r}(n + c_{i,j})) if n ≡ n_{i} (mod π′(p)).

(Note that it is easy to pick c_{i,j}s for i so that ν_{p}(n + c_{i,j}) = 0.)

4 Proof of Theorem 2

If m ≤ 4, one can see that the only solutions are the ones listed in the Theorem 2. So we shall suppose that m ≥ 5. By using Lemma 5 (for p = 2) together with Theorem 1, we deduce that

m − ⌊\frac{log m}{log 2}⌋ − 1 ≤ ν_{2}(m!) = ν_{2}(T_{n})
< ν_{2}(n(n + 1)(n + 4)(n + 17)) − 5 ≤ 4ν_{2}(n + δ) − 5,

for some δ ∈ {0, 1, 4, 17}. Thus ν_{2}(n + δ) ≥ (m − ⌊log m/ log 2⌋ + 4)/4 and therefore, 2^{⌊(m−⌊log m/ log 2⌋+4)/4⌋} divides n + δ. In particular, 2^{⌊(m−⌊log m/ log 2⌋+4)/4⌋} ≤ n + δ ≤ n + 17 and by applying the log function, we obtain

⌊\frac{1}{4} (m − ⌊\frac{log m}{log 2}⌋ + 4)⌋ ≤ \frac{log(n + 17)}{log 2}.  (7)

On the other hand, by Lemma 3, (1.83)^{n−2} < T_{n} = m! < (m/2)^{m} and so n < 1.66m log(m/2)+ 2. Substituting this in (7), we arrive at

⌊\frac{1}{4} (m − ⌊\frac{log m}{log 2}⌋ + 4)⌋ ≤ \frac{log(1.66m log(m/2) + 19)}{log 2}.

This inequality yields m ≤ 32 and then n < 1.66 · 32 log(32/2) + 2 = 149.27 · · ·. Now, we use a simple routine written in Mathematica which (in a few seconds) does not return us any solution in the range 5 ≤ m ≤ 32 and 1 ≤ n ≤ 149. The proof is complete.

5 Acknowledgment

The first author is grateful to FAP-DF and CNPq for the financial support. He also thanks to Matheus Bernardini for nice discussions on the subject. The authors wish to thank the editor and the referee for their helpful comments.

References

[1] M. Agronomof, Sur une suite récurrente, Mathesis 4 (1914), 125–126.

[2] G. Back and M. Caragiu, The greatest prime factor and recurrent sequences, Fibonacci Quart. 48 (2010), 358–362.

[3] M. Bollman, H. S. Hernández, and F. Luca, Fibonacci numbers which are sums of three factorials, Publ. Math. Debrecen 77 (2010), 211–224.

[4] J. J. Bravo and F. Luca, On a conjecture about repdigits in k-generalized Fibonacci sequences, Publ. Math. Debrecen 82 (2013), 623–639.

[5] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n} ± β^{n}, Ann. of Math. 15 (1913), 30–70.

[6] M. Feinberg, Fibonacci-Tribonacci, Fibonacci Quart. 1 (1963), 71–74.

[7] J. Feng, More identities on the Tribonacci numbers, Ars Comb. 100 (2011), 73–78.

[8] G. Grossman and F. Luca, Sums of factorials in binary recurrence sequences, J. Number Theory 93 (2002), 87–107.

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

[10] E. Jacobson. Distribution of the Fibonacci numbers mod 2^{k}, Fibonacci Quart. 30 (1992), 211–15.

[11] J. Klaška, A search for Tribonacci-Wieferich primes, Acta Math. Univ. Ostrav. 16 (2008), 15–20.

[12] J. Klaška, On Tribonacci-Wieferich primes, Fibonacci Quart. 46/47 (2008/09), 290– 297.

[13] J. Klaška, Tribonacci partition formulas modulo m, Acta Math. Sin. (Engl. Ser.) 26 (2010), 465–476.

[14] J. Klaška and L. Skula, The cubic character of the Tribonacci roots, Fibonacci Quart. 48 (2010), 21–28.

[15] J. Klaška and L. Skula, Periods of the Tribonacci sequence modulo a prime p ≡ 1 (mod 3), Fibonacci Quart. 48 (2010), 228–235.

[16] J. Klaška and L. Skula, A note on the cubic characters of Tribonacci roots. Fibonacci Quart. 48 (2010), 324–326.

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

[18] T. Lengyel, Divisibility properties by multisection, Fibonacci Quart. 41 (2003), 72–79.

[19] F. Luca, Products of factorials in binary recurrence sequences. Rocky Mountain J. Math. 29 (1999), 1387–1411.

[20] F. Luca and S. Siksek, Factorials expressible as sums of at most three Fibonacci numbers, Proc. of the Edinburgh Math. Soc. 53 (2010), 679–729.

[21] F. Luca and P. Stănică, F_{1}F_{2}F_{3}F_{4}F_{5}F_{6}F_{8}F_{10}F_{12} = 11!, Port. Math. 63 (2006), 251–260.

[22] P. Y. Lin, De Moivre-type identities for the Tribonacci numbers, Fibonacci Quart. 26 (1988), 131–134.

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

[24] D. Marques, On the intersection of two distinct k-generalized Fibonacci sequences. Mathematica Bohemica 137 (2012), 403–413.

[25] A. Pethő, Fifteen problems in number theory, Acta Univ. Sapientiae Math. 2 (2010), 72–83.

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

[27] W. R. Spickerman, Binet’s formula for the Tribonacci sequence, Fibonacci Quart. 20 (1982), 118–120.

[28] 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.

[29] E. M. Waddill, Some properties of a generalized Fibonacci sequence modulo m, Fibonacci Quart. 16 (1978), 344–353.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B50, 11A07. Keywords: Tribonacci number, divisibility, 2-adic valuation.

(Concerned with sequences \underline{A000073} and \underline{A248174}.)

Received June 30 2014; revised version received October 1 2014. Published in Journal of Integer Sequences, October 3 2014.

Return to Journal of Integer Sequences home page.