On gapped repeats in a cyclic Fibonacci word

Takashi Horiyama, Yasuhide Numata, Kazuhisa Seto, Shuhei Tsujie

June 01, 2026

Abstract

In this article, we consider the words with cyclic indices. For given \(s\), we consider the pair \((\iota,\kappa)\) of indices such that the word of length \(s\) from \(\iota\) is equal to the word of length \(s\) from \(\kappa\). We give a characterization of such pairs for a cyclic Fibonacci word, and give the number of them.

1

1 Introduction↩︎

We call a map from \({[m]}=\Set{1,\ldots,m}\) to \(\Set{0,1}\) a word of length \(m\) over the alphabet \(\Set{0,1}\). We identify a word \(x\) with the sequence \((x(1),\ldots,x(m))\). Investigating the number of specific subwords in words is one of the central topics in combinatorics on words. For words \(x=(x(1),\ldots,x(m))\) and \(x'=(x'(1),\ldots,x'(m'))\) of lengths \(m\) and \(m'\), respectively, let \(x\doubleplus x'\) denote their concatenation, i.e., the word \((x(1),\ldots,x(m),x'(1),\ldots,x'(m'))\) of length \(m+m'\). For a given word \(x\), a subword of the form \(v\doubleplus v\) for some word \(v\) is called a square (or a tandem repeat). Squares are among the most fundamental structures in words. Fraenkel and Simpson [1] showed that the number of distinct squares in a word of length \(n\) is at most \(2n\), and conjectured that the exact bound is \(n\). This upper bound was successively improved in Ilie–Rytter [2], Deza–Franek–Thierry [3], and Thierry [4], and the conjecture was finally proven by Brlek and Li [5].

A gapped repeat is a natural generalization of a square. It is a subword of the form \(v\doubleplus w \doubleplus v\) for some words \(v\) and \(w\). A gapped repeat \(v\doubleplus w \doubleplus v\) is called an \(\alpha\)-gapped repeat if \(|v \doubleplus w| \leq \alpha |v|\) for \(\alpha \geq 1\), where \(|x|\) denotes the length of a word \(x\).

Equivalently, let \(i\) and \(k\) be the starting positions of the first and second occurrences of \(v\) in \(x\), respectively, and let \(l\) be the length of \(v\). Then \(v\doubleplus w \doubleplus v\) is an \(\alpha\)-gapped repeat if \((k-i)/l \leq \alpha\). When \(\alpha=1\), an \(\alpha\)-gapped repeat reduces to a square (i.e., the gap \(w\) is empty). Thus, gapped repeats generalize squares. They are also fundamental structures in words and have been extensively studied. For example, the upper and lower bounds on the number of maximal \(\alpha\)-gapped repeats in a word have been investigated. Kolpakov–Podolskiy–Posypkin–Khrapov [6] and Kolpakov–Kucherov [7] showed that the number of maximal \(\alpha\)-gapped repeats in a word of length \(m\) is \(O(\alpha^2 m)\) and \(\Omega(\alpha m)\), respectively. Crochemore, Kolpakov, and Kucherov [8] improved the upper bound to \(O(\alpha m)\). For exact bounds, it was shown in Gawrychowski–I–Inenaga–Köppl–Manea [9] that the upper bound is \(18\alpha m\), which was later improved to \(3\left(\frac{\pi^2}{6}+\frac{5}{2}\right)\alpha m\) by I and Köppl [10].

The number of squares and \(\alpha\)-gapped repeats has also been studied for specific families of words. One of the most well-studied families is the sequence \(\Set{\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}{n\in\mathbb{Z}{>0}}\) of Fibonacci words, defined by \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{0} = (0)\), \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1} = (1)\), and \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n} = \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-1}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\). Fibonacci words have many interesting properties (see, e.g., [11]–[14]), and the number of squares in the \(n\)-th Fibonacci word is exactly \(2(f_{n-2}-1)\) [15], where \(f_{n}\) denotes the \(n\)-th Fibonacci number. In Yamane–Nakashima–Seto–Horiyama [16], upper and lower bounds on the number of maximal \(\alpha\)-gapped repeats in the \(n\)-th Fibonacci word were shown to be \(2.1\alpha f_n + o(\alpha f_n)\) and \(0.04\alpha f_n - o(\alpha f_n)\), respectively.

In this article, we consider the Fibonacci word \(\mathring\omega_{n}\) with cyclic index set \(\mathbb{Z}/f_{n}\mathbb{Z}\). For a given \(s\in\mathbb{Z}_{>0}\), we study pairs \((\iota,\kappa)\) of indices such that the subword of length \(s\) starting at position \(\iota\) coincides with that starting at position \(\kappa\). We provide a characterization of such pairs and determine their number. This article is organized as follows: We will define notation and state our main results in . In , we show the results.

2 Notation and main results↩︎

Here we define notation and state our main results, which will be shown in .

Let \(I = \mathbb{Z}/m\mathbb{Z}\) and \(w\) be a map from \(I\) to \(\Set{0,1}\). We call \(w\) a word with a cyclic index of length \(m\). For \(s\in \mathbb{Z}_{>0}\), we define \[\begin{align} \@ifstar{\pairII}{\pairI}{w}{s}= \Set{(\iota,\kappa)|t\in {[s]}\implies w(\iota+\overline{t-1})=w(\kappa+\overline{t-1})} \subset I\times I, \end{align}\] where \({[n]}=\Set{1,\ldots,n}\). For \(\delta\in I\) and \(s\in\mathbb{Z}_{>0}\), we also define \[\begin{align} \@ifstar{\pairII}{\pairI}*{w}{s}{\delta}&=\Set{(\iota,\kappa)\in \@ifstar{\pairII}{\pairI}{w}{s}|\iota-\kappa=\delta}. \end{align}\]

Remark 1. By definition, \[\begin{align} \@ifstar{\pairII}{\pairI}*{w}{s}{-\delta}&=\Set{(\kappa,\iota)|(\iota,\kappa)\in \@ifstar{\pairII}{\pairI}*{w}{s}{\delta}}. \end{align}\] Hence \[\begin{align} \# \@ifstar{\pairII}{\pairI}*{w}{s}{-\delta}&=\# \@ifstar{\pairII}{\pairI}*{w}{s}{\delta}. \end{align}\] For \(d<\frac{m}{2}\), \[\begin{align} \# \Set{ \Set{\iota,\kappa}| (\iota,\kappa)\in\@ifstar{\pairII}{\pairI}*{w}{s}{\overline{d}}\cup \@ifstar{\pairII}{\pairI}*{w}{s}{\overline{-d}}} &=\# \@ifstar{\pairII}{\pairI}*{w}{s}{\overline{d}}. \end{align}\] If \(m\) is even and \(d=\frac{m}{2}\), \[\begin{align} \# \Set{ \Set{\iota,\kappa}| (\iota,\kappa)\in\@ifstar{\pairII}{\pairI}*{w}{s}{\overline{d}}\cup \@ifstar{\pairII}{\pairI}*{w}{s}{\overline{-d}}} &=\frac{1}{2}\# \@ifstar{\pairII}{\pairI}*{w}{s}{\overline{d}}. \end{align}\]

We call a map from \({[m]}\) to \(\Set{0,1}\) a word of length \(m\). We identify a word \(x\) with a sequence \((x(1),\ldots,x(m))\). For words \(\underline{x}=(x(1),\ldots,x(m))\) and \(\underline{x'}=(x'(1),\ldots,x'(m'))\), we define \(\underline{x}\doubleplus\underline{x'}\) to be \((x(1),\ldots,x(m),x'(1),\ldots,x'(m'))\). We define a Fibonacci word \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}\) by \[\begin{align} \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{0} &= (0),\\ \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1} &= (1),\\ \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n} &= \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-1}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}. \end{align}\] The length of \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}\) equals the Fibonacci number \(f_{n}\), where we define the \(i\)-th Fibonacci number \(f_{i}\) by \[\begin{align} f_{0}&=1,\\ f_{1}&=1,\\ f_{i}&=f_{i-1}+f_{i-2}. \end{align}\] Moreover the number of zero’s in \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}\) equals \(f_{n-2}\), the number of one’s in \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}\) equals \(f_{n-1}\). Let \(I_n\) to be \(\mathbb{Z}/f_{n}\mathbb{Z}\). We define a map \(\mathring\omega_{n}\) from \(I_n\) to \(\Set{0,1}\) by \(\mathring\omega_{n}(\overline{i})=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}(i)\) for \(i\in {[f_{n}]}\). We call \(\mathring\omega_{n}\) the cyclic Fibonacci word. We are interested in \(\@ifstar{\pairII}{\pairI}*{\mathring\omega_{n}}{s}{\delta}\).

Example 1. Consider the cyclic Fibonacci word \(\mathring\omega_{5}\). Note that \[\begin{align} \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{5}=(1,0,1,1,0,1,0,1). \end{align}\] For \(w=(w_1,\ldots,w_s)\), we consider the set \[\begin{align} J_{w}=\Set{\iota \in I_5|(\mathring\omega_{5}(\iota+\overline{0}),\mathring\omega_{5}(\iota+\overline{1}),\ldots,\mathring\omega_{5}(\iota+\overline{s-1}))=w}. \end{align}\] For \(s=1\), we have \[\begin{align} J_{(1)}&=\Set{\overline{1},\overline{3},\overline{4},\overline{6},\overline{8}},\\ J_{(0)}&=\Set{\overline{2},\overline{5},\overline{7}}. \end{align}\] By definition, \(\@ifstar{\pairII}{\pairI}{\mathring\omega_{5}}{1}=(J_{(1)})^2 \cup (J_{(0)})^2\). Let \(m(J)\) be the vector \((m_0,\ldots,m_7)\) such that \(m_d\) is the number of the pairs \((\iota,\kappa)\in J^2\) with \(\iota-\kappa=\overline{d}\). By direct calculation, we have \[\begin{align} m(J_{(1)})&=(5,2,3,4,2,4,3,2)\\ m(J_{(0)})&=(3,0,1,2,0,2,1,0). \end{align}\] Let \(p_s\) be the vector \((p(0),\ldots,p(7))\) such that \(p(d)=\#\@ifstar{\pairII}{\pairI}*{\mathring\omega_{5}}{s}{\overline{d}}\). Then \(p_s\) is the sum of \(m(J)\). Hence we have \[\begin{align} p_1 &=(5,2,3,4,2,4,3,2) +(3,0,1,2,0,2,1,0)\\ &=(8,2,4,6,2,6,4,2). \end{align}\] Let \(p'_s = (p_s(0),p_s(5),p_s(2),p_s(7);p_s(4);p_s(1),p_s(6),p_s(3))\). Then \[\begin{align} p'_1=(8,6,4,2;2;2,4,6). \end{align}\] For \(s=2\), we have \[\begin{align} J_{(1,0)}&=\Set{\overline{1},\overline{4},\overline{6}},\\ J_{(1,1)}&=\Set{\overline{3},\overline{8}},\\ J_{(0,1)}&=J_{(0)}. \end{align}\] By direct calculation we have \(m(J_{(1,1)})=(2,0,0,1,0,1,0,0)\). Since \[\begin{align} J_{(1,0)}=\Set{\iota-\overline{1} |\iota\in J_{(0)}}, \end{align}\] we have \(m(J_{(1,0)})=m(J_{(0)})=(3,0,1,2,0,2,1,0)\). Hence \[\begin{align} p_2 &= 2(3,0,1,2,0,2,1,0) +(2,0,0,1,0,1,0,0) \\ &=(8,0,2,5,0,5,2,0),\\ p'_2&=(8,5,2,0;0;0,2,5). \end{align}\] For \(s=3\), \(J_{(0,1)}\) splits into \[\begin{align} J_{(0,1,0)}&=\Set{\overline{5}},\\ J_{(0,1,1)}&=\Set{\overline{2},\overline{7}}. \end{align}\] We also have \(J_{(1,0,1)}=J_{(1,0)}\) and \(J_{(1,1,0)}=J_{(1,1)}\). Since \(J_{(0,1,0)}\) is a singleton, we have \(m(J_{(0,1,0)})=(1,0,0,0,0,0,0,0)\). Since \[\begin{align} J_{(0,1,1)}=\Set{\iota-\overline{1} | \iota\in J_{(1,1)}}, \end{align}\] we have \(m(J_{(0,1,1)})=(2,0,0,1,0,1,0,0)\). Hence \[\begin{align} p_3 &= (3,0,1,2,0,2,1,0) +2(2,0,0,1,0,1,0,0) +(1,0,0,0,0,0,0,0) \\ &=(8,0,1,4,0,4,1,0),\\ p'_3&=(8,4,1,0;0;0,1,4). \end{align}\] For \(s=4\), \(J_{(1,0,1,1)}\) splits into \[\begin{align} J_{(1,0,1,1)}&=\Set{\overline{1},\overline{6}},\\ J_{(1,0,1,0)}&=\Set{\overline{4}}. \end{align}\] We also have \(J_{(0,1,1,0)}=J_{(0,1,1)}\), and \(J_{(1,1,0,1)}=J_{(1,1,0)}\). We also have one more singleton \(J_{(0,1,0,1)}=J_{(0,1,0)}\). Hence \[\begin{align} p_4 &= 3(2,0,0,1,0,1,0,0) +2(1,0,0,0,0,0,0,0) \\ &=(8,0,0,3,0,3,0,0),\\ p'_4&=(8,3,0,0;0;0,0,3). \end{align}\] For \(s=5\), \(J_{(1,1,0,1)}\) splits into the singletons \(J_{(1,1,0,1,0)}\) and \(J_{(1,1,0,1,1)}\). We also have \(J_{(0,1,1,0,1)}=J_{(0,1,1,0)}\), \(J_{(1,0,1,1,0)}=J_{(1,0,1,1)}\). Also we have two more singletons. Hence \[\begin{align} p_5 &= 2(2,0,0,1,0,1,0,0) +4(1,0,0,0,0,0,0,0) \\ &=(8,0,0,2,0,2,0,0),\\ p'_5&=(8,2,0,0;0;0,0,2). \end{align}\] For \(s=6\), \(J_{(0,1,1,0,1)}\) splits into the singletons \(J_{(0,1,1,0,1,0)}\) and \(J_{(0,1,1,0,1,1)}\). We also have \(J_{(1,0,1,1,0,1)}=J_{(1,0,1,1,0)}\). We have four more singletons. Hence \[\begin{align} p_6 &= 1(2,0,0,1,0,1,0,0) +6(1,0,0,0,0,0,0,0) \\ &=(8,0,0,1,0,1,0,0),\\ p'_6&=(8,1,0,0;0;0,0,1). \end{align}\] For \(s=7\), \(J_{(1,0,1,1,0,1)}\) splits into singletons \(J_{(1,0,1,1,0,1,0)}\) and \(J_{(1,0,1,1,0,1,1)}\). Since all are singletons, we have \[\begin{align} p_7 &= 8(1,0,0,0,0,0,0,0) \\ &=(8,0,0,0,0,0,0,0),\\ p'_7&=(8,0,0,0;0;0,0,0). \end{align}\]

Note that \[\begin{align} \Set{1,2,\ldots,f_{n}-1} &=\coprod_{l=1}^{n-1} \Set{i | f_{l}\leq i <f_{l+1}}. \end{align}\] Our main results are the following: For the case where \(s=1\), we have .

Theorem 1. We have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\mathring\omega_{n}}{1}{\overline{f_{n-1}p}} = \begin{cases} f_{n}-2p&(0\leq p \leq f_{n-2}),\\ f_{n-3}&(f_{n-2}\leq p \leq f_{n-1}),\\ 2p-f_{n}&(f_{n-1}\leq p < f_{n}). \end{cases} \end{align}\]

For the case where \(2\leq s<f_{n-1}\), we have :

Theorem 2. For \(1<f_{l}\leq s<f_{l+1}<f_{n}\), \[\begin{align} &\#\@ifstar{\pairII}{\pairI}*{\mathring\omega_{n}}{s}{\overline{f_{n-1}p}} =\\& \begin{cases} f_{n}-p(s+1) & (0\leq p<f_{n-l-1}), \\ f_{n-l-1}(f_{l+1}-(s+1))+f_{l}(f_{n-l}-p) & (f_{n-l-1}\leq p<f_{n-l}), \\ (f_{l+1}-(s+1))(f_{n-l+1}-p) & (f_{n-l}\leq p<f_{n-l+1}), \\ 0 & (f_{n-l+1}\leq p\leq f_{n}-f_{n-l+1}), \\ (f_{l+1}-(s+1))(f_{n-l+1}-(f_{n}-p)) & (f_{n}-f_{n-l+1}\leq p \leq f_{n}-f_{n-l}), \\ f_{n-l-1}(f_{l+1}-(s+1))+f_{l}(f_{n-l}-(f_{n}-p)) & (f_{n}-f_{n-l} < p\leq f_{n}-f_{n-l-1}), \\ f_{n}-(f_{n}-p)(s+1) & (f_{n}-f_{n-l-1}< p< f_{n}). \end{cases} \end{align}\]

For the case where \(f_{n-1}\leq s<f_{n}\), we have .

Theorem 3. For \(1<f_{n-1}\leq s<f_{n}\), \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\mathring\omega_{n}}{s}{\overline{f_{n-1}p}} &= \begin{cases} f_{n} &(p=0),\\ f_{n}-(s+1) &(p=1),\\ 0&(1<p<f_{n-1}),\\ f_{n}-(s+1) &(p=f_{n}-1). \end{cases} \end{align}\]

Considering the case where \(s=f_{l+1}-1\), we have the following as a corollary to :

Corollary 2. For \(1<l\leq n-2\), \[\begin{align} &\#\@ifstar{\pairII}{\pairI}*{\mathring\omega_{n}}{f_{l+1}-1}{\overline{f_{n-1}p}}\\ &= \begin{cases} f_{n}-pf_{l+1} & (0\leq p <f_{n-l-1}), \\ (f_{n-l}-p)f_{l} & (f_{n-l-1}\leq p<f_{n-l}), \\ 0 & (f_{n-l}\leq p \leq f_{n}-f_{n-l}), \\ (f_{n-l}-(f_{n}-p))f_{l} & (f_{n}-f_{n-l}< p\leq f_{n}-f_{n-l}-1), \\ f_{n}-(f_{n}-p)f_{l+1} & (f_{n}-f_{n-l}-1< p <f_{n}) . \end{cases} \end{align}\]

3 Proof of main results↩︎

Here we show our main results, i.e., .

First we show some formula for Fibonacci words, which will be used in the proof of . For words \(\underline{x}=(x(1),x(2),\ldots,x(m))\), we define \[\begin{align} {\underline{x}}^{\dagger}&=(x(m),x(m-1),\ldots,x(1)). \end{align}\] Let \[\begin{align} \upsilon_n = \begin{cases} (1,0)&(\text{n is odd}),\\ (0,1)&(\text{n is even}). \end{cases} \end{align}\] Then we have the following:

Lemma 1. For \(n>5\), \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1})\doubleplus\upsilon_{n}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\).

Proof. We show the equation by induction on \(n\). For \(n=6,7\), we have \[\begin{align} \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{6} &=(1,0,1,1,0,1,0,1,1,0,1,1,0)\\ &=(1,0,1,1,0)\doubleplus(1)\doubleplus(0,1)\doubleplus(1)\doubleplus(1,0,1,1,0)\\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{4}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}\doubleplus\upsilon_{6}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{4},\\ \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{7} &=(1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,1,1,0,1,0,1))\\ &=(1,0,1,1,0,1,0,1)\doubleplus(1,0)\doubleplus(1)\doubleplus(1,0)\doubleplus(1,0,1,1,0,1,0,1)\\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{2}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}\doubleplus\upsilon_{7}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{5}. \end{align}\] For \(n>7\), we have \[\begin{align} &\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-7}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}\doubleplus\upsilon_{n})\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2} \\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6})\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-7}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}\doubleplus\upsilon_{n})\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2} \\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-7}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}\doubleplus\upsilon_{n})\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}) \\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-7}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}\doubleplus\upsilon_{n}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4})\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}). \end{align}\] By induction hypothesis, \[\begin{align} &\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-7}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}\doubleplus\upsilon_{n}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4})\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}) \\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}) \\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4})\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}) \\ &=(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3})\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5})\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4} \\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-1}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4} \\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-1}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2} \\ &=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}. \end{align}\] ◻

Lemma 2. For \(n>4\), \({\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}=\upsilon_n\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-1}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1})\).

Proof. For \(n=5,6\), \[\begin{align} {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{5}}^{\dagger}&=(1,0,1,0,1,1,0,1)=\upsilon_5\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{4}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1},\\ {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{6}}^{\dagger}&=(0,1,1,0,1,1,0,1,0,1,1,0,1)=\upsilon_6\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{5}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{2}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}. \end{align}\] Consider the case where \(n>6\). By induction hypothesis, we have \[\begin{align} &{\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger} \\ &= {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}}^{\dagger}\doubleplus{\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-1}}^{\dagger} \\ &= (\upsilon_{n-2}\doubleplus \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}) \doubleplus (\upsilon_{n-1}\doubleplus \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}) \\ &= \upsilon_{n-2}\doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1} \doubleplus \upsilon_{n-1}) \doubleplus \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}) \end{align}\] By definition we have \(\upsilon_{n-2}=\upsilon_{n}\), \(\upsilon_{n-1}=\upsilon_{n-3}\) and \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}=\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}\). Hence \[\begin{align} &{\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger} \\ &=\upsilon_{n-2}\doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1} \doubleplus \upsilon_{n-1}) \doubleplus \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-2}\doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}) \\ &= \upsilon_{n}\doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1} \doubleplus \upsilon_{n-3}) \doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4}) \doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}) \\ &= \upsilon_{n}\doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1} \doubleplus \upsilon_{n-3} \doubleplus \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3})\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4} \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}). \end{align}\] Hence, by , we have \[\begin{align} &{\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger} \\ &= \upsilon_{n}\doubleplus (\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3}\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-6}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1} \doubleplus \upsilon_{n-3} \doubleplus \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-3})\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4} \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1})\\ &= \upsilon_{n}\doubleplus \@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-1}\doubleplus(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-4} \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-5}\doubleplus\cdots \doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{1}). \end{align}\] ◻

Corollary 3. Let \(2\leq l\leq n-1\) and \(w=({\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}(1),\ldots,{\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}(f_{l}))\), i.e., the first \(f_{l}\) letters in \({\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}\). The number of zeros in \(w\) is \(f_{l-2}\). The number of ones in \(w\) is \(f_{l-1}\).

Proof. In the case where \(n=3\), we have \({\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{3}}^{\dagger}=(1,0,1)\). Since \(w=(1,0)\) for \(l=2\), the number of zeros is \(f_{0}\) and the number of ones is \(f_{1}\). In the case where \(n=4\), we have \({\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{4}}^{\dagger}=(0,1,1,0,1)\). Since \(w=(0,1)\) for \(l=2\), the number of zeros is \(f_{0}\) and the number of ones is \(f_{1}\). Since \(w=(0,1,1)\) for \(l=3\), the number of zeros is \(f_{1}\) and the number of ones is \(f_{2}\). In the case where \(n>4\), since the first \(f_{l}\) letters of \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n-1}\) is \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{l}\), it follows from that \(w\) is the first \(f_{l}\) letters of the words \((0,1)\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{l}\) or \(w=(1,0)\doubleplus\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{l}\) of length \(f_{l}+2\). Since the final two letters of \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{l}\) is \((1,0)\) or \((0,1)\), the number of zeros (resp. ones) in \(w\) is the number of zeros (resp. ones) in \(\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{l}\), i.e., \(f_{l-2}\) (resp. \(f_{l-1}\)). ◻

Next we give another definition of the cyclic Fibonacci words. For \(n\in \mathbb{Z}_{>0}\), we define \(R_{n}\) to be \(\mathbb{Z}/f_{n}\mathbb{Z}\). Let \[\begin{align} o_{n}= \begin{cases} -1 & (\text{n is even}),\\ 0 & (\text{n is odd}). \end{cases} \end{align}\] We define the subsets \(\widecheck R_{n}\) and \(\widehat R_{n}\) by \[\begin{align} \widecheck R_{n}& = \Set{\overline{x+o_{n}}\in R_{n}|x\in {[f_{n-2}]}}, \\ \widehat R_{n} &= \Set{\overline{x+f_{n-2}+o_{n}}\in R_{n}|x\in {[f_{n-1}]}}. \end{align}\] Let \[\begin{align} \@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}&= \overline{f_{n-1}} \in R_{n},\\ \@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}* &= \overline{f_{n-2}} \in R_{n}. \end{align}\] We define maps \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}\) and \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*\) from \(I_n\) to \(R_{n}\) by \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)&=\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}\iota,\\ \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)&=\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}* \iota \end{align}\] for \(\iota\in I_n\). Let \(\nu_{n}\) be the map from \(R_{n}\) to \(\Set{0,1}\) by \[\begin{align} \nu_{n}(\alpha) &= \begin{cases} 0 & (\alpha\in\widecheck R_{n}),\\ 1 & (\alpha\in\widehat R_{n}). \end{cases} \end{align}\] We define maps \(\@ifstar{w_{n}^{\ast}}{w_{n}}\) and \(\@ifstar{w_{n}^{\ast}}{w_{n}}*\) from \(I_n\) to \(\Set{0,1}\) by \[\begin{align} \@ifstar{w_{n}^{\ast}}{w_{n}}(\iota) & = \nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)),\\ \@ifstar{w_{n}^{\ast}}{w_{n}}*(\iota) & = \nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)) \end{align}\] for \(\iota\in I_n\).

The following are known:

Propsition 4. For \(n>1\), \(\@ifstar{w_{n}^{\ast}}{w_{n}}=\mathring\omega_{n}\).

Since we have \(\@ifstar{w_{n}^{\ast}}{w_{n}}=\mathring\omega_{n}\), we also have the following:

Corollary 5. For \(n>1\), \[\begin{align} (\@ifstar{w_{n}^{\ast}}{w_{n}}*(\overline{0}),\@ifstar{w_{n}^{\ast}}{w_{n}}*(\overline{1}),\ldots,\@ifstar{w_{n}^{\ast}}{w_{n}}*(\overline{f_{n}-1})) ={\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}. \end{align}\]

Proof. Since \(\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*=-\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}\), \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i})=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{-i})=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{f_{n}-i})\). Hence we have \[\begin{align} (\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0}),\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1}),\ldots,\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{f_{n}-1})) &= (\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{f_{n}}),\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{f_{n}-1}),\ldots,\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1})), \end{align}\] which implies \[\begin{align} (\@ifstar{w_{n}^{\ast}}{w_{n}}*(\overline{0}),\@ifstar{w_{n}^{\ast}}{w_{n}}*(\overline{1}),\ldots,\@ifstar{w_{n}^{\ast}}{w_{n}}*(\overline{f_{n}-1})) ={(\@ifstar{w_{n}^{\ast}}{w_{n}}(\overline{1}),\ldots,\@ifstar{w_{n}^{\ast}}{w_{n}}(\overline{f_{n}}))}^{\dagger}. \end{align}\] ◻

Since we have , we can count the numbers of indices such that \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in \widecheck R_{n}\) and \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in \widehat R_{n}\).

Lemma 3. If \(1\leq f_{l}-1\leq s \leq f_{l+1}-1\leq f_{n}\), then \[\begin{align} f_{l-2}&\leq \#\Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in \widecheck R_{n}} \leq f_{l-1},\\ f_{l-1}&\leq \#\Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in \widehat R_{n}} \leq f_{l}. \end{align}\]

Proof. By , we have \[\begin{align} \Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in \widecheck R_{n}} &= \Set{t|0\leq t \leq s, \nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t}))=0} \\ &= \Set{t|0\leq t \leq s, {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}(t+1)=0}. \end{align}\] By , \[\begin{align} \#\Set{t|0\leq t < f_{l}, {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}(t+1)=0}=f_{l-2},\\ \#\Set{t|0\leq t < f_{l+1}, {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}(t+1)=0}=f_{l-1}. \end{align}\] Hence we have \[\begin{align} f_{l-2}&\leq \#\Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in \widecheck R_{n}} \leq f_{l-1}. \end{align}\] Similarly, by , we have \[\begin{align} \Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in \widehat R_{n}} &= \Set{t|0\leq t \leq s, {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}(t+1)=1}. \end{align}\] By , \[\begin{align} \#\Set{t|0\leq t < f_{l}, {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}(t+1)=0}=f_{l-1},\\ \#\Set{t|0\leq t < f_{l+1}, {\@ifstar{\@ifstar{\fibwordR}{\fibwordM}}{\fibwordI}{n}}^{\dagger}(t+1)=0}=f_{l}. \end{align}\] Hence we have \[\begin{align} f_{l-1}&\leq \#\Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in \widehat R_{n}} \leq f_{l}. \end{align}\] ◻

Next, we consider when the values \(\@ifstar{w_{n}^{\ast}}{w_{n}}(\iota)\) and \(\@ifstar{w_{n}^{\ast}}{w_{n}}(\kappa)\) are the same. We define \(\@ifstar{\samestepN}{\samestepP}*{t}\) to be the equivalence relation induced by the classification \[\begin{align} \Set{\widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t-1}),\widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t-1})}, \end{align}\] where \[\begin{align} \widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t-1}) &= \Set{\overline{a+o_{n}}\in R_{n}|(t-1)f_{n-2}<a\leq tf_{n-2}},\\ \widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t-1}) &=\Set{\overline{a+o_{n}}\in R_{n}|tf_{n-2}<a\leq tf_{n-2}+f_{n-1}}. \end{align}\]

Lemma 4. For \(\iota,\kappa\in I_n\) and \(t\in{[f_{n}]}\), the following are equivalent:

  1. \(\@ifstar{w_{n}^{\ast}}{w_{n}}(\iota+\overline{t-1})=\@ifstar{w_{n}^{\ast}}{w_{n}}(\kappa+\overline{t-1})\).

  2. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\@ifstar{\samestepN}{\samestepP}*{t}\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\).

Proof. By definition, \(\@ifstar{w_{n}^{\ast}}{w_{n}}(\iota+\overline{t-1})\neq\@ifstar{w_{n}^{\ast}}{w_{n}}(\kappa+\overline{t-1})\) means that \(\nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota+\overline{t-1}))\neq\nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa+\overline{t-1}))\). In the case where \(\nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota+\overline{t-1}))\neq\nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa+\overline{t-1})\), without loss of generality, we can assume that \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota+\overline{t-1})\in\widehat R_{n}\) and \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa+\overline{t-1})\in\widecheck R_{n}\). Since \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota+\overline{t-1})=\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)+\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{t-1})\), we have \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\in \widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t-1})\). Simalarly we have \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\in \widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t-1})\). Hence \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\) and \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\) do not satisfy \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\@ifstar{\samestepN}{\samestepP}*{t}\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\).

Conversely, in the case where \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\) and \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\) do not satisfy \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\@ifstar{\samestepN}{\samestepP}*{t}\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\), without loss of generality, we can assume that \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\in \widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t-1})\) and \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\in \widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t-1})\). Hence we have \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)+\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{t-1})\in \widecheck R_{n}\), which implies \(\nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota+\overline{t-1}))=0\). Similarly we have \(\nu_{n}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa+\overline{t-1}))=1\). Hence \(\@ifstar{w_{n}^{\ast}}{w_{n}}(\iota+\overline{t-1})\neq\@ifstar{w_{n}^{\ast}}{w_{n}}(\kappa+\overline{t-1})\). ◻

Let \[\begin{align} X= \Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}} |0\leq t \leq s}. \end{align}\] For \(a,b \in\mathbb{Z}\) with \(a<b\) and \(b-a<f_{n}\), we define the relation \(\sim\) by \[\begin{align} a\sim b \iff \text{``a\leq c < b\implies \overline{c}\not \in X.''} \end{align}\] We define \(\@ifstar{\samecompN}{\samecompP}*{s}\) to be the equivalence relation on \(R_{n}\) induced by \(\sim\).

Remark 6. Let \(X=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}} |0\leq t \leq s}\). For \(\alpha,\beta \in R_{n}\), the following are equivalent:

  1. \(\alpha\) and \(\beta\) do not satisfy \(\alpha\@ifstar{\samecompN}{\samecompP}*{s} \beta\).

  2. The following hold:

    1. There exist \(a,b,c\) such that \(\alpha=\overline{a}\), \(\beta=\overline{b}\), \(\overline{c}\in X\), \(a\leq c < b\) and \(b-a<f_{n}\).

    2. There exist \(a',b',c'\) such that \(\alpha=\overline{a'}\), \(\beta=\overline{b'}\), \(\overline{c'}\in X\), \(b'\leq c' < a'\) and \(a'-b'<f_{n}\).

Lemma 5. Let \(s\in{[f_{n}]}\). For \(\alpha,\beta \in R_{n}\), the following are equivalent:

  1. \(\alpha\@ifstar{\samecompN}{\samecompP}*{s}\beta\).

  2. For all \(t\in{[s]}\), \(\alpha\@ifstar{\samestepN}{\samestepP}*{t}\beta\).

Proof. Let \(X=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}} | 0\leq t \leq s }\).

In the case where \(\alpha=\overline{a},\beta=\overline{b}\in R_{n}\) and \(t\in{[s]}\) do not satisfy \(\alpha\@ifstar{\samestepN}{\samestepP}*{t}\beta\), without loss of generality, we can assume that \[\begin{align} (t-1)f_{n-2}+o_{n}< a \leq tf_{n-2}+o_{n}< b \leq (t-1)f_{n-2}+f_{n}+o_{n}. \end{align}\] Since \(0\leq t-1 < t\leq s\), \(\overline{(t-1)f_{n-2}}+\overline{o_{n}}\) and \(\overline{tf_{n-2}}+\overline{o_{n}}\) are in \(X\). Hence \(\alpha,\beta\) do not satisfy \(\alpha\@ifstar{\samecompN}{\samecompP}*{s}\beta\).

In the case where \(\alpha,\beta\in R_{n}\) do not satisfy \(\alpha\@ifstar{\samecompN}{\samecompP}*{s}\beta\), there exisits \(\overline{c},\overline{c'}\in X\) such that \(\alpha=\overline{a}\), \(\beta=\overline{b}\) and \(c' < a<c\leq b \leq c'+f_{n}\). Without loss of generality, we can assume that \(\overline{c}=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}}\), \(\overline{c'}=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t'})+\overline{o_{n}}\), \(0\leq t<t' \leq s\) and \[\begin{align} \label{lem:samecomp:pr:eq:a} c'&< a\leq c < b \leq c'+f_{n}. \end{align}\tag{1}\] If \(t'-t=1\), then \(1\leq t'\leq s\). Moreover 1 means that \(\beta\in \widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t'-1})\) and \(\alpha\in \widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t'-1})\). Hence \(\alpha\) and \(\beta\) do not satisfy \(\alpha \@ifstar{\samestepN}{\samestepP}*{t'} \beta\). Assume that \(t'-t>1\). In this case, we have \(0\leq t\leq s-2\) and \(2 \leq t'\leq s\). Hence we have \(1\leq t+1\), \(t'\), \(t'-1 \leq s\). If \(c-f_{n-1}< a\) and \(b \leq c+f_{n-2}\), then we have \[\begin{align} c-f_{n-1} < a\leq c< b \leq c+f_{n-2}. \end{align}\] Since \(\overline{c}=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\), we have \(\beta\in \widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\) and \(\alpha\in \widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\). Hence \(\alpha\) and \(\beta\) do not satisfy \(\alpha \@ifstar{\samestepN}{\samestepP}*{t+1} \beta\). If \(a\leq c-f_{n-1}\), then we have \(a+f_{n}\leq c-f_{n-1}+f_{n}=c+f_{n-2}\), Hence \[\begin{align} c< b \leq c'+f_{n}< a+f_{n}\leq c+f_{n-2}. \end{align}\] Since \((c'+f_{n})-b<(c+f_{n-2})-(c)=f_{n-2}\), we have \(c'+f_{n}-f_{n-2}<b\). Hence we have \(c'+f_{n}-f_{n-2}<b\leq c'+f_{n-2}\). Since \(\overline{c'+f_{n}-f_{n-2}}=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t'-1})\), we have \(\beta\in\widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t'-1})\). On the other hand, since \((a+f_{n})-(c'+f_{n}) <(c+f_{n-2})-c=f_{n-2}\), we have \((a+f_{n})<(c'+f_{n})+f_{n-2}\). Hence we have \(c'+f_{n}< (a+f_{n})\leq (c'+f_{n})+f_{n-1}\). Since \(c'+f_{n}=(c'+f_{n}-f_{n-2})+f_{n-2}\), we have \(\alpha\in\widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t'-1})\). Hence \(\alpha\) and \(\beta\) do not satisfy \(\alpha \@ifstar{\samestepN}{\samestepP}*{t'} \beta\). Assume that \(c+f_{n-2} < b\). In this case, we have \(c-f_{n-1} < b-f_{n}\). Hence \[\begin{align} c-f_{n-1} < b-f_{n} \leq c' < a \leq c. \end{align}\] If \(c'-f_{n-2}< b-f_{n}\), then \(\beta\in \widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t'-1})\). Moreover, since \(a-c'\leq c-(c-f_{n-1})\), \(c' < a\leq c'+f_{n-1}\). Hence \(\alpha\in \widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t'-1})\). Hence \(\alpha\) and \(\beta\) do not satisfy \(\alpha \@ifstar{\samestepN}{\samestepP}*{t'} \beta\). Assume that \(b-f_{n}\leq c'-f_{n-2}\). In this case, we consider \(c'-2f_{n-2}\). Since \(c'-(b-f_{n})<c-(c-f_{n-1})=f_{n-1}\), \(c'-2f_{n-2}<b-f_{n}\). Hence \(\beta\in \widecheck R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{t'-2})\). On the other hand, since \(a\leq c\), we have \(a-f_{n}\leq c-f_{n}<c-f_{n-1}\). We also have \(c-f_{n-1}< b-f_{n}\leq c'-f_{n-2}\). Hence we have \((c'-f_{n-2})-(a-f_{n})\geq (c-f_{n-1})-(c-f_{n})=f_{n-2}\), which implies \(a-f_{n}\leq (c'-f_{n-2})-f_{n-2}=c'-2f_{n-2}\). Hence we have \(c'-f_{n-2}<a \leq c'-2f_{n-2}+f_{n}\), which implies \(\alpha\in\widehat R_{n}+\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{t'-2})\). Hence \(\alpha\) and \(\beta\) do not satisfy \(\alpha \@ifstar{\samestepN}{\samestepP}*{t'-1} \beta\). ◻

By , we have the following:

Corollary 7. Let \(s\in {[f_{n}]}\). For \(\iota,\kappa\), the following are equivalent:

  1. \((\iota,\kappa)\in\@ifstar{\pairII}{\pairI}{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}\).

  2. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\@ifstar{\samecompN}{\samecompP}*{s}\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\).

We define \(\@ifstar{\equvclassN}{\equvclassP}*{s}\) to be \[\begin{align} R_{n}/{\@ifstar{\samecompN}{\samecompP}*{s}} \end{align}\] i.e., the set of equvalent classes.

Lemma 6. For \(s\in{[f_{n}]}\) and \(\delta\in I_n\), \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &= \sum_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}}\#\Set{(\alpha,\alpha')\in C| \alpha-\alpha'=\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)}. \end{align}\]

Proof. By , \[\begin{align} \@ifstar{\pairII}{\pairI}{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s} &=\Set{(\iota,\kappa)|\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)\@ifstar{\samecompN}{\samecompP}*{s}\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)}\\ &=\coprod_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}}\Set{(\iota,\kappa)|\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota),\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\in C}. \end{align}\] Since \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}\) is a bijection, we have \[\begin{align} \@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &=\coprod_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}}\Set{(\iota,\kappa)|\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota),\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\in C, \iota-\kappa=\delta}\\ &=\coprod_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}}\Set{(\iota,\kappa)|\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota),\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\in C, \@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota-\kappa)=\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)}\\ &=\coprod_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}}\Set{(\iota,\kappa)|\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota),\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\in C, \@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)-\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)=\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)} \end{align}\] for \(\delta\in I_n\). Hence \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &= \sum_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}}\#\Set{(\iota,\kappa)|\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota),\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)\in C, \@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)-\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\kappa)=\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)}\\ &= \sum_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}}\#\Set{(\alpha,\alpha')\in C| \alpha-\alpha'=\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)}. \end{align}\] ◻

Lemma 7. Let \(d\in{[f_{n}]}\), \(o\in\mathbb{Z}\) and \(C=\Set{\overline{a+o}\in R_{n}|a\in{[d]}}\). Consider \(C(p)=\Set{(\alpha,\alpha')\in C^2|\alpha-\alpha'=\overline{p}}\) for \(0\leq p <f_{n}\). If \(d<\frac{f_{n}}{2}\), then \[\begin{align} \# C(p) &= \begin{cases} d-p & (0\leq p \leq d),\\ 0 & (d\leq p \leq f_{n}-d),\\ d-(f_{n}-p) & (f_{n}-d\leq p < f_{n}). \end{cases} \end{align}\] If \(d\geq \frac{f_{n}}{2}\), then \[\begin{align} \# C(p) &= \begin{cases} d-p & (0\leq p \leq f_{n}-d),\\ 2d-f_{n} & (f_{n}-d\leq p \leq d),\\ d-(f_{n}-p) & (d\leq p < f_{n}). \end{cases} \end{align}\]

Proof. In the case where \(p=0\), we have \(C(p)=\Set{(\alpha,\alpha)|\alpha\in C}\), which implies \(\# C(p)=d\).

Consider the case where \(p>0\). Let \(a,a'\in{[f_{n}]}\) satisfy \((\alpha,\alpha')\in C(p)\), \(\alpha=\overline{a}\) and \(\alpha'=\overline{a'}\). Then \(a\) and \(a'\) satisfy one of the following:

  1. \(a>a'\) and \(a-a'=p\); or

  2. \(a<a'\) and \(a-a'+f_{n}=p\).

Since \(\overline{a}\) and \(\overline{a'}\) are in \(C\), \(a\) and \(a'\) also satisfy \(|a-a'|<d\). Hence we have \(d>a-a'\) and \(a-a'>-d\). Since \(a-a'>-d\), we also have \(a-a'+f_{n}>-d+f_{n}\). First consider the case where \(d<\frac{f_{n}}{2}\). If \(p\leq \frac{f_{n}}{2}\), then we have \(a-a'+f_{n}>-d+f_{n}>\frac{f_{n}}{2}\geq p\), which implies \(a-a'+f_{n}\neq p\). Hence we condiser only the case [lem:numofpairswithdiff:item:62]. Since \[\begin{align} C(p)=\Set{(\alpha+\overline{p},\alpha)|\alpha+\overline{p},\alpha\in C}, \end{align}\] we have \(\#C(p)=d-p\) for \(p < d\) and \(\#C(p)=0\) for \(p \geq d\). If \(p\geq \frac{f_{n}}{2}\), then we have \(a-a'<d<\frac{f_{n}}{2}\leq p\), which implies \(a-a'\neq p\). Hence we condiser only the case [lem:numofpairswithdiff:item:60]. Since \[\begin{align} C(p)=\Set{(\alpha,\alpha+\overline{f_{n}-p})|\alpha,\alpha+\overline{f_{n}-p}\in C}, \end{align}\] we have \(\#C(p)=d-(f_{n}-p)\) for \(d >f_{n}-p\) and \(\#C(p)=0\) for \(d \leq f_{n}-p\). Next consider the case where \(d\geq \frac{f_{n}}{2}\). If \(p\geq d\), then we have \(a-a'<d\leq p\), which implies \(a-a'\neq p\) Hence we condiser only the case [lem:numofpairswithdiff:item:60]. Since \(f_{n}-p \leq f_{n}-d \leq \frac{f_{n}}{2}\leq d\), we have \(\#C(p)=d-(f_{n}-p)\). If \(p\leq f_{n}-d\), then we have \(a-a'+f_{n}>-d+f_{n}\geq p\), which implies \(a-a'+f_{n}\neq p\). Hence we condiser only the case [lem:numofpairswithdiff:item:62]. Since \(p\leq f_{n}-d\leq \frac{f_{n}}{2}\leq d\), we have \(\#C(p)=d-p\). If \(f_{n}-d<p<d\), then we consider the cases [lem:numofpairswithdiff:item:62] and [lem:numofpairswithdiff:item:60]. Since \(p<d\), we have \[\begin{align} \#\Set{(\alpha+\overline{p},\alpha)|\alpha+\overline{p},\alpha\in C}=d-p. \end{align}\] Since \(d >f_{n}-p\), we have \[\begin{align} \#\Set{(\alpha,\alpha+\overline{f_{n}-p})|\alpha,\alpha+\overline{f_{n}-p}\in C}=d-(f_{n}-p). \end{align}\] Hence \(\#C(p)=(d-p)+(d-(f_{n}-p))=2d-f_{n}\). ◻

Lemma 8. Let \(\delta\in I_n\) and \(0<p<f_{n}\) satisfy \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)=\overline{p}\). We have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{1}{\delta} & = \begin{cases} f_{n}-2p&(0\leq p \leq f_{n-2}),\\ f_{n-3}&(f_{n-2}\leq p \leq f_{n-1}),\\ 2p-f_{n}&(f_{n-1}\leq p < f_{n}). \end{cases} \end{align}\]

Proof. In the case where \(s=1\), \(\@ifstar{\equvclassN}{\equvclassP}*{s}\) consists of two equvalent classes \(C_1\) and \(C_2\), which satisfy \(\#C_1=f_{n-1}>\frac{f_{n}}{2}\) and \(\#C_1=f_{n-2}<\frac{f_{n}}{2}\). Hence it follows from that \[\begin{align} &\#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{1}{\delta} =\\& \begin{cases} (f_{n-1}-p)+(f_{n-2}-p)&(0\leq p \leq f_{n-2}),\\ (2f_{n-1}-f_{n})+0&(f_{n-2}\leq p \leq f_{n-1}),\\ (f_{n-1}-(f_{n}-p))+(f_{n-2}-(f_{n}-p))&(f_{n-1}\leq p < f_{n}). \end{cases} \end{align}\] Hence \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{1}{\delta} = \begin{cases} f_{n}-2p&(0\leq p \leq f_{n-2}),\\ f_{n-3}&(f_{n-2}\leq p \leq f_{n-1}),\\ 2p-f_{n}&(f_{n-1}\leq p < f_{n}). \end{cases} \end{align}\] ◻

By Cassini’s identity, \(\overline{f_{n-1}f_{n+1}}=(\overline{-1})^n \in R_{n}\). Since \(\overline{f_{n+1}}=\overline{f_{n-1}}\in R_{n}\), we have \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{f_{n-1}p})=\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}\overline{f_{n-1}p}=\overline{f_{n-1}f_{n-1}p}=(\overline{-1})^n\overline{p}\in R_{n}\). Hence, by , we have .

Now we consider the case where \(s>1\). By using \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}\) instead of \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*\), we also define \(\@ifstar{\samecompN}{\samecompP}{s}\) and \(\@ifstar{\equvclassN}{\equvclassP}{s}\).

Lemma 9. For \(s\in {[f_{n}]}\) and \(d\in {[f_{n}]}\), \[\begin{align} \#\Set{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}|\#C=d}=\#\Set{C\in \@ifstar{\equvclassN}{\equvclassP}{s}|\#C=d}. \end{align}\]

Proof. Let \[\begin{align} X&=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}}| 0\leq t\leq s},\\ X'&=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{t})+\overline{o_{n}}| 0\leq t\leq s}. \end{align}\] Since \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})=-\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{t})\), we have \[\begin{align} X' &=\Set{-\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}}| 0\leq t\leq s}\\ &=\Set{-(x-\overline{o_{n}})+\overline{o_{n}}| \alpha\in X}. \end{align}\] Since \(X\) and \(X'\) define \(\@ifstar{\samecompN}{\samecompP}*{s}\) and \(\@ifstar{\samecompN}{\samecompP}{s}\) respectively, it follows that \[\begin{align} \#\Set{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}|\#C=d}=\#\Set{C\in \@ifstar{\equvclassN}{\equvclassP}{s}|\#C=d}. \end{align}\] ◻

We define \(\@ifstar{\numofclassN}{\numofclassP}*{s}{d}\) to be \[\begin{align} \#\Set{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}|\#C=d}, \end{align}\] i.e., the number of equivalence classes of size \(d\). By , \(\@ifstar{\numofclassN}{\numofclassP}*{s}{d}\) also equals \(\#\Set{C\in \@ifstar{\equvclassN}{\equvclassP}{s}|\#C=d}\).

Example 2. Let \(s=1\). In this case, \[\begin{align} X &=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0})+\overline{o_{n}},\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1})+\overline{o_{n}}} =\Set{\overline{o_{n}+1},\overline{f_{n-2}}+\overline{o_{n}+1}}. \end{align}\] Hence \(\@ifstar{\equvclassN}{\equvclassP}*{s}=\Set{C_1,C_2}\), where \[\begin{align} C_1&=\Set{\overline{i}+\overline{o_{n}}|i\in{[f_{n-2}]}},\\ C_2&=\Set{\overline{f_{n-2}+i}+\overline{o_{n}}|i\in{[f_{n-1}]}}. \end{align}\] Hence \(\@ifstar{\numofclassN}{\numofclassP}{s}{f_{n-2}}=1\), \(\@ifstar{\numofclassN}{\numofclassP}{s}{f_{n-1}}=1\), and \(\@ifstar{\numofclassN}{\numofclassP}{s}{d}=0\) for \(d\neq f_{n-2}, f_{n-1}\).

Example 3. Let \(s=2\). In this case, \[\begin{align} X&=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0})+\overline{o_{n}},\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1})+\overline{o_{n}},\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{2})+\overline{o_{n}}}\\ &=\Set{\overline{0}+\overline{o_{n}},\overline{f_{n-2}}+\overline{o_{n}},2\overline{f_{n-2}}+\overline{o_{n}}}. \end{align}\] Hence \(\@ifstar{\equvclassN}{\equvclassP}*{s}=\Set{C_1,C_2,C_3}\) where \[\begin{align} C_1 &=\Set{\overline{i}+\overline{o_{n}}|i\in {[f_{n-2}]}},\\ C_2&=\Set{\overline{f_{n-2}+i}+\overline{o_{n}}|i\in {[f_{n-2}]}},\\ C_3&=\Set{\overline{f_{n-1}+f_{n-4}+i}+\overline{o_{n}}|i\in {[f_{n-3}]}}. \end{align}\] Hence \(\@ifstar{\numofclassN}{\numofclassP}{s}{f_{n-2}}=2\), \(\@ifstar{\numofclassN}{\numofclassP}{s}{f_{n-3}}=1\), and \(\@ifstar{\numofclassN}{\numofclassP}{s}{d}=0\) for \(d\neq f_{n-2}, f_{n-3}\).

Remark 8. If \(s>1\) and \(n>2\), then \(\#C \leq f_{n-2} < \frac{f_{n}}{2}\) for \(C\in \@ifstar{\equvclassN}{\equvclassP}*{s}\).

Lemma 10. Let \(\delta\in I_n\) and \(0<p<f_{n}\) satisfy \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)=\overline{p}\). For \(1<s<f_{n}\), we have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &= \begin{cases} \displaystyle \sum_{d=p+1}^{f_{n}-1} \@ifstar{\numofclassN}{\numofclassP}*{s}{d}\cdot (d-p) & (1\leq p < \frac{f_{n}}{2}), \\ \displaystyle \sum_{d=f_{n}-p+1}^{f_{n}-1} \@ifstar{\numofclassN}{\numofclassP}*{s}{d}\cdot (d-(f_{n}-p)) & (\frac{f_{n}}{2}\leq p <f_{n}). \end{cases} \end{align}\]

Proof. As in , \(\#C< \frac{f_{n}}{2}\) for \(C\in \@ifstar{\equvclassN}{\equvclassP}*{s}\) for \(s>1\). If \(1\leq p \leq \frac{f_{n}}{2}\), then \(f_{n}-\# C > \frac{f_{n}}{2}\geq p\). Hence it follows from that \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &= \sum_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}\colon \# C > p} \#C-p\\ &= \sum_{d=p+1}^{f_{n}-1} \@ifstar{\numofclassN}{\numofclassP}*{s}{d}\cdot (d-p). \end{align}\] If \(\frac{f_{n}}{2}\leq p < f_{n}\), then \(\# C < \frac{f_{n}}{2}\leq p\). Hence it follows from that \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &= \sum_{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}\colon \# C > f_{n}-p} \#C-(f_{n}-p)\\ &= \sum_{d=f_{n}-p+1}^{f_{n}-1} \@ifstar{\numofclassN}{\numofclassP}*{s}{d}\cdot (d-(f_{n}-p)). \end{align}\] ◻

Next, to calculate \(\@ifstar{\numofclassN}{\numofclassP}*{s}{d}\), we consider the relation of \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*\), \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-1]\) and \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2]\). We define bijections \(\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}\) and \(\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}\) by \[\begin{align} \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}\colon R_{n-2} &\to \widecheck R_{n}\\ \overline{x+o_{n-2}}&\mapsto \overline{x+o_{n}}, \intertext{where x\in{[f_{n-2}]}, and} \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}\colon R_{n-1} &\to \widehat R_{n}\\ \overline{x+o_{n-1}}&\mapsto \overline{x+f_{n-2}+o_{n}}, \end{align}\] where \(x\in{[f_{n-1}]}\). Then we have the following:

Lemma 11. Let \(\iota=\overline{i}, \iota'=\overline{i+1},\iota''=\overline{i+2},\iota'''=\overline{i+3} \in I_n\). Let \(a\in{[f_{n}]}\) satisfy \(\overline{a}=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)\).

  1. If \(0< a\leq f_{n-3}\), then we have the following:

    1. \(f_{n-2}< a+f_{n-2}\leq f_{n-1}\).

    2. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota') +\overline{o_{n}}\in \widehat R_{n}\). Hence \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota')+\overline{o_{n}} \not\in \widecheck R_{n}\).

    3. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}} \in \widehat R_{n}\). Hence \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}} \not\in \widecheck R_{n}\).

    4. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota''')+\overline{o_{n}} \in \widecheck R_{n}\).

    5. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota''')+\overline{o_{n}}=\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2])\).

  2. If \(f_{n-3}< a\leq f_{n-2}\), then we have the following:

    1. \(f_{n-1}< a+f_{n-2} \leq f_{n}\).

    2. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota')+\overline{o_{n}} \in \widehat R_{n}\). Hence \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota')+\overline{o_{n}} \not\in \widecheck R_{n}\).

    3. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}}\in\widecheck R_{n}\).

    4. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}}=\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2])\).

  3. If \(f_{n-2}< a\leq f_{n-1}\), then we have the following:

    1. \(f_{n-1}< a+f_{n-2} \leq f_{n}\).

    2. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota')+\overline{o_{n}} \in \widehat R_{n}\).

    3. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota')+\overline{o_{n}}=\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\widehat \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1])\).

  4. If \(f_{n-1}< a \leq f_{n}\), then we have the following:

    1. \(0 <a+f_{n-2}-f_{n}\leq f_{n-2}\).

    2. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota')+\overline{o_{n}} \in \widecheck R_{n}\). Hence \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota')+\overline{o_{n}} \not\in \widehat R_{n}\).

    3. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}} \in \widehat R_{n}\).

    4. \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}}=\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\widehat \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1])\).

Proof. By direct calculation, we have . follow from .

First we consider . Since \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}}=\overline{a+o_{n}}\in\widecheck R_{n}, \end{align}\] We have \[\begin{align} \widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})=\overline{a+o_{n-2}}\in R_{n-2}. \end{align}\] Hence \[\begin{align} \widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2]=\overline{a+f_{n-4}+o_{n-2}}\in R_{n-2}. \end{align}\] Since \(0< a \leq f_{n-3}\), we have \(0< a+f_{n-4}\leq f_{n-2}\). Hence \[\begin{align} \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2])=\overline{a+f_{n-4}+o_{n}}\in R_{n}. \end{align}\] On the other hand, \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota''')+\overline{o_{n}}=\overline{a+3f_{n-2}+o_{n}}\in R_{n}. \end{align}\] Since \(3f_{n-2}=f_{n}+f_{n-4}\), \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota''')+\overline{o_{n}}=\overline{a+f_{n-4}+o_{n}}\in R_{n}. \end{align}\]

Next we consider . Similar to , we have \[\begin{align} \widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2]=\overline{a+f_{n-4}+o_{n-2}}=\overline{a-f_{n-3}+o_{n-2}}\in R_{n-2}. \end{align}\] Since \(f_{n-3} < a \leq f_{n-2}\), we have \(0< a-f_{n-3}\leq f_{n-2}\). Hence \[\begin{align} \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2])=\overline{a-f_{n-3}+o_{n}}\in R_{n}. \end{align}\] On the other hand, \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}}=\overline{a+2f_{n-2}+o_{n}}\in R_{n}. \end{align}\] Since \(2f_{n-2}=f_{n-1}+f_{n-4}\), \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}} &=\overline{a+f_{n-1}+f_{n-4}+o_{n}}\\ &=\overline{a+f_{n-1}+f_{n-4}-f_{n}+o_{n}}\\ &=\overline{a-f_{n-3}+o_{n}} \in R_{n}. \end{align}\]

Next we consider . Since \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}}=\overline{a+o_{n}}\in\widehat R_{n}, \end{align}\] We have \[\begin{align} \widehat \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})=\overline{a-f_{n-2}+o_{n-1}}\in R_{n-1}. \end{align}\] Hence \[\begin{align} \widehat \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1] &= \overline{a-f_{n-2}+f_{n-2}+o_{n-1}}\\ &=\overline{a+o_{n-1}} \in R_{n-1}. \end{align}\] Since \(f_{n-2}< a \leq f_{n-1}\), we have \[\begin{align} \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\widehat \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1])=\overline{a+f_{n-2}+o_{n}}\in R_{n}. \end{align}\] On the other hand, \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota')+\overline{o_{n}}=\overline{a+f_{n-2}+o_{n}}\in R_{n}. \end{align}\]

Finally we consider . Similar to . \[\begin{align} \widehat \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1] &=\overline{a+o_{n-1}}=\overline{a-f_{n-1}+o_{n-1}} \in R_{n-1}. \end{align}\] Since \(f_{n-1} < a\leq f_{n}\), we have \(0< a-f_{n-1}\leq f_{n-1}\). Hence \[\begin{align} \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\widehat \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1])&=\overline{a-f_{n-1}+f_{n-2}+o_{n}}\\ &=\overline{a-f_{n-3}+o_{n}}\in R_{n}. \end{align}\] On the other hand, \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota'')+\overline{o_{n}}=\overline{a-f_{n-3}+o_{n}}\in R_{n}. \end{align}\] ◻

Now we define maps \(\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*\) from \(I_{n-2}\) to \(\widecheck R_{n}\) and \(\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*\) from \(I_{n-1}\) to \(\widehat R_{n}\). We define \((\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\overline{0}),\ldots,\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\overline{f_{n-2}-1}))\) and \((\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\overline{0}),\ldots,\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\overline{f_{n-1}-1}))\) to be the subsequence of \((\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0}),\ldots,\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{f_{n}-1}))\) such that \(\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\iota)+\overline{o_{n}}\in \widecheck R_{n}\) and \(\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\iota)+\overline{o_{n}}\in \widehat R_{n}\), respectively.

Corollary 9. We have the following:

  1. \(\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\iota)+\overline{o_{n}}=\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2](\iota)+\overline{o_{n-2}})\) for \(\iota\in I_{n-2}\).

  2. \(\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\iota)+\overline{o_{n}}=\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\iota)+\overline{o_{n-1}})\) for \(\iota\in I_{n-1}\).

Proof. Since \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0})+\overline{o_{n}}=\overline{0}+\overline{o_{n}}&\in\widehat R_{n}, \end{align}\] we have \(\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\overline{0})=\overline{0}=\overline{f_{n}}\). Hence \[\begin{align} \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\overline{0})+\overline{o_{n-1}}) &= \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\overline{0+o_{n-1}})\\ &= \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\overline{f_{n-1}+o_{n-1}})\\ &= \overline{f_{n-1}+f_{n-2}+o_{n}}\\ &= \overline{f_{n}+o_{n}}\\ &= \@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\overline{0})+\overline{o_{n}}. \end{align}\] Since \[\begin{align} \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1})+\overline{o_{n}}=\overline{f_{n-2}}+\overline{o_{n}}&\in\widecheck R_{n}, \end{align}\] we have \(\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\overline{0})=\overline{f_{n-2}}\). Hence \[\begin{align} \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-2](\overline{0})+\overline{o_{n-2}}) &= \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\overline{0+o_{n-2}})\\ &= \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\overline{f_{n-2}+o_{n-1}})\\ &= \overline{f_{n-2}+o_{n}}\\ &= \@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\overline{0})+\overline{o_{n}}. \end{align}\] Let \(\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\iota)=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i})=\overline{a}\). Assume that \(\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\iota)+\overline{o_{n}}=\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2](\iota)+\overline{o_{n-2}})\). If \(0<a\leq f_{n-3}\), then \(\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\iota+\overline{1})=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i+3})\) by of . Moreover, by of , we have \[\begin{align} \@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\iota+\overline{1})+\overline{o_{n}} &= \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i+3})+\overline{o_{n}}\\ &= \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2])\\ &= \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2](\iota)+\overline{o_{n-2}}+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2])\\ &= \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2](\iota+\overline{1})+\overline{o_{n-2}}). \end{align}\] If \(f_{n-3}<a\leq f_{n-2}\), then \(\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\iota+\overline{1})=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i+2})\) by of . Moreover, by of , we have \[\begin{align} \@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\iota+\overline{1})+\overline{o_{n}} &= \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i+2})+\overline{o_{n}}\\ &= \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2])\\ &= \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2](\iota)+\overline{o_{n-2}}+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*[n-2])\\ &= \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2](\iota+\overline{1})+\overline{o_{n-2}}). \end{align}\]

Let \(\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\iota)=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i})=\overline{a}\). Assume that \(\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\iota)+\overline{o_{n}}=\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\iota)+\overline{o_{n-1}})\). If \(f_{n-2}<a\leq f_{n-1}\), then \(\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\iota+\overline{1})=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i+1})\) by of . Moreover, by of , we have \[\begin{align} \@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\iota+\overline{1})+\overline{o_{n}} &= \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i+1})+\overline{o_{n}}\\ &= \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\widehat \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1])\\ &= \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\iota)+\overline{o_{n-1}}+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1])\\ &= \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\iota+\overline{1})+\overline{o_{n-1}}). \end{align}\] If \(f_{n-1}<a\leq f_{n}\), then \(\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\iota+\overline{1})=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i+2})\) by of . Moreover, by of , we have \[\begin{align} \@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\iota+\overline{1})+\overline{o_{n}} &= \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i+2})+\overline{o_{n}}\\ &= \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\widecheck \rho_{n}^{-1}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\iota)+\overline{o_{n}})+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1])\\ &= \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\iota)+\overline{o_{n-1}}+\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}[n-1])\\ &= \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\iota+\overline{1})+\overline{o_{n-1}}). \end{align}\] ◻

Next we give explicit description of \(\@ifstar{\numofclassN}{\numofclassP}*{s}{d}\). Let \[\begin{align} \@ifstar{\equvclassLN}{\equvclassLP}*{s}&=\Set{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}| C\subset \widecheck R_{n}},\\ \@ifstar{\equvclassRN}{\equvclassRP}*{s}&=\Set{C\in \@ifstar{\equvclassN}{\equvclassP}*{s}| C\subset \widehat R_{n}}. \end{align}\]

Lemma 12. For \(0<s<f_{n}\), \(\@ifstar{\equvclassN}{\equvclassP}*{s}=\@ifstar{\equvclassLN}{\equvclassLP}*{s}\cup\@ifstar{\equvclassRN}{\equvclassRP}*{s}\).

Proof. The relation \(\@ifstar{\samecompN}{\samecompP}*{s}\) is defined by the set \[\begin{align} X &=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}}|0\leq t\leq s}. \end{align}\] Since \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0})+\overline{o_{n}}=\overline{0}+\overline{o_{n}}\) and \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1})+\overline{o_{n}}=\overline{f_{n-2}}+\overline{o_{n}}\) are in \(X\), \(\alpha\in\widecheck R_{n}\) and \(\alpha'\in\widehat R_{n}\) do not satisfy \(\alpha\@ifstar{\samecompN}{\samecompP}*{s}\alpha'\). Hence each equivalent class is a subset of \(\widecheck R_{n}\) or \(\widehat R_{n}\). ◻

Lemma 13. Let \(2<f_{l}\leq s <f_{l+1}\leq f_{n}\). There exist \(\widecheck{s}\), \(\widehat{s}\), \(\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}*\) and \(\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}*\) such that

  1. \(f_{l-2}-1\leq \widecheck{s}< f_{l-1}\),

  2. \(f_{l-1}-1\leq \widehat{s}< f_{l}\),

  3. \(\widecheck{s}+\widehat{s}=s-1\),

  4. \(\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}*\colon\@ifstar{\equvclassN}{\equvclassP}*[n-2]{\widecheck{s}}\to\@ifstar{\equvclassLN}{\equvclassLP}*{s}\) is a bijection satisfying \(\#\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}*(C)=\#C\) for each \(C\in \@ifstar{\equvclassN}{\equvclassP}*[n-2]{\widecheck{s}}\),

  5. \(\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}*\colon\@ifstar{\equvclassN}{\equvclassP}[n-1]{\widehat{s}} \to\@ifstar{\equvclassRN}{\equvclassRP}*{s}\) is a bijection satisfying \(\#\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}*(C)=\#C\) for \(C\in \@ifstar{\equvclassN}{\equvclassP}*[n-1]{\widehat{s}}\).

Proof. Let \[\begin{align} X&=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}}|0\leq t \leq s}, \end{align}\] Define \(\widecheck{s}=\#X\cap \widecheck R_{n}-1\) and \(\widehat{s}=\#X\cap \widehat R_{n}-1\). Then \(\widecheck{s}+\widehat{s}=(\#X\cap \widecheck R_{n}-1)+(\widehat{s}=\#X\cap \widehat R_{n}-1)=\#X-2=s-1\). Let \[\begin{align} \widecheck{X}&=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2](\overline{i})+\overline{o_{n-2}}|0\leq i\leq \widecheck{s}}\subset R_{n}{n-2},\\ \widehat{X}&=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\overline{i-1})+\overline{o_{n-1}}|0\leq i\leq \widehat{s}}\subset R_{n}{n-1}. \end{align}\] Then \(\widecheck{X}\) defines \(\@ifstar{\samecompN}{\samecompP}*[n-2]{\widecheck{s}}\) and \(\widehat{X}\) defines \(\@ifstar{\samecompN}{\samecompP}[n-1]{\widehat{s}}\). By , we have have \[\begin{align} X\cap \widecheck R_{n} &= \Set{\@ifstar{\widecheck a_{n}^{\ast}}{\widecheck a_{n}}*(\overline{i})+\overline{o_{n}}|0\leq i \leq \widecheck{s}} \\ &= \Set{\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*[n-2](\overline{i})+\overline{o_{n-2}})|0\leq i \leq\widecheck{s}} \\ &= \Set{\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\alpha)|\alpha\in \widecheck X}, \\ X\cap \widehat R_{n} &= \Set{\@ifstar{\widehat a_{n}^{\ast}}{\widehat a_{n}}*(\overline{i})+\overline{o_{n}}|0\leq i \leq \widehat{s}}\\ &= \Set{\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\@ifstar{a_{{n}}^{\ast}}{a_{n}}[n-1](\overline{i})+\overline{o_{n-1}})|0\leq i \leq\widehat{s}}\\ &= \Set{\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\alpha)|\alpha \in \widehat X} . \end{align}\] Hence \(\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}\) and \(\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}\) induce bijections \[\begin{align} \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}*\colon \@ifstar{\equvclassN}{\equvclassP}*[n-2]{\widecheck{s}}&\to\@ifstar{\equvclassLN}{\equvclassLP}*{s}\\ C&\mapsto \Set{\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}(\alpha)| \alpha\in C},\\ \@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}*\colon \@ifstar{\equvclassN}{\equvclassP}[n-1]{\widehat{s}} &\to\@ifstar{\equvclassRN}{\equvclassRP}*{s}\\ C&\mapsto \Set{\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}(\alpha)| \alpha\in C}. \end{align}\] Since \(\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}\) and \(\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}\) are bijective, \(\#\@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}*(C)=\#C\) and \(\#\@ifstar{\widehat \varrho_{n}}{\widehat \rho_{n}}*(C)=\#C\) for any \(C\).

Now we consider \(\widecheck{s}=\#X\cap \widecheck R_{n}-1\) and \(\widecheck{s}=\#X\cap \widecheck R_{n}-1\). If \(n\) is odd, then \(o_{n}=0\). Hence \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i})+\overline{o_{n}}=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i})\) and \[\begin{align} X&=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}}|0\leq t \leq s}\\ &=\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})|0\leq t \leq s}. \end{align}\] By , we have \(f_{l-2}\leq\#X\cap\widecheck R_{n}\leq f_{l-1}\) and \(f_{l-1}\leq\#X\cap\widehat R_{n}\leq f_{l}\). These imply \(f_{l-2}-1\leq \widecheck{s}< f_{l-1}\) and \(f_{l-1}-1\leq \widehat{s}< f_{l}\). If \(n\) is even, then \(o_{n}=-1\). Hence \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i})+\overline{o_{n}}=\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{i})-\overline{1}\). For \(a\in{[f_{n}]}\setminus\Set{f_{n-2},f_{n}}\), \(\overline{a}\in\widecheck R_{n}=\Set{\overline{0},\ldots,\overline{f_{n-2}-1}}\) means \(a\in \Set{1,\ldots,f_{n-2}-1}\), which implies \(\overline{a+o_{n}}\in\widecheck R_{n}\). Similarly. \(\overline{a}\in\widehat R_{n}=\Set{\overline{f_{n-2}},\ldots,\overline{f_{n}-1}}\) means \(a\in \Set{f_{n-2}+1,\ldots,f_{n-2}-1}\), which implies \(\overline{a+o_{n}}\in\widehat R_{n}\). Hence we have \[\begin{align} \alpha\in\widecheck R_{n}\iff\alpha+\overline{o_{n}}\in\widecheck R_{n},\\ \alpha\in\widehat R_{n}\iff\alpha+\overline{o_{n}}\in\widehat R_{n} \end{align}\] for \[\begin{align} \alpha\in R_{n}\setminus\Set{\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0})=\overline{0}=\overline{f_{n}},\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1})=\@ifstar{\gamma_{{n}}^{\ast}}{\gamma_{n}}*=\overline{f_{n-2}}}. \end{align}\] Since \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0})\in \widecheck R_{n}\), \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1})=\widehat R_{n}\), \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{0})+\overline{o_{n}}\in \widehat R_{n}\), \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{1})+\overline{o_{n}}=\widecheck R_{n}\), we have \[\begin{align} \#\Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}}\in\widecheck R_{n}} &=\#\Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in\widecheck R_{n}},\\ \#\Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})+\overline{o_{n}}\in\widehat R_{n}} &=\#\Set{t|0\leq t \leq s, \@ifstar{a_{{n}}^{\ast}}{a_{n}}*(\overline{t})\in\widehat R_{n}} \end{align}\] for \(s\geq 1\). By , we have \(f_{l-2}\leq\#X\cap\widecheck R_{n}\leq f_{l-1}\) and \(f_{l-1}\leq\#X\cap\widehat R_{n}\leq f_{l}\). These imply \(f_{l-2}-1\leq \widecheck{s}< f_{l-1}\) and \(f_{l-1}-1\leq \widehat{s}< f_{l}\). ◻

Propsition 10. For \(0<f_{l} \leq s <f_{l+1}<f_{n}\), \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*{s}{d}&= \begin{cases} f_{l+1}-(s+1)&(d=f_{n-l+1}),\\ s+1-f_{l-1}&(d=f_{n-l}),\\ s+1-f_{l}&(d=f_{n-l-1}),\\ 0&(\text{otherwise}). \end{cases} \end{align}\]

Proof. We show the equations by induction on \(s\). The cases where \(s=1\) with \(l=1\) and \(s=2\) with \(l=2\) are the base cases, which are in .

By , We obtain bijections \[\begin{align} \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}*\colon\@ifstar{\equvclassN}{\equvclassP}*[n-2]{\widecheck{s}}&\to\@ifstar{\equvclassLN}{\equvclassLP}*{s},\\ \@ifstar{\widecheck \varrho_{n}}{\widecheck \rho_{n}}*\colon\@ifstar{\equvclassN}{\equvclassP}*[n-1]{\widehat{s}}&\to\@ifstar{\equvclassRN}{\equvclassRP}*{s} \end{align}\] with \(f_{l-2}-1\leq \widecheck{s}<f_{l-1}\) and \(f_{l-1}-1\leq \widehat{s}<f_{l}\). Hence we have \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*{s}{d} &=\@ifstar{\numofclassN}{\numofclassP}*[n-2]{\widecheck{s}}{d}+\@ifstar{\numofclassN}{\numofclassP}*[n-1]{\widehat{s}}{d}. \end{align}\] Note that, for \(s=f_{l}-1\), we have \[\begin{align} &\begin{cases} f_{l+1}-(s+1)=f_{l-1}&(d=f_{n-l+1}),\\ s+1-f_{l-1}=f_{l-2}&(d=f_{n-l}),\\ s+1-f_{l}=0&(d=f_{n-l-1}),\\ 0&(\text{otherwise}) \end{cases} \\ ={}& \begin{cases} f_{l}-(s+1)=0&(d=f_{n-l+2)}),\\ s+1-f_{l-2}=f_{l-1}&(d=f_{n-l+1}),\\ s+1-f_{l-1}=f_{l-2}&(d=f_{n-l}),\\ 0&(\text{otherwise}). \end{cases} \end{align}\] Hence, by induction hypothesis, we have \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*[n-2]{\widecheck{s}}{d}&= \begin{cases} f_{l-1}-(\widecheck{s}+1)&(d=f_{n-2-(l-3)}=f_{n-l+1}),\\ \widecheck{s}+1-f_{l-3}&(d=f_{n-2-(l-2)}=f_{n-l}),\\ \widecheck{s}+1-f_{l-2}&(d=f_{n-2-(l-1)}=f_{n-l-1}),\\ 0&(\text{otherwise}), \end{cases} \\ \@ifstar{\numofclassN}{\numofclassP}*[n-1]{\widehat{s}}{d}&= \begin{cases} f_{l}-(\widehat{s}+1)&(d=f_{n-1-(l-2)}=f_{n-l+1}),\\ \widehat{s}+1-f_{l-2}&(d=f_{n-1-(l-1)}=f_{n-l}),\\ \widehat{s}+1-f_{l-1}&(d=f_{n-1-l}=f_{n-l-1}),\\ 0&(\text{otherwise}). \end{cases} \end{align}\] Hence, for \(d=f_{n-l+1}\), \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*{s}{d} &= f_{l-1}-(\widecheck{s}+1)+f_{l}-(\widehat{s}+1)= f_{l+1}-(s+1). \end{align}\] For \(d=f_{n-l}\), \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*{s}{d} &= \widecheck{s}+1-f_{l-3}+\widehat{s}+1-f_{l-2} =s+1-f_{l-1}. \end{align}\] For \(d=f_{n-l-1}\), \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*{s}{d} &= \widecheck{s}+1-f_{l-2}+\widehat{s}+1-f_{l-1} = s+1-f_{k}. \end{align}\] For \(d\not\in\Set{f_{n-l},f_{n-l-1},f_{n-l-2}}\), we have \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*{s}{d} &=0+0=0. \end{align}\] ◻

Corollary 11. For \(0<f_{l} \leq s <f_{l+1}<f_{n}\), we have \[\begin{align} \Set{\# C |C\in \@ifstar{\equvclassN}{\equvclassP}*{s}} &= \begin{cases} \Set{f_{n-l-1},f_{n-l}}&(s=f_{l+1}-1),\\ \Set{f_{n-l-1},f_{n-l},f_{n-l+1}}&(s< f_{l+1}-1). \end{cases} \end{align}\]

Proof. If \(s=f_{l+1}-1\), then \(f_{l+1}-(s+1)=0\). Hence \(\@ifstar{\numofclassN}{\numofclassP}*{s}{f_{n-l+1}}=0\). ◻

Theorem 4. Let \(\delta\in I_n\) and \(0<p<f_{n}\) satisfy \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)=\overline{p}\). For \(1<f_{l}\leq s<f_{l+1}<f_{n}\), \[\begin{align} &\#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} =\\& \begin{cases} f_{n}-p(s+1) & (0< p<f_{n-l-1}), \\ f_{n-l-1}(f_{l+1}-(s+1))+f_{l}(f_{n-l}-p) & (f_{n-l-1}\leq p<f_{n-l}), \\ (f_{l+1}-(s+1))(f_{n-l+1}-p) & (f_{n-l}\leq p<f_{n-l+1}), \\ 0 & (f_{n-l+1}\leq p\leq f_{n}-f_{n-l+1}), \\ (f_{l+1}-(s+1))(f_{n-l+1}-(f_{n}-p)) & (f_{n}-f_{n-l+1}\leq p \leq f_{n}-f_{n-l}), \\ f_{n-l-1}(f_{l+1}-(s+1))+f_{l}(f_{n-l}-(f_{n}-p)) & (f_{n}-f_{n-l} < p\leq f_{n}-f_{n-l-1}), \\ f_{n}-(f_{n}-p)(s+1) & (f_{n}-f_{n-l-1}< p< f_{n}). \end{cases} \end{align}\]

Proof. By , for \(d\not\in\Set{f_{n-l-1},f_{n-l},f_{n-l+1}}\), we have \(\@ifstar{\numofclassN}{\numofclassP}{s}{d}=0\). Hence, by , we have \(\#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta}=0\) for \(f_{n-l+1} \leq p \leq \frac{f_{n}}{2}\). Similarly, for \(\frac{f_{n}}{2}\leq p\leq f_{n}-f_{n-l+1}\), we have \(\#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta}=0\). For \(f_{n-l} \leq p< f_{n-l+1}\), we have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &=(f_{l+1}-(s+1))(f_{n-l+1}-p). \end{align}\] Similarly, for \(f_{n}-f_{n-l+1}\leq p \leq f_{n}-f_{n-l}\), we have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &=(f_{l+1}-(s+1))(f_{n-l+1}-(f_{n}-p)). \end{align}\] For \(f_{n-l-1} \leq p <f_{n-l}\), we have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &=(f_{l+1}-(s+1))(f_{n-l+1}-p)+(s+1-f_{l-1})(f_{n-l}-p)\\ &=(s+1-f_{l-1})f_{n-l}-(s+1-f_{l-1})p\\ &\quad+(f_{l+1}-(s+1))f_{n-l+1}-(f_{l+1}-(s+1))p\\ &=(s+1-f_{l-1})f_{n-l}+(f_{l+1}-(s+1))f_{n-l+1}-f_{l}p\\ &=(s+1)f_{n-l}-f_{l-1}f_{n-l}+f_{l+1}f_{n-l+1}-(s+1)f_{n-l+1}-f_{l}p\\ &=-(s+1)f_{n-l-1}-f_{l-1}f_{n-l}+f_{l+1}f_{n-l+1}-f_{l}p\\ &=-(s+1)f_{n-l-1}-f_{l-1}f_{n-l}+f_{l+1}f_{n-l}+f_{l+1}f_{n-l-1}-f_{l}p\\ &=(f_{l+1}-(s+1))f_{n-l-1}+(f_{l+1}-f_{l-1})f_{n-l}-f_{l}p\\ &=(f_{l+1}-(s+1))f_{n-l-1}+f_{l}f_{n-l}-f_{l}p\\ &=(f_{l+1}-(s+1))f_{n-l-1}+f_{l}(f_{n-l}-p). \end{align}\] Similarly, for \(f_{n}-f_{n-(l)} < p\leq f_{n}-f_{n-(l+1)}\), we have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} f_{n-l-1}(f_{l+1}-(s+1))+f_{l}(f_{n-l}-(f_{n}-p)). \end{align}\] For \(1\leq p < f_{n-l-1}\), we have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} &= (f_{l+1}-(s+1))(f_{n-l+1}-p)\\ &\quad +(s+1-f_{l-1})(f_{n-l}-p) +(s+1-f_{l})(f_{n-l-1}-p)\\ &=(f_{l+1}-(s+1))f_{n-l-1}+f_{l}(f_{n-l}-p)+(s+1-f_{l})(f_{n-l-1}-p)\\ &=(f_{l+1}-(s+1)+(s+1-f_{l}))f_{n-l-1}+f_{l}(f_{n-l}-p)-(s+1-f_{l})p\\ &=f_{l-1}f_{n-l-1}+f_{l}(f_{n-l}-p)-(s+1-f_{l})p\\ &=f_{l-1}f_{n-l-1}+f_{l}(f_{n-l}-p+p)-(s+1)p\\ &=f_{l-1}f_{n-l-1}+f_{l}f_{n-l}-(s+1)p\\ &=f_{n}-(s+1)p. \end{align}\] Similarly, for \(f_{n}-f_{n-l-1}< p< f_{n}\), we have \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta}= f_{n}-(f_{n}-p)(s+1). \end{align}\] ◻

Considering the case where \(s=f_{l+1}-1\), we have the following:

Corollary 12. Let \(\delta\in I_n\) and \(0<p<f_{n}\) satisfy \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)=\overline{p}\). For \(1<l\leq n-2\), \[\begin{align} &\#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{f_{l+1}-1}{\delta}\\ &= \begin{cases} f_{n}-pf_{l+1} & (0<p <f_{n-l-1}), \\ (f_{n-l}-p)f_{l} & (f_{n-l-1}\leq p<f_{n-l}), \\ 0 & (f_{n-l}\leq p \leq f_{n}-f_{n-l}), \\ (f_{n-l}-(f_{n}-p))f_{l} & (f_{n}-f_{n-l}< p\leq f_{n}-f_{n-l}-1), \\ f_{n}-(f_{n}-p)f_{l+1} & (f_{n}-f_{n-l}-1< p <f_{n}) . \end{cases} \end{align}\]

By Cassini’s identity, we have \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{f_{n-1}p})=(\overline{-1})^n\overline{p}\in R_{n}\). Hence imply .

Finally we consider the case where \(f_{n-1} \leq s <f_{n}\).

Propsition 13. For \(f_{n-1} \leq s <f_{n}\), \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*{s}{d}&= \begin{cases} f_{n-1}-(s+1)&(d=2),\\ 2(s+1)-f_{n-1}&(d=1),\\ 0&(\text{otherwise}). \end{cases} \end{align}\]

Proof. By , For \(0<f_{l} \leq s <f_{l+1}<f_{n}\), \[\begin{align} \@ifstar{\numofclassN}{\numofclassP}*{f_{n-1}-1}{d}&= \begin{cases} f_{n-1}-f_{n-3}=f_{n-2}&(d=f_{2}),\\ f_{n-1}-f_{n-2}=f_{n-3}&(d=f_{1}),\\ 0&(\text{otherwise}). \end{cases} \end{align}\] Hence, for each class \(C\) in \(\@ifstar{\equvclassN}{\equvclassP}*{f_{n-1}-1}\), we have \(\#C=2\) or \(\#C=1\). For \(0<f_{l} \leq s <f_{l+1}<f_{n}\), \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}*(s)\) is in some \(C\) in \(\@ifstar{\equvclassN}{\equvclassP}*{f_{n-1}-1}\) with \(\#C=2\) and \(C\) splits into two classes of size \(1\) in \(\@ifstar{\equvclassN}{\equvclassP}*{s}\). Hence we have the equation. ◻

Theorem 5. Let \(\delta\in I_n\) and \(0<p<f_{n}\) satisfy \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\delta)=\overline{p}\). For \(1<f_{n-1}\leq s<f_{n}\), \[\begin{align} \#\@ifstar{\pairII}{\pairI}*{\@ifstar{w_{n}^{\ast}}{w_{n}}}{s}{\delta} = \begin{cases} f_{n}-(s+1) &(p=1)\\ 0&(1<p<f_{n-1})\\ f_{n}-(s+1) &(p=f_{n}-1). \end{cases} \end{align}\]

Proof. By , we have the equation. ◻

By Cassini’s identity, we have \(\@ifstar{a_{{n}}^{\ast}}{a_{n}}(\overline{f_{n-1}p})=(\overline{-1})^n\overline{p}\in R_{n}\). Hence implies .

References↩︎

[1]
Aviezri S. Fraenkel and Jamie Simpson, How many squares can a string contain?, J. Combin. Theory Ser. A 82(1998), no. 1, 112–120, URL https://doi.org/10.1006/jcta.1997.2843.
[2]
Lucian Ilie, A note on the number of squares in a word, Theoret. Comput. Sci. 380(2007), no. 3, 373–376, URL https://doi.org/10.1016/j.tcs.2007.03.025.
[3]
Antoine Deza, Frantisek Franek, and Adrien Thierry, How many double squares can a string contain?, Discrete Appl. Math. 180(2015), 52–69, URL https://doi.org/10.1016/j.dam.2014.08.016.
[4]
Adrien Thierry, A proof that a word of length \(n\) has less than \(1.5n\) distinct squares, arXiv preprint arXiv:2001.02996 (2020).
[5]
Srečko Brlek and Shuo Li, On the number of squares in a finite word, Comb. Theory 5(2025), no. 1, Paper No. 3, 12, URL https://doi.org/10.5070/c65165014.
[6]
Roman Kolpakov, Mikhail Podolskiy, Mikhail Posypkin, and Nickolay Khrapov, Searching of gapped repeats and subrepetitions in a word, J. Discrete Algorithms 46/47(2017), 1–15, URL https://doi.org/10.1016/j.jda.2017.10.004.
[7]
Roman Kolpakov and Gregory Kucherov, On maximal repetitions in words, Fundamentals of computation theory (Ia¥c si, 1999), Lecture Notes in Comput. Sci., vol. 1684, Springer, Berlin, 1999, pp. 374–385, URL https://doi.org/10.1007/3-540-48321-7_31.
[8]
Maxime Crochemore, Roman Kolpakov, and Gregory Kucherov, Optimal bounds for computing \(¥alpha\)-gapped repeats, Language and automata theory and applications, Lecture Notes in Comput. Sci., vol. 9618, Springer, [Cham], 2016, pp. 245–255, URL https://doi.org/10.1007/978-3-319-30000-9_19.
[9]
Pawe¥l Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik K¥"oppl, and Florin Manea, Tighter bounds and optimal algorithms for all maximal \(¥alpha\)-gapped repeats and palindromes: finding all maximal \(¥alpha\)-gapped repeats and palindromes in optimal worse case time on integer alphabets, Theory Comput. Syst. 62(2018), no. 1, 162–191, URL https://doi.org/10.1007/s00224-017-9794-5.
[10]
Tomohiro I and Dominik K¥"oppl, Improved upper bounds on all maximal \(¥alpha\)-gapped repeats and palindromes, Theoret. Comput. Sci. 753(2019), 1–15, URL https://doi.org/10.1016/j.tcs.2018.06.033.
[11]
Costas S. Iliopoulos, Dennis Moore, and W. F. Smyth, A characterization of the squares in a Fibonacci string, Theoret. Comput. Sci. 172(1997), no. 1-2, 281–291, URL https://doi.org/10.1016/S0304-3975(96)00141-7.
[12]
Kaisei Kishi, Yuto Nakashima, and Shunsuke Inenaga, Largest repetition factorization of Fibonacci words, String processing and information retrieval, Lecture Notes in Comput. Sci., vol. 14240, Springer, Cham, [2023]©2023, pp. 284–296, URL https://doi.org/10.1007/978-3-031-43980-3_23.
[13]
, On maximal repetitions in words, Fundamentals of computation theory (Iaşi, 1999), Lecture Notes in Comput. Sci., vol. 1684, Springer, Berlin, 1999, pp. 374–385, URL https://doi.org/10.1007/3-540-48321-7_31.
[14]
Guy Melançon, Lyndon factorization of Sturmian words, Discrete Math. 210(2000), no. 1-3, 137–149, Formal power series and algebraic combinatorics (Minneapolis, MN, 1996), URL https://doi.org/10.1016/S0012-365X(99)00123-5.
[15]
, The exact number of squares in Fibonacci words, Theoret. Comput. Sci. 218(1999), no. 1, 95–106, WORDS (Rouen, 1997), URL https://doi.org/10.1016/S0304-3975(98)00252-7.
[16]
Kazuma Yamane, Yuto Nakashima, Kazuhisa Seto, and Takashi Horiyama, Maximal \(¥alpha\)-gapped repeats in a Fibonacci string, SOFSEM 2025: theory and practice of computer science. Part II, Lecture Notes in Comput. Sci., vol. 15539, Springer, Cham, [2025] ¥copyright 2025, pp. 337–350, URL https://doi.org/10.1007/978-3-031-82697-9_25.

  1. The first and third authors were partially supported by JSPS KAKENHI Grant Number JP22H03549. The second author was partially supported by JSPS KAKENHI Grant Number JP23K17298. The second and fourth authors were partially supported by JSPS KAKENHI Grant Number JP23H00081.↩︎

Subjects

Combinatorics (math.CO)

Formal Languages and Automata Theory (cs.FL)

Updated on Academus

2026/06/11 21:23 UTC