Fibonacci-esque sequences modulo $1$: what is the largest possible infimum?

Question

Let an infinite sequence $S$ be a "Fibonacci-esque sequence" if, for all $n \geq 3, S(n) = S(n-1) + S(n-2).$ We can reduce $S$ modulo $1$ to get a "reduced Fibonacci sequence." These sequences can contain the element $0$, but not the element $1$. For example, the sequence $0.2, 0.6, 0.8, 0.4, 0.2, 0.6, 0.8, 0.4, ...$ is a reduced Fibonacci sequence with infimum $0.2.$ What is the largest possible infimum of a reduced Fibonacci sequence? What about reduced Fibonacci sequences containing only rational numbers?

In one of the answers, a sequence of reduced Fibonacci sequences was presented with infima approaching $\frac{1}{3}$.

The reduced Fibonacci sequence $\frac{19104}{64079}, \frac{39071}{64079}, \color{red}{\frac{58175}{64079}}, \frac{33167}{64079}, \frac{27263}{64079}, \color{red}{\frac{60430}{64079}}, \frac{23614}{64079}, \frac{19965}{64079}, \frac{43579}{64079}, \color{red}{\frac{63544}{64079}}, \frac{43044}{64079}, \frac{42509}{64079}, \frac{21474}{64079}, \color{red}{\frac{63983}{64079}}, \frac{21378}{64079}, \frac{21282}{64079}, \frac{42660}{64079}, \color{red}{\frac{63942}{64079}}, \frac{42523}{64079}, \frac{42386}{64079}, \frac{20830}{64079}, \color{red}{\frac{63216}{64079}}, \frac{19967}{64079}, \frac{19104}{64079}, \frac{39071}{64079}, …$ which contains only rational numbers, has infimum $\frac{19104}{64079}$ and period $23.$ It is best up to denominator $75000$.

The best known cases are those in this conjecture that I made.

I have highlighted all the "big" elements (above three times the infimum) in red, since they seem to have a pattern, appearing every $3$ or $4$ numbers, and this pattern seems worth analyzing.

I conjecture that for irrationals, the bound is $\frac{1}{3},$ and for rationals, the bound is $\frac{2}{3\sqrt{5}}.$

Answer 1

This provides an improved bound on the answer when you're allowed to have irrational values.

Let $\phi=\tfrac{1+\sqrt 5}2$ be the golden ratio. Let $S(1)=\tfrac 1 3+x$ and $S(2)=\tfrac 1 3 - \tfrac x \phi$.

Then $$ S(3)= \tfrac 2 3 + x(1-\tfrac 1\phi) = \tfrac 2 3 + x \phi^{-2}\\ S(4)=1+x(1-\tfrac 2\phi )=1-x \phi^{-3}\\ S(5)=\tfrac 5 3 +x(2-\tfrac 3\phi )=\tfrac 5 3+x \phi^{-4} $$

As you can see, the $x$ term keeps shrinking.

Because the period is even, the terms that are near integers (eg $S(4)$) always have a negative coefficient on $x$ -- so when you reduce modulo 1, you never get terms near 0, just terms near 1/3, 2/3, and slightly below 1.

You can set $x$ as small as you want to get the infinum as close to 1/3 as you want.

Answer 2

Here is the Python program that I used to find the lower bound for rational numbers presented in the main post (now outdated):

import math

target = 203/682 # the previous best

def reduce(i,n):
    if i < n:
        return i
    else:
        return i - n

def checksuccess(n):
    b = math.floor(target*n) + 1
    for i in range(b, n//2 - 1):
        for j in range(2*i+1, n):
            current_1 = i
            current_2 = j
            while current_1 != -1:
                if current_2 < i:
                    break
                elif current_2 == i and reduce(current_1 + i, n) == j:
                    print(i,j,n)
                    break
                else:
                    current_2 = current_1 + current_2
                    current_1 = current_2 - current_1
                    current_2 = reduce(current_2, n)
            else:
                continue
    return 0

for i in range(1000, 10000):
    checksuccess(i)
    if i % 100 == 0:
        print(i)

It finds sequences of rational numbers with denominators between $1000$ and $10000$ that do better than the sequence $\frac{203}{682}, \frac{416}{682}, \color{red}{\frac{619}{682}}, \frac{353}{682}, \frac{290}{682}, \color{red}{\frac{643}{682}}, \frac{251}{682}, \frac{212}{682}, \frac{463}{682}, \color{red}{\frac{675}{682}}, \frac{456}{682}, \frac{449}{682}, \frac{223}{682}, \color{red}{\frac{672}{682}}, \frac{213}{682}, \frac{203}{682}, \frac{416}{682} ...,$ the previous best. It also prints its progress for every $100$ denominators that it completes.

Again, I have highlighted terms in red for pattern finding.

Answer 3

Theorem $1$: Every reduced Fibonacci sequence contains terms less than $\frac{1}{2}$.

Proof: We proceed to prove this by contradiction. Let $S$ be a reduced Fibonacci sequence with no elements less than $\frac{1}{2}.$ Let $m$ be the least positive integer such that S contains elements less than $1 - \frac{1}{2^m}.$ Let $a_n$ be the first element less than $1 - \frac{1}{2^m}.$ Since all elements are above $\frac{1}{2}, a_n + a_{n+1} > 1,$ so $a_{n+2} = a_n + a_{n+1} - 1,$ which is less than $a_n$. Likewise, $a_{n+3}$ is also less than $a_n$. Therefore, $a_{n+4} = a_{n+2} + a_{n+3} - 1 \leq 2a_n - 1 \leq 2 - \frac{2}{2^m} - 1 = 1 - \frac{1}{2^{m-1}},$ so $a_{n+4} \leq 1 - \frac{1}{2^{m-1}}.$ This contradicts the fact that $m$ is the smallest positive integer with the above property. Thus proved.

Theorem $2$: Every reduced Fibonacci sequence consisting of only rational numbers is periodic, and therefore has a smallest element.

Proof: Let $d$ be the common denominator of the first two terms. Since subsequent terms are sums of previous terms, they all have common denominator $d.$ Therefore, the whole sequence has common denominator $d.$ Every pair of consecutive terms is preceded by a unique pair (or not preceded by a pair at all). Since there are only finitely many options for pairs of consecutive elements, one of them must be repeated at some point. If the first repeated pair is something other than the starting pair, then it has two possible preceding pairs, which is impossible. Therefore, the first pair to repeat is the starting pair. Since each pair is followed by a unique pair, the sequence keeps on repeating the same cycle of pairs. This means that the sequence is periodic, so each element appears infinitely many times. Since it contains only finitely many unique elements, it has a smallest element.

Theorem $3$: Every reduced Fibonacci sequence consisting of only rational numbers contains infinitely many terms greater than three times the infimum of the sequence ("big" elements).

Proof: Let $S$ be a reduced Fibonacci sequence. Let $a_n$ be the first occurrence of the smallest element such that $n \geq 3.$ This exists by Theorem $2.$

Case $1$: $a_{n+1} < a_n.$

This contradicts the fact that $a_n$ is the smallest element.

Case $2$: $a_n \leq a_{n+1} < 2a_n.$

In this case, $a_{n-1} = a_{n+1} - a_n < 2a_n - a_n < a_n,$ which contradicts the fact that $a_n$ is the smallest element.

Case $3$: $a_{n+1} \geq 2a_n$ and $a_n \geq \frac{1}{3}.$

In this case, since $a_n \geq \frac{1}{3}, 3a_n \geq 1,$ so $a_{n+1} + a_n \geq 1.$ Therefore, $a_{n+2} = a_n + a_{n+1} - 1,$ which is smaller than $a_n,$ contradicting the fact that $a_n$ is the smallest element. Thus proved.

Case $4$: $a_{n+1} \geq 2a_n$ and $a_n < \frac{1}{3}.$

In this case, by similar reasoning to the above, $a_{n+2}$ is a big element. Therefore, there is a big element. By Theorem $2$, this implies that there are infinitely many big elements.

It seems like a variation of the proof of Theorem $4$ can be used to prove it for irrationals, too.

Answer 4

This may not contribute too much, but I can show that the minimum can't be $1/3$.

Suppose the minimum is $1/3$. For some $x$, the first $11$ terms $a_1,a_2,\dotsc,a_{11}$ in the sequence are $$ {1\over3},\ {1\over3}+x,\ {2\over3}+x,\ 2x,\ {2\over3}+3x,\ {2\over3}+5x,\ {1\over3}+8x,\ 13x,\ {1\over3}+21x,\ {1\over3}+34x,\ {2\over3}+55x $$ where all the terms are meant to be reduced modulo one.

From $a_2=(1/3)+x$ we deduce $0\le x<2/3$.

From $a_3=(2/3)+x$ we deduce $0\le x<1/3$.

From $a_4=2x$ we deduce $1/6\le x<1/3$.

From $a_5=(2/3)+3x$ we deduce $2/9\le x<1/3$.

From $a_6=(2/3)+5x$ we deduce $2/9\le x<4/15$.

We pause to notice that we have a strict inequality $x<4/15$; that will be important.

From $a_7=(1/3)+8x$ we deduce $1/4\le x<4/15$.

From $a_8=13x$ we deduce $10/39\le x<4/15$.

From $a_9=(1/3)+21x$ we deduce $10/39\le x<4/15$ (so no improvement on $a_8$).

From $a_{10}=(1/3)+34x$ we deduce $9/34\le x<4/15$.

From $a_{11}=(2/3)+55x$ we deduce $4/15\le x<4/15$, contradiction!

Unfortunately, this only rules out $1/3$, doesn't rule out any numbers around $1/3$.

Answer 5

Conjectured family of rational sequences achieving (in the limit) infimum $\frac{2}{3\sqrt{5}}$:

We will use the standard indexing of Fibonacci numbers: that is, $F_0 = 0$ and $F_1 = 1.$ Define $L_n$ as $F_{n-1} + F_{n+1}.$

I conjecture (based on empirical evidence) that the reduced Fibonacci sequence starting with $\frac{2F_{8n-1} - 2}{3L_{8n-1}}$ and $\frac{F_{8n+2}-F_{8n-5} + 1}{3L_{8n-1}}$ for $n \geq 1$ has infimum $\frac{2F_{8n-1} - 2}{3L_{8n-1}}.$ This approaches $\frac{2}{3\sqrt{5}}$ as $n \rightarrow \infty.$

Answer 6

Your conjecture is true.

Your conjecture : The reduced Fibonacci sequence starting with $\frac{2F_{8n-1} - 2}{3L_{8n-1}}$ and $\frac{F_{8n+2}-F_{8n-5} + 1}{3L_{8n-1}}$ for $n \geq 1$ has infimum $\frac{2F_{8n-1} - 2}{3L_{8n-1}}.$

Let us define $a_n(m),b_n(m),c_n(m)$ as follows :

$$\begin{cases}a_{n}(1)=2F_{8n-1} - 2 \\a_n(2)=F_{8n+2}-F_{8n-5} + 1 \\a_{n}(m+2)=a_{n}(m+1)+a_{n}(m)\qquad (m\ge 1) \\b_n(m)=\left\lfloor\frac{a_n(m)}{3L_{8n-1}}\right\rfloor \\c_n(m)=a_n(m)-3L_{8n-1}b_n(m)\end{cases}$$

Then, the $m$-th term of your sequence can be written as $\dfrac{c_n(m)}{3L_{8n-1}}$.

Now, I'm going to prove the following claims.

Claim 1 : $a_{n}(m)=L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-F_{m-4}$

Claim 2 : $c_n(8n)=c_n(1)$ and $c_n(8n+1)=c_n(2)$

Claim 3 : $b_n(1)=0$, and for $2\le m\le 8n-1$, $$b_n(m)=\frac 23L_m-F_m-\begin{cases}1&\text{if $m\equiv 2,6\pmod 8$} \\\\\dfrac 23&\text{if $m\equiv 1,3,4\pmod 8$} \\\\\dfrac 13&\text{if $m\equiv 0,5,7\pmod 8$}\end{cases}$$

Claim 4 : For every $m=2,3,\cdots,8n-1$, $c_n(m)\gt c_n(1)$.

From the claims, we can say that your conjecture is true.

---

Claim 1 : $a_{n}(m)=L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-F_{m-4}$

Proof :

We have $a_n(1)=2F_{8n}-2F_{8n-2}-2$ and $a_n(2)=F_{8n}+4F_{8n-2}+1$. Let $\{A_m\},\{B_m\},\{C_m\}$ be the sequence with $A_{m+2}=A_{m+1}+A_m,B_{m+2}=B_{m+1}+B_m$ and $C_{m+2}=C_{m+1}+C_m$ with $A_1=2,A_2=1,B_1=-2,B_2=4,C_1=-2,C_2=1$ respectively. Letting $\alpha=\frac{1-\sqrt 5}{2}$ and $\beta=\frac{1+\sqrt 5}{2}$, we have $$A_{m+1}-\alpha A_m=\beta(A_m-\alpha A_{m-1})=\cdots =\beta^{m-1}(A_2-\alpha A_1)$$ and $$A_{m+1}-\beta A_m=\alpha(A_m-\beta A_{m-1})=\cdots =\alpha^{m-1}(A_2-\beta A_1)$$ Subtracting the latter from the former, we get $$A_m=\frac{A_2(\beta^{m-1}-\alpha^{m-1})+A_1(\beta^{m-2}-\alpha^{m-2})}{\beta-\alpha}=F_{m-1}+2F_{m-2}=L_{m-1}$$ Similarly, $$\begin{align}B_m&=\frac{B_2(\beta^{m-1}-\alpha^{m-1})+B_1(\beta^{m-2}-\alpha^{m-2})}{\beta-\alpha}=4F_{m-1}-2F_{m-2}=2L_{m-2} \\\\C_m&=\frac{C_2(\beta^{m-1}-\alpha^{m-1})+C_1(\beta^{m-2}-\alpha^{m-2})}{\beta-\alpha}=F_{m-1}-2F_{m-2}=-F_{m-4}\end{align}$$ These give $$a_n(m)=L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-F_{m-4}.\ \blacksquare$$

---

Claim 2 : $c_n(8n)=c_n(1)$ and $c_n(8n+1)=c_n(2)$

Proof :

It is sufficient to prove that $a_n(8n)\equiv a_n(1)\pmod{3L_{8n-1}}$ and $a_n(8n+1)\equiv a_n(2)\pmod{3L_{8n-1}}$.

Letting $s=L_{8n-1}$ and $t=L_{8n}$, we have $$\begin{align}&a_{n}(8n)-a_n(1) \\\\&\equiv sF_{8n}+2L_{8n-2}F_{8n-2}-F_{8n-4}-(2F_{8n}-2F_{8n-2}-2)\pmod{3s} \\\\&\equiv (s-2)F_{8n}+(2L_{8n-2}+2)F_{8n-2}-F_{8n-4}+2\pmod{3s} \\\\&\equiv (s-2)\frac{t+2s}{5}+(2t-2s+2)\frac{3s-t}{5}-\frac{7s-4t}{5}+2\pmod{3s}\end{align}$$

So, we obtain $$\begin{align}5(a_{n}(8n)-a_n(1))&\equiv 3s(-s+ 3t-1) -s^2 -2s- 2 t^2 + 10\pmod{3s} \\\\&\equiv -s^2-2s- 2 (sL_{8n+1}+5) + 10\pmod{3s} \\\\&\equiv (-s-2-2L_{8n+1})s\pmod{3s}\end{align}$$ Since $s\equiv 2\pmod 3,L_{8n+1}\equiv 1\pmod 3$ and $\gcd(3s,5)=1$, it follows that $a_n(8n)-a_n(1)\equiv 0\pmod{3s}$.

Next, we have $$\begin{align}&a_{n}(8n+1)-a_n(2) \\\\&\equiv L_{8n}F_{8n}+2L_{8n-1}F_{8n-2}-F_{8n-3}-(F_{8n}+4F_{8n-2}+1)\pmod{3s} \\\\&\equiv (L_{8n}-1)F_{8n}+(2L_{8n-1}-4)F_{8n-2}-F_{8n-3}-1\pmod{3s} \\\\&\equiv (t-1)\frac{t+2s}{5}+(2s-4)\frac{3s-t}{5}-\frac{3t-4s}{5}-1\pmod{3s}\end{align}$$

So, we obtain $$\begin{align}5(a_{n}(8n+1)-a_n(2))&\equiv 3s(2s-3)-s+ t^2 - 5\pmod{3s} \\\\&\equiv -s+ sL_{8n+1}+5 - 5\pmod{3s} \\\\&\equiv (L_{8n+1}-1)s\pmod{3s}\end{align}$$ Since $L_{8n+1}\equiv 1\pmod 3,\gcd(3s,5)=1$, it follows that $a_n(8n+1)-a_n(2)\equiv 0\pmod{3s}$.$\ \blacksquare$

---

Claim 3 : $b_n(1)=0$, and for $2\le m\le 8n-1$, $$b_n(m)=\frac 23L_m-F_m-\begin{cases}1&\text{if $m\equiv 2,6\pmod 8$} \\\\\dfrac 23&\text{if $m\equiv 1,3,4\pmod 8$} \\\\\dfrac 13&\text{if $m\equiv 0,5,7\pmod 8$}\end{cases}$$

Proof :

$b_n(m)$ is defined as $b_n(m)=\left\lfloor\frac{a_n(m)}{3L_{8n-1}}\right\rfloor$. So, it is sufficient to prove that $$\begin{align}P&:=a_n(m)-3L_{8n-1}b_n(m)\ge 0 \\\\Q&:=3L_{8n-1}b_n(m)+3L_{8n-1}-a_n(m)\gt 0\end{align}$$

Writing $b_n(m)=\frac 23L_m-F_m-C$, we have $$P=3CL_{8n-1}-F_{m-4}+\bigg(L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-2L_{8n-1}L_{m}+3L_{8n-1}F_{m}\bigg)$$

Here, using $$F_aL_b=F_{a+b}+(-1)^{b}F_{a-b},\quad L_aL_b=L_{a+b}+(-1)^bL_{a-b}$$ $$F_{-c}=(-1)^{c+1}F_c,\quad L_{-c}=(-1)^cL_c$$ we obtain $$P=3CL_{8n-1}-F_{m-4}+\underbrace{F_{8n+m-1}+2F_{8n+m-4}-2L_{8n+m-1}+3F_{8n+m-1}}_{=0}+(-1)^{m-1}\bigg(\underbrace{F_{8n-m+1}-2F_{8n-m}+2L_{8n-m-1}+3F_{8n-m-1}}_{=F_{8n-m+3}}\bigg)$$ which gives $$P=3CL_{8n-1}-F_{m-4}+(-1)^{m-1}F_{8n-m+3}$$

• For $m\equiv 2,6\pmod 8$ with $C=1$, since $-F_{m-4}\ge -F_{8n-6}$ and $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n+1}$, we get $P\ge 3L_{8n-1}-F_{8n-6}-F_{8n+1}=F_{8n}+4F_{8n-2}-F_{8n-6}\ge 0$.

• For $m=1,3,4\pmod 8$ with $C=\frac 23$, since $-F_{m-4}\ge -F_{8n-8}$ and $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n-1}$, we get $P\ge 2L_{8n-1}-F_{8n-8}-F_{8n-1}=2F_{8n}+F_{8n-4}-F_{8n-8}\ge 0$.

• For $m=0,5,7\pmod 8$ with $C=\frac 13$, since $-F_{m-4}\ge -F_{8n-5}$ and $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n-5}$, we get $P\ge L_{8n-1}-2F_{8n-5}=F_{8n}+F_{8n-2}-2F_{8n-5}\ge 0$.

Similarly, we get $$\begin{align}Q&=3L_{8n-1}(1-C)+F_{m-4}+\bigg(2L_{8n-1}L_{m}-3L_{8n-1}F_{m}-L_{m-1}F_{8n}-2L_{m-2}F_{8n-2}\bigg) \\\\&=3L_{8n-1}(1-C)+F_{m-4}+\underbrace{2L_{8n+m-1}-3F_{8n+m-1}-F_{8n+m-1}-2F_{8n+m-4}}_{=0} \\&\qquad+(-1)^m\bigg(\underbrace{2L_{8n-m-1}+3F_{8n-m-1}+F_{8n-m+1}-2F_{8n-m}}_{=F_{8n-m+3}}\bigg) \\\\&=3L_{8n-1}(1-C)+F_{m-4}+(-1)^{m}F_{8n-m+3}\end{align}$$

• For $m\equiv 2,6\pmod 8$ with $C=1$, since $F_{m-4}\ge F_{-2}=-1$ and $(-1)^mF_{8n-m+3}\ge F_{5}=5$, we get $Q\ge -1+5=4\gt 0$.

• For $m\equiv 1,3,4\pmod 8$ with $C=\frac 23$, since $F_{m-4}\ge F_{0}=0$ and $(-1)^mF_{8n-m+3}\ge -F_{8n}$, we get $Q\ge L_{8n-1}-F_{8n}=F_{8n-2}\gt 0$.

• For $m\equiv 0,5,7\pmod 8$ with $C=\frac 13$, since $F_{m-4}\ge F_1=1$ and $(-1)^mF_{8n-m+3}\ge -F_{8n-2}$, we get $Q\ge 2L_{8n-1}+1-F_{8n-2}=2F_{8n}+F_{8n-2}+1\gt 0$.$\ \blacksquare$

---

Claim 4 : For every $m=2,3,\cdots,8n-1$, $c_n(m)\gt c_n(1)$.

Proof :

In a similar way to the one used in the proof of Claim 3, we have, writing $b_n(m)=\frac 23L_m-F_m-C$,

$$\begin{align}c_n(m)-c_n(1)&=3CL_{8n-1}-2F_{8n-1}-F_{m-4}+2 \\&\qquad +\bigg(L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-2L_mL_{8n-1}+3L_{8n-1}F_m\bigg) \\\\&=3CL_{8n-1}-2F_{8n-1}-F_{m-4}+2 \\&\qquad +\underbrace{F_{8n+m-1}+2F_{8n+m-4}-2L_{8n+m-1}+3F_{8n+m-1}}_{=0} \\&\qquad +(-1)^{m-1}\bigg(\underbrace{F_{8n-m+1}-2F_{8n-m}+2L_{8n-m-1}+3F_{8n-m-1}}_{=F_{8n-m+3}}\bigg) \\\\&=3CL_{8n-1}-2F_{8n-1}+(-1)^{m-1}F_{8n-m+3}-F_{m-4}+2\end{align}$$

• For $m\equiv 2,6\pmod 8$ with $C=1$, since $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n+1}$ and $-F_{m-4}\ge -F_{8n-6}$, we get $c_n(m)-c_n(1)\ge 3L_{8n-1}-2F_{8n-1}-F_{8n+1}-F_{8n-6}+2=3F_{8n-2}+F_{8n-4}-F_{8n-6}+2\gt 0$.

• For $m\equiv 1,3,4\pmod 8$ with $C=\frac 23$, since $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n-1}$ and $-F_{m-4}\ge -F_{8n-8}$, we get $c_n(m)-c_n(1)\ge 2L_{8n-1}-2F_{8n-1}-F_{8n-1}-F_{8n-8}+2=2F_{8n-2}+F_{8n-4}-F_{8n-8}+2\gt 0$.

• For $m\equiv 0\pmod 8$ with $C=\frac 13$, since $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n-5}$ and $-F_{m-4}\ge -F_{8n-12}$, we get $c_n(m)-c_n(1)\ge L_{8n-1}-2F_{8n-1}-F_{8n-5}-F_{8n-12}+2=F_{8n-6}-F_{8n-12}+2\gt 0$.

• For $m\equiv 5,7\pmod 8$ with $C=\frac 13$, since $(-1)^{m-1}F_{8n-m+3}\ge F_{4}=3$ and $-F_{m-4}\ge -F_{8n-5}$, we get $c_n(m)-c_n(1)\ge L_{8n-1}-2F_{8n-1}+3-F_{8n-5}+2=F_{8n-6}+5\gt 0$.$\ \blacksquare$