On Some Magnified Fibonacci Numbers Modulo a Lucas Number

Ram Krishna Pandey Department of Mathematics Indian Institute of Technology Patna Patliputra Colony, Patna - 800013 India

                        ram@iitp.ac.in

Abstract Let, as usual, F_{n} and L_{n} denote the nth Fibonacci number and the nth Lucas number, respectively. In this paper, we consider the Fibonacci numbers F_{2}, F_{3}, …, F_{t}. Let n ≥ 1 be an integer such that 4n+2 ≤ t ≤ 4n+5 and m = F_{2n+2} +F_{2n+4} = L_{2n+3}. We prove that the integers F_{2}F_{2n+2}, F_{3}F_{2n+2}, …, F_{t}F_{2n+2} modulo m all belong to the interval [F_{2n+1}, 3F_{2n+2}]. Furthermore, the endpoints of the interval [F_{2n+1}, 3F_{2n+2}] are obtained only by the integers F_{4}F_{2n+2} and F_{4n+2}F_{2n+2}, respectively.

1 Introduction

Let m_{1}, m_{2}, … be positive integers. Cusick and Pomerance [4] discuss the quantity κ where

κ := sup_{x∈(0,1)} min_{i} ∥xm_{i}∥.

Here, for x ∈ ℝ, ∥x∥ is distance to the nearest integer. Observe that if we have a finite number of integers m_{1}, m_{2}, …, m_{n} and

κ_{1} := max_{1≤k≤m/2^{m=m_{j} +m_{l}}} \frac{1}{m} min_{i} |km_{i}|_{m},

where |x|_{m} denotes the absolute value of the absolutely least remainder of x mod m, then by a remark of Haralambis [5] we have that κ = κ_{1}. The quantity κ has become an important quantity now; it is involved in the well-known Lonely Runner conjecture. This conjecture, due to Bienia et al. [2], is stated as follows:

Suppose n runners having nonzero distinct constant speeds run laps on a unitlength circular track. Then there is a time at which all the n runners are simultaneously at least 1/(n + 1) units from their common starting point.

The original form of this conjecture, as given by Wills [8] and Cusick [3], is as follows:

Suppose m_{1}, m_{2}, …, m_{n} be n positive integers. Then κ ≥ 1/(n + 1).

This is an interpretation also due to Liu and Zhu [7]. In the present paper we show that if the integers m_{1}, m_{2}, …, m_{n} in the definition of κ are F_{2}, F_{3}, …, F_{t} and n ≥ 1 be an integer such that 4n + 2 ≤ t ≤ 4n + 5, then

κ ≥ \frac{F_{2n+1}}{F_{2n+2} + F_{2n+4}} .

This also confirms the lonely runner conjecture in the case where the speeds of the runners are F_{2}, F_{3}, …, F_{t}.

2 Main Results

Let M = {F_{2}, F_{3}, …, F_{t}}. Let n ≥ 1 be an integer such that 4n + 2 ≤ t ≤ 4n + 5 and m = F_{2n+2} + F_{2n+4} = L_{2n+3}. The above bound about κ may be obtained using Theorem 5 and κ_{1}. The lonely runner conjecture is also satisfied in the special case n = 0. In this special case the set of speeds may be \{F_{2}\}, \{F_{2}, F_{3}\}, \{F_{2}, F_{3}, F_{4}\}, and \{F_{2}, F_{3}, F_{4}, F_{5}\}. Taking x = \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, and \frac{1}{4} in the definition of κ for the sets \{F_{2}\}, \{F_{2}, F_{3}\}, \{F_{2}, F_{3}, F_{4}\}, and \{F_{2}, F_{3}, F_{4}, F_{5}\}, respectively, we see that the lonely runner conjecture is satisfied.

In this section, we use the following identities and these identities may be found in Koshy [6].

1. Cassini’s identity: F_{n}^{2} − F_{n+1}F_{n−1} = (−1)^{n−1}.

2. F_{n}^{2} + F_{n+1}^{2} = F_{2n+1}.

3. d’Ocagne’s identity: F_{m}F_{n+1} − F_{m+1}F_{n} = (−1)^{n}F_{m−n}.

4. F_{2n} = ∑_{i=0}^{n−1} F_{2i+1}.

5. F_{2n+1} − 1 = ∑_{i=1}^{n} F_{2i}.

Lemma 1. (a) F_{2}F_{2n+2} ≡ F_{4n+5}F_{2n+2} (mod m).

(b) F_{2}F_{2n+2} ≡ −F_{4n+4}F_{2n+2} (mod m).

(c) F_{3}F_{2n+2} ≡ F_{4n+3}F_{2n+2} (mod m).

(d) F_{4}F_{2n+2} ≡ −F_{4n+2}F_{2n+2} (mod m).

Proof. (a) We have

mF_{2n+2} = (F_{2n+2} + F_{2n+4})F_{2n+2}
= F_{2n+2}^{2} + F_{2n+4}F_{2n+2}
= F_{2n+2}^{2} + (F_{2n+3} + F_{2n+2})(F_{2n+3} − F_{2n+1})
= F_{2n+2}^{2} + F_{2n+3}^{2} + F_{2n+3}F_{2n+2} − F_{2n+3}F_{2n+1} − F_{2n+2}F_{2n+1}
= F_{2n+2}^{2} + F_{2n+3}^{2} + (F_{2n+2} + F_{2n+1})F_{2n+2} − F_{2n+3}F_{2n+1} − F_{2n+2}F_{2n+1}
= F_{2n+2}^{2} + F_{2n+3}^{2} + F_{2n+2}^{2} − F_{2n+3}F_{2n+1}
= F_{2n+2}^{2} + F_{2n+3}^{2} + (−1)^{2n+1} (using Cassini’s identity)
= F_{4n+5} − 1 (using the identityF_{n}^{2} + F_{n+1}^{2} = F_{2n+1}) .

Hence we get

F_{4n+5}F_{2n+2} = (1 + mF_{2n+2})F_{2n+2} ≡ F_{2n+2} = F_{2}F_{2n+2} (mod m).

(b) We have

F_{2}F_{2n+2} ≡ F_{4n+5}F_{2n+2} (mod m) (by (a))
= (F_{4n+6} − F_{4n+4})F_{2n+2}
= F_{4n+6}F_{2n+2} − F_{4n+4}F_{2n+2}
= (L_{2n+3}F_{2n+3})F_{2n+2} − F_{4n+4}F_{2n+2} (since L_{n}F_{n} = F_{2n})
≡ −F_{4n+4}F_{2n+2} (mod m) (as m = L_{2n+3}) .

(c) F_{3}F_{2n+2} = (F_{2} + F_{1})F_{2n+2} ≡ (F_{4n+5} − F_{4n+4})F_{2n+2} ≡ F_{4n+3}F_{2n+2} (mod m).

(d) F_{4}F_{2n+2} = (F_{3} + F_{2})F_{2n+2} ≡ (F_{4n+3} − F_{4n+4})F_{2n+2} ≡ −F_{4n+2}F_{2n+2} (mod m).

Lemma 2. F_{r+5}F_{2n+2} = (F_{r+4} + F_{r+3})F_{2n+2} ≡ ϵF_{4n+1−r}F_{2n+2} (mod m) for each 0 ≤ r ≤ 2n − 2, where

ϵ = \{ \begin{matrix}+1, & if r is even; \\ −1, & if r is odd. \end{matrix}

Proof. Using the recurrence relation F_{n+1} = F_{n} + F_{n−1} for n ≥ 1 and Lemma 1, the proof follows by induction on r.

Thus in order to examine the integers F_{2}F_{2n+2}, F_{3}F_{2n+2}, …, F_{4n+5}F_{2n+2} modulo m, it is sufficient to examine only the integers F_{2}F_{2n+2}, F_{3}F_{2n+2}, …, F_{2n+3}F_{2n+2} modulo m. Lemma 3. (a) F_{2}F_{2n+2} ≡ F_{2n+2} (mod m).

(b) F_{3}F_{2n+2} ≡ −F_{2n+3} (mod m).

(c) F_{4}F_{2n+2} ≡ −F_{2n+1} (mod m).

(d) F_{5}F_{2n+2} ≡ 2F_{2n+2} − F_{2n+1} (mod m).

Proof. (a) F_{2}F_{2n+2} ≡ F_{2n+2} (mod m) (as F_{2} = 1).

(b) F_{3}F_{2n+2} = 2F_{2n+2} ≡ −(F_{2n+1} + F_{2n+2}) = −F_{2n+3} (mod m).

(c) F_{4}F_{2n+2} = (F_{2} + F_{3})F_{2n+2} ≡ F_{2n+2} − F_{2n+3} = −F_{2n+1} (mod m).

(d) F_{5}F_{2n+2} = 5F_{2n+2} ≡ 2F_{2n+2} − F_{2n+1} (mod m).

We observe that in all above four congruences if R is the remainder then we have, F_{2n+1} ≤ |R| ≤ \frac{m}{2}, i.e., we have that the positive remainder is always in the interval [F_{2n+1}, 3F_{2n+2}].

Inductively, we can prove that

F_{2n+3−k} = F_{2n−1−k}F_{5} + F_{2n−2−k}F_{4}

for each 0 ≤ k ≤ 2n − 3. Hence we have

F_{2n+3−k}F_{2n+2} = (F_{2n−1−k}F_{5} + F_{2n−2−k}F_{4})F_{2n+2}
≡ F_{2n−1−k}(2F_{2n+2} − F_{2n+1}) − F_{2n−2−k}F_{2n+1} (mod m) (using (c), (d) of Lemma 3)
= F_{2n−1−k}F_{2n+2} + F_{2n−1−k}(F_{2n+1} + F_{2n}) − F_{2n−1−k}F_{2n+1} − F_{2n−2−k}F_{2n+1}
= F_{2n−1−k}F_{2n+2} + F_{2n−1−k}F_{2n} − F_{2n−2−k}F_{2n+1}
= F_{2n−1−k}F_{2n+2} + (−1)^{2n−2−k}F_{2+k} (using d’Ocagne’s identity) .

Thus we get

F_{2n+3−k}F_{2n+2} ≡ F_{2n−1−k}F_{2n+2} + ϵF_{2+k} (mod m), …  (1)

where

ϵ = \{ \begin{matrix}+1, & if k is even; \\ −1, & if k is odd. \end{matrix}

Lemma 4. Let R_{k} = F_{2n−1−k}F_{2n+2} + ϵF_{2+k} for each 0 ≤ k ≤ 2n − 3, where

ϵ = \{ \begin{matrix}+1, & if k is even; \\ −1, & if k is odd. \end{matrix}

Then F_{2n+1} < |R_{k}|_{m} < \frac{m}{2}. Proof. We partition the set {0, 1, 2, …, 2n − 3} into the sets A_{2}, A_{3}, A_{4}, and A_{5} where

A_{i} = \{2n − 1 − i − 4t : 0 ≤ t ≤ ⌊\frac{2n − 1 − i}{4}⌋\} ,

for each 2 ≤ i ≤ 5. Notice that

ϵ = \{ \begin{matrix}+1, & if k ∈ A_{3} ∪ A_{5}; \\ −1, & if k ∈ A_{2} ∪ A_{4}. \end{matrix}

We consider the following cases:

Case I: (k ∈ A_{2}). Clearly (1) implies that

F_{6+4t}F_{2n+2} ≡ F_{2+4t}F_{2n+2} − F_{2n−1−4t} (mod m).

t = 0 ⇒ F_{6}F_{2n+2} ≡ F_{2}F_{2n+2} − F_{2n−1} ≡ F_{2n+2} − F_{2n−1} (mod m). Observe that F_{2n+1} < F_{2n+2} − F_{2n−1} < m/2.

t = 1 ⇒ F_{10}F_{2n+2} ≡ F_{6}F_{2n+2} − F_{2n−5} ≡ F_{2n+2} − F_{2n−1} − F_{2n−5} (mod m). Observe that F_{2n+1} < F_{2n+2} − F_{2n−1} − F_{2n−5} < m/2.

Inductively, we let t = ⌊\frac{2n−3}{4}⌋. In this case k = 1 or k = 3 depending on n is even or odd. If k = 1, then we have

F_{2n+2}F_{2n+2} ≡ F_{2n−2}F_{2n+2}−F_{3} ≡ F_{2n+2}−(F_{2n−1}+F_{2n−5}+⋯+F_{3}) (mod m). Observe that F_{2n+1} < F_{2n+2} − (F_{2n−1} + F_{2n−5} + ⋯ + F_{3}) < m/2 as we have the identity F_{2n} = ∑_{i=0}^{n−1} F_{2i+1}.

If k = 3, then we have F_{2n}F_{2n+2} ≡ F_{2n−4}F_{2n+2} −F_{5} ≡ F_{2n+2} −(F_{2n−1} +F_{2n−5} +⋯+F_{5}) (mod m). Observe that

F_{2n+1} < F_{2n+2} − (F_{2n−1} + F_{2n−5} + ⋯ + F_{5}) < m/2 as we have the identity F_{2n} = ∑_{i=0}^{n−1} F_{2i+1}.

Case II: (k ∈ A_{3}). Clearly (1) implies that

F_{7+4t}F_{2n+2} ≡ F_{3+4t}F_{2n+2} + F_{2n−2−4t} (mod m).

t = 0 ⇒ F_{7}F_{2n+2} ≡ F_{3}F_{2n+2} + F_{2n−2} ≡ −F_{2n+3} + F_{2n−2} (mod m). Observe that F_{2n+1} < | − F_{2n+3} + F_{2n−2}| < m/2.

t = 1 ⇒ F_{11}F_{2n+2} ≡ F_{7}F_{2n+2} + F_{2n−6} ≡ −F_{2n+3} + F_{2n−2} + F_{2n−6} (mod m). Observe that F_{2n+1} < | − F_{2n+3} + F_{2n−2} + F_{2n−6}| < m/2.

Inductively, we let t = ⌊\frac{2n−4}{4}⌋. In this case k = 0 or k = 2 depending on n is even or odd. If k = 0, then we have

F_{2n+3}F_{2n+2} ≡ F_{2n−1}F_{2n+2} + F_{2} ≡ −F_{2n+3} + (F_{2n−2} + F_{2n−6} + ⋯ + F_{2}) (mod m). Observe that F_{2n+1} < |−F_{2n+3}+(F_{2n−2}+F_{2n−6}+⋯+F_{2})| < m/2 as we have F_{2n+3}−(F_{2n−2}+F_{2n−6}+ ⋯ + F_{2}) = F_{2n+1} + F_{2n+2} − (F_{2n−2} + F_{2n−6} + ⋯ + F_{2}) and the identity F_{2n+1} − 1 = ∑_{i=1}^{n} F_{2i}

If k = 2, the result follows from the above case k = 0.

Case III: (k ∈ A_{4}). Clearly (1) implies that

F_{8+4t}F_{2n+2} ≡ F_{4+4t}F_{2n+2} − F_{2n−3−4t} (mod m).

t = 0 ⇒ F_{8}F_{2n+2} ≡ F_{4}F_{2n+2} − F_{2n−3} ≡ −F_{2n+1} − F_{2n−3} (mod m). Observe that F_{2n+1} < F_{2n+1} + F_{2n−3} < m/2.

t = 1 ⇒ F_{12}F_{2n+2} ≡ F_{8}F_{2n+2} − F_{2n−7} ≡ −(F_{2n+1} + F_{2n−3} + F_{2n−7}) (mod m). Observe that F_{2n+1} < F_{2n+1} + F_{2n−3} + F_{2n−7} < m/2.

Inductively, we let t = ⌊\frac{2n−5}{4}⌋. In this case k = 1 or k = 3 depending on n is odd or even. If k = 1, then we have

F_{2n+2}F_{2n+2} ≡ F_{2n−2}F_{2n+2} − F_{3} ≡ −(F_{2n+1} + F_{2n−3} + F_{2n−7} + … + F_{3}) (mod m). Observe that F_{2n+1} + F_{2n−3} + F_{2n−7} + … + F_{3} < m/2 as we have the identity F_{2n} = ∑_{i=0}^{n−1} F_{2i+1}.

If k = 3. It follows from the above case k = 1.

Case IV: (k ∈ A_{5}) Clearly (1) implies that

F_{9+4t}F_{2n+2} ≡ F_{5+4t}F_{2n+2} + F_{2n−4−4t} (mod m).

t = 0 ⇒ F_{9}F_{2n+2} ≡ F_{5}F_{2n+2} + F_{2n−4} ≡ 2F_{2n+2} − F_{2n+1} + F_{2n−4} (mod m). Observe that F_{2n+1} < 2F_{2n+2} − F_{2n+1} + F_{2n−4} < m/2.

t = 1 ⇒ F_{13}F_{2n+2} ≡ F_{9}F_{2n+2}+F_{2n−8} ≡ 2F_{2n+2}−F_{2n+1}+F_{2n−4}+F_{2n−8} (mod m). Observe that F_{2n+1} < 2F_{2n+2} − F_{2n+1} + F_{2n−4} + F_{2n−8} < m/2.

Inductively, we let t = ⌊\frac{2n−6}{4}⌋. In this case k = 0 or k = 2 depending on n is odd or even. If k = 0, then we have

F_{2n+3}F_{2n+2} ≡ F_{2n−1}F_{2n+2} + F_{2} ≡ 2F_{2n+2} − F_{2n+1} + (F_{2n−4} + F_{2n−8} + … + F_{2}) (mod m). Observe that F_{2n+1} < 2F_{2n+2} − F_{2n+1} + (F_{2n−4} + F_{2n−8} + … + F_{2}) < m/2 as we have 2F_{2n+2} − F_{2n+1} + (F_{2n−4} + F_{2n−8} + … + F_{2}) = F_{2n+2} + F_{2n} + (F_{2n−4} + F_{2n−8} + … + F_{2}) < F_{2n+2} + F_{2n+1} − 1 < m/2 using the identity F_{2n+1} − 1 = ∑_{i=1}^{n} F_{2i}

If k = 2. It follows from the above case k = 0.

Theorem 5. Let F_{2}, F_{3}, …, F_{t} be the Fibonacci numbers and let n ≥ 1 be an integer such that 4n + 2 ≤ t ≤ 4n + 5 and m = F_{2n+2} + F_{2n+4} = L_{2n+3}. Then the integers F_{2}F_{2n+2}, F_{3}F_{2n+2}, …, F_{t}F_{2n+2} modulo m all belong to the interval [F_{2n+1}, 3F_{2n+2}]. Moreover, both the endpoints of the interval [F_{2n+1}, 3F_{2n+2}] are obtained only by the integers F_{4}F_{2n+2} and F_{4n+2}F_{2n+2}, respectively.

Proof. Lemma 3 and Lemma 4 together prove the theorem.

3 Acknowledgements

The author wishes to thank to the referees for their useful comments.

References

[1] U. Betke and J. M. Wills, Untere Schranken für zwei diophantische Approximations-Functionen, Monatsh. Math. 76 (1972), 214–217.

[2] W. Bienia, L. Goddyn, P. Gvozdjak, A. Sebo, and M. Tarsi, Flows, view-obstructions and the lonely runner, J. Combin. Theory Ser. B 72 (1998), 1–9.

[3] T. W. Cusick, View-obstruction problems in n-dimensional geometry, J. Combin. Theory Ser. A 16 (1974), 1–11.

[4] T. W. Cusick and C. Pomerance, View-obstruction problems III, J. Number Theory 19 (1984), 131–139.

[5] N. M. Haralambis, Sets of integers with missing differences, J. Combin. Theory Ser. A 23 (1977), 22–33.

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

[7] D. D.-F. Liu and X. Zhu, Fractional chromatic number for distance graphs with large clique size, J. Graph Theory 47 (2004), 129–146.

[8] J. M. Wills, Zwei Sätze über inhomogene diophantische Approximation von Irrationalzahlen, Monatsh. Math. 71 (1967), 263–269.

2010 Mathematics Subject Classification: Primary 11B39. Keywords: Fibonacci numbers, Lucas numbers, congruences.

(Concerned with sequence \underline{A000045}.)

Received September 28 2012; revised version received January 21 2013. Published in Journal of Integer Sequences, January 26 2013.

Return to Journal of Integer Sequences home page.