Average of Generalized Fibonacci Sequence

Abstract

$\quad$ Amirali Fatehizadeh & Daniel Yaqubi answered the question when does we have the average of first $n$ Fibonacci numbers are integer. In this post, I will generalize that result.

1. Introduction

Given two positive integers $a$ and $m$ such that $a-2$ is not divisible by $4$. Let the sequence $(S_n)_{n \in \mathbb{N}}$ defined by $S_0 = 0, S_1 = 1$ and $S_{n+2} = aS_{n+1} - S_n$ for all $n \in \mathbb{N}.$ Then, for each $m$, there exists a positive integer $N$ has $m$ distinct prime divisors such that $$n \mid S_1 + S_2 + \ldots + S_N$$

2. Preliminaries

We consider the sequence $(T_n)_{n \in \mathbb{N}}$ defined by $T_0 = 2, T_1 = a$ and $T_{n+2} = aT_{n+1}-T_n$. As a result, we have $$ S_n = \dfrac{\alpha^n-\beta^n}{\alpha-\beta} \quad \text{ and } \quad T_n = \alpha^n + \beta^n $$ where $\alpha \ge \beta$ are two roots of equation $x^2-ax+1 = 0.$

Lemma 1. From the general formula of $S_n$ and $T_n$, the following holds for all nonnegative integer $n$
  1. $S_{2n} = S_{n} T_n$.
  2. $S_{2n+1}-1 = S_nT_{n+1}$.

Lemma 2. For a prime number $p$, we always have $p \mid S_{p-(\frac{\Delta}{p})} $ where $\Delta = a^2-{4}$ and $\left(\frac{\bullet}{p}\right)$ is Legendre symbol.

Lemma 3. For a prime number $p$ such that $p \mid S_n $ then $p \mid \dfrac{S_{pn}}{S_n}.$
Proof. For a positive integer $n$ such that $p \mid S_n$, then $$p \mid \dfrac{\alpha^n-\beta^n}{\alpha -\beta}.$$ As a result, there must exist $\mu \in \mathcal{O}_{K}$ where $K = \mathbb{Q}(\alpha)$ such that $\alpha^n-\beta^n =\mu p.$ We also consider $(p) \subset \mathcal{O}_{K}$ be the principal ideal generated by $p$ of $\mathcal{O}_{K}$ and let $c = \alpha^n, d = \beta^n$. From this, we have \begin{align*} \dfrac{S_{pn}}{S_n} &= \dfrac{c^p-d^p}{c-d} \\\\ & = \dfrac{(d+\mu p)^p-d^p}{\mu p} \\\\ & = \dfrac{ \mathop{\sum}\limits_{0\le j \le p}\binom{p}{j}(\mu p)^jd^{p-j} - d^p}{\mu p} \\\\ & = \dfrac{ \mathop{\sum}\limits_{1\le j \le p}\binom{p}{j}(\mu p)^jd^{p-j}}{\mu p} \\\\ & = \mathop{\sum}\limits_{1\le j \le p}\binom{p}{j}(\mu p)^{j-1}d^{p-j} \\\\ & \equiv 0 \pmod{(p)} \end{align*} since $ \binom{p}{j}$ is divisible by $p$ for all $j = \overline{1,p-1}.$

As a consequence, we have the following corollary:

Corollary. For a prime $p$ such that $p \mid S_{k}$ then $p^{n+1} \mid S_{kp^n}$ for all $n \in \mathbb{N}.$

3. Main result

Consider the case $m = 1.$ Then, we only need to choose $N = p$ where $p$ is a prime divisor of $\Delta$ then of course, we have $$p \mid S_{p - (\frac{\Delta}{p})} = S_p.$$

Now, we consider the case $m \geq 2.$

Then, we denote $p_1,p_2,\dots, p_m$ are $m$ first primes and we choose $N = 2M$ where $M = (p_1p_2\cdots p_m)^{p_m}$ which give ours the following result: $$ \begin{align*} S_1+\ldots+S_n &= \sum_{i = 1}^n \dfrac{\alpha^n-\beta^n}{\alpha-\beta} \\ &= \dfrac{\dfrac{ \alpha^{n+1}-1}{\alpha-1} - \dfrac{\beta^{n+1}-1}{\beta-1}}{\alpha-\beta} \\ &= \dfrac{(\beta-1)(\alpha^{n+1}-1)-(\alpha-1)(\beta^{n+1}-1)}{(\alpha-\beta)(\alpha-1)(\beta-1)} \\ &= \dfrac{\alpha^n-\beta^n+\alpha-\beta-(\alpha^{n+1}-\beta^{n+1})}{(\alpha-\beta)(2-a)} \\ &= \dfrac{S_{n+1}-1-S_{n}}{a-2} \\ &= \dfrac{S_M(T_{M+1}-T_M)}{a-2}. \end{align*} $$ Note that $T_0 \equiv T_1 \equiv 2 \pmod{a-2}$ so by induction, $T_n \equiv 2 \pmod{a-2}$ for all nonnegative integer $n$. Therefore, $S_1+\ldots+S_n$ is divisible by $n$ is equivalent to $2M \mid S_M$.

Now, consider $p_1 = 2$ then since $a-2$ is not divisible by 4 so $S_2=a$ or $S_3=a^2-1$ is divisible by 4. From this and following lemma 3, we derive that $2^{p_m+1} \mid S_M$. On the other hand, we fix an index $i \ge 2$ then there must exist nonnegative integer numbers $\alpha_{j,i}$ less than $p_m$ for all $j = \overline{1,i}$ such that $$p_i - \left( \frac{\Delta}{p} \right) = p_1^{\alpha_{1,i}} p_2^{\alpha_{2,i}}\cdots p_{i-1}^{\alpha_{i-1,i}} p_i^{\alpha_{i,i}}$$ with note that $\alpha_{i,i} \le 1$. Therefore following from lemma, we see that $$ p_i \mid S_{p - \left(\frac{\Delta}{p}\right)} = S_{p_1^{\alpha_{1,i}}p_2^{\alpha_{2,i}}\cdots p_{i-1}^{\alpha_{i-1,i}}p_i^{\alpha_{i,i}}} $$ so $$ p_i^{p_m} \mid S_{p_1^{\alpha_{1,i}}\cdot p_2^{\alpha_{2,i}}\cdots p_{i-1}^{\alpha_{i-1,i}}p_i^{\alpha_{i,i}+p_m-1}} \mid S_{(p_1p_2\ldots p_m)^{p_m}} = S_K $$

Therefore, we derive that $$2M = 2(p_1p_2\cdots p_m)^{p_m} \mid S_M$$ as desired.

4. Conclusion

I generalized the reference problem by considering the extension of algebraic number field. On the other hand, on the aforementioned paper, Amirali Fatehizadeh & Daniel Yaqubi also conjectured that for infinitely many odd numbers $n$ also satisfied the problem. This was proved recently by Oisın Flynn-Connolly. Therefore, if I have time, I will consider to extend the result for odd positive integer in a similar way.

References

[1] Fatehizadeh, A., & Yaqubi, D. (2022). Average of the Fibonacci Numbers. Journal of Integer Sequences, 25(2), Article 22.2.6, 10 pp. Retrieved from https://cs.uwaterloo.ca/journals/JIS/VOL25/Yaqubi/yaq6.html

[2] Flynn-Connolly, O. (2025). On the divisibility of sums of Fibonacci numbers (arXiv:2504.09938). arXiv. https://arxiv.org/abs/2504.09938