Tribonacci Numbers and the Brocard-Ramanujan Equation

Vinícius Facó and Diego Marques Departamento de Matemática Universidade de Brasília Brasília 70910-900 Brazil

                      vinicius@mat.unb.br
                       diego@mat.unb.br

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 short note, we prove that there are no integer solutions (u, m) to the Brocard-Ramanujan equation m! + 1 = u^{2} where u is a Tribonacci number.

1 Introduction

In the past few years, several authors have considered Diophantine equations involving factorial numbers. For instance, Erdős and Selfridge [6] proved that n! is a perfect power only when n = 1. However, the most famous among such equations was posed by Brocard [5] in 1876 and independently by Ramanujan ([17], [18, p. 327]) in 1913. The Diophantine equation

m! + 1 = u^{2}  (1)

is now known as Brocard-Ramanujan Diophantine equation.

It is a simple matter to find the three known solutions, namely m = 4, 5 and 7. Recently, Berndt and Galway [2] showed that there are no further solutions with m ≤ 10^{9}. An interesting contribution to the problem is due to Overholt [15], who showed that the equation (1) has only finitely many solutions if we assume a weak version of the abc conjecture. However, the Brocard-Ramanujan equation is still an open problem.

Let (F_{n})_{n≥0} be the Fibonacci sequence (sequence \underline{A000045} in the OEIS [19]) given by F_{0} = 0, F_{1} = 1 and F_{n+2} = F_{n+1} + F_{n}, for n ≥ 0.

A number of mathematicians have been interested in Diophantine equations that involve both factorial and Fibonacci numbers. For example, Grossman and Luca [8] showed 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}. Also, all the solutions for the case k ≤ 2 were determined. Later, Bollman, Hernández and Luca [3] solved the case k = 3. In a recent paper, Luca and Siksek [11] found all factorials expressible as the sum of at least three Fibonacci numbers.

In 1999, Luca [10] proved that F_{n} is a product of factorials only when n = 1, 2, 3, 6 and 12. Also, Luca and Stănică [12] showed that 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!.

In 2012, Marques [13] proved that (m, u) = (4, 5) is the only solution of Eq. (1) where u is a Fibonacci number. His proof depends on the primitive divisor theorem together with factorizations formulas for F_{n} ± 1.

Among the several generalizations of Fibonacci numbers, one of the best known is the Tribonacci sequence (T_{n})_{n≥0} (sequence \underline{A000073} in the OEIS). This 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.

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

Here, we are interested in solutions (m, u) of the Brocard-Ramanujan equation where u is a Tribonacci number. We point out that in this we have neither a primitive divisor theorem for T_{n} nor a factorization formula for T_{n} ± 1.

More precisely, we shall prove the following theorem.

Theorem 1. There is no solution (m, u) for the Brocard-Ramanujan equation (1), where u is a Tribonacci number.

The idea behind the proof is as follows. The equation we are interested in solving is m! = (T_{n} − 1)(T_{n} + 1). The 2-adic valuation of m! is m + O(log m). We show that the 2-adic valuation of (T_{n} − 1)(T_{n} + 1) is ⪅ 8 log n/ log 2. Thus m ⪅ 8 log n/ log 2. This forces m! to be smaller than (T_{n} − 1)(T_{n} + 1), for m and n sufficiently large, which allows us to complete the proof.

2 The proof of Theorem 1

2.1 A key lemma

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 by Lengyel [9]. Also, very recently the 2-adic order of Tribonacci numbers was made explicit by Lengyel and Marques [14]. Here, we shall prove the following key result which will play an important role in the proof of Theorem 1.

Lemma 2. We have

ν_{2}(T_{n} + 1) = \begin{cases}15, & if n = 61; \\ 0, & if n ≡ 0, 3 (mod 4); \\ 1, & if n ≡ 1, 2, 6 (mod 8); \\ 3, & if n ≡ 5 (mod 16); \\ ν_{2}((n + 3)^{2}) − 3, & if n ≡ 13, 29, 45 (mod 64); \\ ν_{2}((n − 61)(n + 3)) − 3, & if n > 61 and n ≡ 61 (mod 64). \end{cases}

and, for n ≥ 5,

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

The case T_{n} − 1:

First, note that Lengyel and Marques [14] proved that T_{n} − 1 is odd for every n ≡ 0, 3 (mod 4), which proves the first case. Now, note that, in order to prove the second case, it suffices to prove that T_{n} ≡ 3 (mod 4). In this case, we have n = 8k + 5, with k ≥ 0. Then we proceed on induction on k. For k = 0, it follows directly, since T_{5} − 1 = 7 − 1 = 6 = 2 · 3. So, we suppose that T_{8k+5} ≡ 3 (mod 4). Using the sum formula for T_{n} (proved by Feng [16]), we have that

T_{8(k+1)+5} = T_{(8k+5)+8}
= T_{6}T_{8k+5} + (T_{6} + T_{5})T_{8k+6} + T_{7}T_{8k+7}
= 13T_{8k+5} + 20T_{8k+6} + 24T_{8k+7}
≡ 3 (mod 4).

In the third case, for t ≥ 6 and s ≥ 1 odd, we write n = 2^{t−3}s + 2. Now, by a Lengyel and Marques result [14, Lemma 3.1], we have that

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

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

The fourth case follows by proceeding in the same way as the third one. For t ≥ 6 and s ≥ 1 odd, we write n = 2^{t−3}s − 2. Then, by the Lengyel and Marques result [14, Lemma 3.1], we have that

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

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

Now, for the last case, we know that 16 divides exactly one among n − 1 and n + 7. Suppose that 16|(n + a), for some a ∈ {−1, 7}. Then ν_{2}(n + b) = 3 for b ∈ {−1, 7} \ {a}. So, we desire to prove that

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

For that, we write n = 2^{t−2}s − a, for t ≥ 5 and s ≥ 1 odd, and proceed as in Lengyel and Marques [14, Lemma 3.1] to prove that

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

Therefore

ν_{2}(T_{n} − 1) = t − 2 = ν_{2}(n + a) + 1,

and this completes the proof.

The case T_{n} + 1:

The first two cases are trivial. The third and the fourth cases follow in the same way. Note that, in order to prove them, it suffices to show that T_{n} ≡ 1 (mod 4) when n ≡ 1, 2, 6 (mod 8) and to show that T_{n} = 7 (mod 16) when n ≡ 5 (mod 16). In order to avoid unnecessary repetitions, we shall prove only one of these cases. So, let us write n = 8k + 6 and apply induction on k ≥ 0. For k = 0, it follows directly, since T_{6}+1 = 13+1 = 14 = 2·7. Now, suppose that T_{8k+6} ≡ 1 (mod 4). Then, we have that

T_{8(k+1)+6} = T_{(8k+6)+8}
= T_{6}T_{8k+6} + (T_{6} + T_{5})T_{8k+7} + T_{7}T_{8k+8}
= 13T_{8k+6} + 20T_{8k+7} + 24T_{8k+8}
≡ 1 (mod 4).

Now, for the the fifth case, note that, if n = 64k + 13,

ν_{2}((n + 3)^{2}) − 3 = 2ν_{2}(n + 3) − 3
= 2ν_{2}(64k + 13 + 3) − 3 = 2ν_{2}(16(4k + 1)) − 3 = 2 · 4 − 3
= 5.

So, it suffices to prove that T_{n} ≡ 31 (mod 64). Again, we proceed on induction. First, observe that T_{13} = 927 ≡ 31 (mod 64). Now, we have that

T_{64(k+1)+13} = T_{(64k+13)+64}
= T_{62}T_{64k+13} + (T_{62} + T_{61})T_{64k+14} + T_{63}T_{64k+15}
≡ −1 + 32T_{64k+14} (mod 64).

But, from the previous case, we have that T_{64k+14} ≡ 1 (mod 4). Then,

T_{64(k+1)+13} ≡ −1 + 32T_{64k+14} (mod 64)
≡ 32 − 1 (mod 64)
≡ 31 (mod 64).

When n ≡ 29, 45 (mod 64), we proceed in the same way.

For the last case, we proceed as for the last case of the previous theorem. Note that 128 divides exactly one among n−61 and n+3. Suppose that 128|(n+a), for some a ∈ {−61, 3}. Then ν_{2}(n + b) = 6 for b ∈ {−61, 3} \ {a}. So, we desire to prove that

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

For that, we write n = 2^{t−2}s − a, for t ≥ 8 and s ≥ 1 odd, and proceed as in Lengyel and Marques [14, Lemma 3.1] to prove that

T_{2^{t−2}s−a} + 1 ≡ 2^{t+1} (mod 2^{t+2}).

Therefore

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

This completes the proof.

Now, we are ready to deal with the proof of the main theorem.

2.2 The proof

If n ≤ 61, a straightforward search shows that there are no solutions. So we shall suppose that n > 61. Then m ≥ 30. Next we use the fact that ν_{2}(m!) ≥ m − ⌊log m/ log 2⌋ − 1 (which is a consequence of the De Polignac’s formula) together with Lemma 2. Then

m − ⌊\frac{log m}{log 2}⌋ − 1 ≤ ν_{2}(m!) = ν_{2}(T_{n} − 1) + ν_{2}(T_{n} + 1)
< ν_{2}((n + 2)(n − 2)(n − 1)(n + 7)(n + 3)^{3}(n − 61)) + 5
≤ 8ν_{2}(n + ω) + 5,

for some ω ∈ {−61, −2, −1, 2, 3, 7}. Thus ν_{2}(n + ω) ≥ (m − ⌊log m/ log 2⌋ − 6)/8. Therefore, 2^{⌊(m−⌊log m/ log 2⌋−6)/8⌋} | (n + ω). In particular, 2^{⌊(m−⌊log m/ log 2⌋−6)/8⌋} ≤ |n + ω| ≤ n + 61 (here we used that n + ω ≠ 0). By applying the log function, we obtain

⌊\frac{1}{8} (m − ⌊\frac{log m}{log 2}⌋ − 6)⌋ ≤ \frac{log(n + 61)}{log 2}.  (2)

On the other hand, (1.83)^{2n−4} < T_{n}^{2} = m! + 1 < 2(m/2)^{m} (the first inequality was proved by Bravo and Luca [4]). So n < 0.9m log(m/2) + 2.6. Substituting this in equation (2), we obtain

⌊\frac{1}{8} (m − ⌊\frac{log m}{log 2}⌋ − 6)⌋ ≤ \frac{log(0.9m log(m/2) + 63.6)}{log 2}.

This inequality yields m ≤ 78. Then n < 0.9 · 78 log(78/2) + 2.6 = 259.782 . . .. Now, we use a simple routine written in Mathematica which does not return any solution in the range 30 ≤ m ≤ 78 and 62 ≤ n ≤ 259. The proof is complete.

3 Acknowledgment

The authors would like to thank CNPq for the financial support and to the editor and the referee for helpful comments.

References

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

[2] B. C. Berndt and W. Galway, The Brocard–Ramanujan diophantine equation n! + 1 = m^{2}, Ramanujan J. 4 (2000), 41–42.

[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] H. Brocard, Question 166, Nouv. Corresp. Math. 2 (1876), 287.

[6] P. Erdős and J. L. Selfridge, The product of consecutive integers is never a power. Illinois J. Math. 19 (1975), 292–301.

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

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

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

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

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

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

[13] D. Marques, Fibonacci numbers at most one away from the product of factorials. Notes on Number Theory and Discrete Mathematics 18 (2012), 13–19.

[14] D. Marques and T. Lengyel, The 2-adic order of the Tribonacci numbers and the equation T_{n} = m!. J. Integer Sequences 17 (2014), Article 14.10.1.

[15] M. Overholt, The Diophantine equation n! + 1 = m^{2}, Bull. London Math. Soc., 25 (1993), 104.

[16] J. Feng, More identities on the tribonacci numbers, Ars Combin. 100 (2011), 73–78.

[17] S. Ramanujan, Question 469, J. Indian Math. Soc. 5 (1913), 59.

[18] S. Ramanujan, Collected Papers, Chelsea, 1962.

[19] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically

    at https://oeis.org.

2010 Mathematics Subject Classification: Primary 11B39, Secondary 11Dxx. Keywords: Fibonacci number, p-adic order, Tribonacci number, Brocard-Ramanujan equation.

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

Received December 22 2015; revised versions received March 15 2016; April 26 2016. Published in Journal of Integer Sequences, April 26 2016.

Return to Journal of Integer Sequences home page.