Average of the Fibonacci Numbers

Amirali Fatehizadeh Department of Mathematical Sciences Sharif University of Technology Tehran Iran

                 amirali.fatehizadeh@gmail.com

Daniel Yaqubi Department of Computer Science University of Torbat-e Jam Torbat-e Jam Iran

                    daniel yaqubi@yahoo.es

Abstract The arithmetic mean of the first n Fibonacci numbers is not an integer for all n. However, for some values of n, it is. In this paper we consider the sequence of integers n for which the average of the first n Fibonacci numbers is an integer. We prove some interesting properties and present two related conjectures.

1 Introduction

The Fibonacci sequence (F_{n})_{n≥0} is defined by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2; it is sequence \underline{A000045} in the On-Line Encyclopedia of Integer Sequences (OEIS) [11]. Fibonacci numbers have been extensively studied [5, 6]. Numerous fascinating properties are known. For instance, the Fibonacci numbers have a close relation to binomial coefficients:

F_{n+1} = ∑_{i=0}^{⌊ \frac{n}{2} ⌋} \binom{n − i}{i}.

The average of the first n terms of the Fibonacci sequence is not always an integer. For instance, for n = 3 we have (1 + 1 + 2)/3 = 4/3, but for n = 1, 2, 24, 48, …, the quantities

(\frac{1}{n} ∑_{i=1}^{n} F_{i})_{n≥1} are integers.

In this paper, we explore the following question: Which terms of the sequence

A_{F} (n) = (\frac{1}{n} ∑_{i=1}^{n} F_{i})_{n≥1}  (1)

are integers?

We give a characterization of the values of n for which A_{F} (n) is an integer. In other words, we give an implicit necessary and sufficient condition in Theorem 7 and explicit sufficient conditions in the proof of Theorem 9 and in Theorems 10 and 11 on n to make the first n Fibonacci numbers divisible by n. Moreover, we present a construction of finding infinitely many n that satisfy the given conditions. Further, we show that there are infinitely many n for which 6 is a divisor of the sum of the first n Fibonacci numbers.

Finally, we show that A_{F} (p) is not an integer if p is an odd prime number.

Our work is based on the results in [6, 7, 11, 10, 13].

2 Preliminaries

First, we recall some definitions and important theorems [1, 4, 12]. A fundamental identity that we use in this paper is [6, Theorem 5.1]

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

The Lucas numbers (L_{n})_{n≥0}, are defined by the same recurrence relation as the Fibonacci numbers with different initial values (see \underline{A000032}).

L_{0} = 2, L_{1} = 1, L_{n} = L_{n−1} + L_{n−2}, for n ≥ 2.

The following relations between Fibonacci numbers and Lucas numbers can be found in [6]:

F_{4k+1} − 1 = F_{2k}L_{2k+1},  (3)
F_{4k+2} − 1 = F_{2k}L_{2k+2},  (4)
F_{4k+3} − 1 = F_{2k+2}L_{2k+1},  (5)
F_{2k} = F_{k}L_{2k}.  (6)

An integer a is called a quadratic residue modulo p (with p > 2) if p ∤ a and there exists an integer b such that a ≡ b^{2} (mod p). Otherwise, it is called a non-quadratic residue modulo p.

Let p be an odd prime number. The Legendre symbol is a function of a and p defined as

(\frac{a}{p})= \begin{cases}+1, & if a is a quadratic residue modulo p and a ≢ 0 (mod p), \\ −1, & if a is a non-quadratic residue modulo p, \\ 0, & if a ≡ 0 (mod p). \end{cases}

We note that for a prime number p the Legendre symbol, (\frac{5}{p}), is equal to

(\frac{5}{p})= \begin{cases}+1, & if p ≡ ±1 (mod 5), \\ 0, & if p ≡ 0 (mod 5), \\ −1, & if p ≡ ±2 (mod 5). \end{cases}

Consider the sequence of the Fibonacci numbers modulo 8:

0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, …

We observe that the reduced sequence is periodic.

Lagrange [7] proved that this property is true in general, i.e., that the Fibonacci sequence is periodic modulo m for any positive integers m > 1.

Definition 1. For a given positive integer m, we call the least integer such that (F_{n}, F_{n+1}) ≡ (0, 1) (mod m) the (Pisano) period of the Fibonacci sequence modulo m and denote it by π(m).

The sequence π(n) is sequence \underline{A001175} in the OEIS [11].

We recall as a lemma the fixed point theorem of Fulton and Morris [4].

Lemma 2 (Fixed Point Theorem [4]). Let m be a positive integer greater than 1. Then π(m) = m if and only if m = (24)5^{λ−1} for some λ > 0.

For instance, with m = 8 we have π(8) = 12 and α(8) = 6. The 12 terms in the period form two sets of 6 terms. The terms of the second half are 5 times the corresponding terms in the first half (mod 8). For the Lucas sequence F_{n} = U_{n}(P, Q); Robinson [10], we have t ≡ F_{α(m)−1}(−Q) (mod m) is the multiplier between consecutive parts of length α(m) of the period. If the (mod m) order of t is r then π(m) = rα(m). Here F_{n} = U_{n}(1, −1), (P, Q) = (1, −1), α(8) = 6, t = 5, r = 2; thus π(8) = 2 · 6 = 12; Robinson [10]. The 12 terms in the period form two sets of 6 terms. The terms of the second half are 5 times the corresponding terms in the first half (modulo 8). The next definition is

Definition 3. For a given positive integer, we call the least integer such that (F_{n}, F_{n+1}) ≡ σ(0, 1) (mod m) for some positive integer σ the restricted period of the Fibonacci sequence modulo m and denote it by α(m).

Robinson [10] proved the following theorems. Theorem 4.

(i) m | F_{n} if and only if α(m) | n, and (ii) m | F_{n} and m | F_{n+1} − 1 if and only if π(m) | n. Theorem 5. If p is a prime, then

(i) α(p) | (p − (\frac{5}{p})), (ii) if p ≡ ±1 (mod 5), then π(p) | (p − 1), and (iii) if p ≡ ±2 (mod 5), then π(p) | 2(p + 1).

The exponent of the multiplier of the Fibonacci sequence modulo p, t ≡ F_{α(p)−1} (mod p) is \frac{π(p)}{α(p)} and can only take the values 1, 2 and 4.

For a positive integer n and a prime p, the p-adic valuation of n, ν_{p}(n), is the exponent of the highest power of p that divides n.

Legendre’s classical formula for the p-adic valuation of the factorials is well known:

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

We recall Lengyel’s lemma [8] about the p-adic evaluation of Fibonacci numbers in cases p = 2, 3 and 5. Lemma 6 ([8], Lemmas 1 and 2). For all n ≥ 0, we have ν_{5}(F_{n}) = ν_{5}(n). On the other hand,

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

and

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

3 Main results

We focus now on the average of the first n Fibonacci numbers, A_{F} (n). Theorem 7. Let n be a positive integer. Then n | ∑_{i=1}^{n} F_{i} if and only if F_{n+2} ≡ 1 (mod n).

Proof. We have

n | ∑_{i=1}^{n} F_{i} ⟺ ∑_{i=1}^{n} F_{i} ≡ 0 (mod n)
⟺ F_{n+2} − 1 ≡ 0 (mod n)
⟺ F_{n+2} ≡ 1 (mod n).

Lemma 8. Let n be a positive integer. If π(n) = n or π(n) = n + 1, then

n | ∑_{i=1}^{n} F_{i}.

Proof. According to the definition of the period of a Fibonacci sequence, the congruence F_{k} ≡ F_{k+π(m)} (mod m) holds for any integer k. In particular, for k = 1 and k = 2, we have

F_{1} ≡ F_{1+π(n)}(mod n) and F_{2} ≡ F_{2+π(n)} (mod n).

This implies that if π(n) = n + 1, then 1 = F_{1} ≡ F_{n+2} (mod n) and if π(n) = n, then 1 = F_{2} ≡ F_{n+2} (mod n). By Theorem 7 and Identity (2) the statement follows.

Theorem 9. There are infinitely many even numbers n such that

n | ∑_{i=1}^{n} F_{i}.

Proof. Lemma 2 states that for n = (24)5^{k−1} and k ≥ 1, we have π(n) = n. Hence, Lemma 8 implies the theorem.

Theorem 10. Let α be a non-negative integer. Then

3 · 2^{α+3} | ∑_{i=1}^{3·2^{α+3}} F_{i}.  (7)

Proof. According to the Fibonacci identity (2), we have

∑_{i=1}^{3·2^{α+3}} F_{i} = F_{3·2^{α+3}+2} − 1.

It is sufficient to show that 3 · 2^{α+3} | F_{3·2^{α+3}+2} − 1.

By Identities (4) and (6) we have

F_{3·2^{α+3}+2} − 1 = F_{3·2^{α+2}}L_{3·2^{α+2}+2}
= F_{3·2^{α+1}}L_{3·2^{α+1}}L_{3·2^{α+2}+2}
= F_{3·2^{α}}L_{3·2^{α}}L_{3·2^{α+1}}L_{3·2^{α+2}+2}
⋮
= F_{3}L_{3}L_{6} ⋯ L_{3·2^{α}}L_{3·2^{α+1}}L_{3·2^{α+2}+2}.

But F_{3} = 2, L_{3} = 4 and each of L_{6}, …, L_{3·2^{α+1}} are even numbers. Since L_{3·2^{α+2}+2} is divisible by 3, (7) holds.

Next we present a generalization of the previous theorem. Theorem 11. Let α, β and γ be positive integers. For n = 2^{α+3} · 3^{β+1} · 5^{γ} it holds

18 | \frac{1}{n} ∑_{i=1}^{n} F_{i}  (8)

Proof. Consider n = 2^{α+3} · 3^{β+1} · 5^{γ}, then n ≡ 0 (mod 4). Using Identity (2) and (4) we have

∑_{i=1}^{n} F_{i} = F_{2^{α+3}·3^{β+1}·5^{γ}+2} − 1 = F_{2^{α+2}·3^{β+1}·5^{γ}}L_{2^{α+2}·3^{β+1}·5^{γ}+2}  (9)

By Lengyel’s lemma 6 we can write

ν_{2}(F_{2^{α+2}·3^{β+1}·5^{γ}}) = α + 4,
ν_{3}(F_{2^{α+2}·3^{β+1}·5^{γ}}) = β + 2,
ν_{5}(F_{2^{α+2}·3^{β+1}·5^{γ}}) = γ.

In (9) the Lucas factor L_{2^{α+2}·3^{β+1}·5^{γ}+2} is also divisible by 3. This implies

18 | \frac{1}{n} ∑_{i=1}^{n} F_{i},  (10)

which concludes the proof.

Next we show that A_{F} (p) is not an integer for an odd prime number p . Theorem 12. Let p be an odd prime number. Then

p ∤ ∑_{i=1}^{p} F_{i}.  (11)

Proof. Assume that p is an odd prime number such that

p | ∑_{i=1}^{p} F_{i}.

We investigate the cases p = 4k + 1 and p = 4k + 3 separately. We can assume that p > 5.

Case I. Suppose that p = 4k + 1. According to Identities (2) and (5), we have

p | ∑_{i=1}^{p} F_{i} = F_{4k+3} − 1 = F_{2k+2}L_{2k+1}.  (12)

Hence, p | F_{2k+2} or p | L_{2k+1}. Suppose that p | F_{2k+2}. According to the first case of Theorem 5, we have

α(p) | p − (\frac{5}{p})= 4k + 1 − (\frac{5}{4k + 1}).

The first case of Theorem 4 leads to α(p) | 2k + 2. Then

α(p) | 4k + 4 − (4k + 1 − (\frac{5}{4k + 1})) .

This implies

α(p) | 3 + (\frac{5}{4k + 1}).

This is impossible, since (\frac{5}{p})= ±1 .

Now suppose that p | L_{2k+1}. From Identity (6), we have p | F_{4k+2}. So, by Theorems 4 and 5, we have

α(p) | p − (\frac{5}{p})= 4k + 1 − (\frac{5}{4k + 1}),

and α(p) | 4k + 2. This implies

α(p) | 4k + 2 − (4k + 1 − (\frac{5}{4k + 1})) = 1 + (\frac{5}{4k + 1}).

We have again a contradiction, since (\frac{5}{p}) = ±1.

Case II. Now assume that p = 4k + 3. We follow the argument given in Case I. By using Identities (2) and (3), we can write

p | ∑_{i=1}^{p} F_{i} = F_{4(k+1)+1} − 1 = F_{2(k+1)}L_{2(k+1)+1}.  (13)

The prime number p = 4k + 3 must divide F_{2(k+1)} or L_{2(k+1)+1}. Suppose first that p | F_{2(k+1)}. Similarly as in the first case, by Theorems 4 and 5, we have

α(p) | p − (\frac{5}{p})= 4k + 3 − (\frac{5}{4k + 3}),

and α(p) | 2(k + 1) = 2k + 2. This implies

α(p) | 4k + 4 − (4k + 3 − (\frac{5}{4k + 3})) = 1 + (\frac{5}{4k + 3}).

This is impossible, since (\frac{5}{p})= ±1.

Now let p | L_{2(k+1)+1}. From the identity (6), we have p | F_{4k+6}. According to Theorems 4 and 5, we can write

α(p) | p − (\frac{5}{p})= 4k + 3 − (\frac{5}{4k + 3}),

and α(p) | 4k + 6. Then

α(p) | 4k + 6 − (4k + 3 − (\frac{5}{4k + 3})) = 3 + (\frac{5}{4k + 3}).

This is impossible, since (\frac{5}{p})= ±1.

The proof of the result follows immediately from the two cases above.

4 Concluding remarks

We conclude this paper with two interesting conjectures concerning averages of Fibonacci numbers.

Conjecture 13. There are infinitely many odd integers n that divide the sum of the first n Fibonacci numbers.

Conjecture 14. There are infinitely many pairs of positive integers (n, n + 1) such that

n | ∑_{i=1}^{n} F_{i} and n + 1 | ∑_{i=1}^{n+1} F_{i}.

Some values of the Conjectures 13 and 14 are given as sequences \underline{A331976} and \underline{A331977}, respectively. Currently 33 such pairs have been found and given in \underline{A331977}. The first few pairs are (1, 2), (6479, 6480), (11663, 11664), (34943, 34944), (47519, 47520), (51983, 51984).

Most of the results can be easily stated for the average of the first n Lucas numbers with a similar proof (for example, Theorem 11).

We note that the study of the average of related number sequences, as generalized Fibonacci numbers, Pell-Lucas numbers might be lead to interesting results as well.

5 Acknowledgments

The authors would like thank the anonymous referee for her/his careful reading and valuable suggestions. Special thanks go to Beáta Bényi for helpful remarks.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1998.

[2] H. Belbachir and S. Celia, The generalized bi-periodic Fibonacci sequence modulo m, J. Integer Sequences 24 (2021), Article 21.9.4.

[3] T. A. Benjamin and J. Q. Jennifer, Proofs that Really Count: the Art of Combinatorial proof, American Mathematical Society, 2003.

[4] J. Fulton and W. Morris, On arithmetical functions related to the Fibonacci numbers, Acta Arith. 16 (1969), 105–110.

[5] D. E. Knuth, The Art of Computer Programming, Addison–Wesley, 1968.

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

[7] J. L. Lagrange, Oeuvres de Lagrange, Gauthier-Villars, 1882.

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

[9] P. Ribenboim, The Little Book of Big Primes, Springer, 1991.

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

[11] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2021. Available

    at https://oeis.org.

[12] L. Somer and M. Krizek, Fixed points and upper bounds for the rank of appearance in Lucas sequences, Fibonacci Quart. 51 (2013), 291–306.

[13] D. D. Wall Fibonacci series modulo m, Amer. Math. Monthly 67 (1960), 525–532.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B50, 11A07 . Keywords: Fibonacci number, Lucas number, Pisano period, rank of appearance, restricted period.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A001175}, \underline{A111035}, \underline{A124456}, \underline{A331870}, \underline{A331976}, and \underline{A331977}.)

Received July 30 2021; revised version received August 27 2021; November 2 2021; February 7 2022. Published in Journal of Integer Sequences, February 7 2022.

Return to Journal of Integer Sequences home page.