April 28, 2025
Zeckendorf’s theorem states that every positive integer can be uniquely decomposed into nonadjacent Fibonacci numbers. On the other hand, Chung and Graham proved that every positive integer can be uniquely written as a sum of even-indexed Fibonacci numbers with coefficients \(0,1\), or \(2\) such that between two coefficients \(2\), there is a coefficient \(0\). We discover a correspondence between a lexicographically ordered sublist of Zeckendorf decompositions and letters in the golden string \(\mathcal{S}\). Likewise, we identify a dual correspondence for Chung-Graham decompositions. We then use these correspondences to give the set of all positive integers having \(F_{2k}\) in both of their Zeckendorf and Chung-Graham decompositions.
For \(n\in \mathbb{N}\cup \{0\}\), let \(F_n\) be the \(n\)th Fibonacci number, i.e., \(F_{n+2} = F_{n+1} + F_n\) for all \(n\ge 0\) with \(F_0 = 0\) and \(F_1 = 1\). Zeckendorf’s theorem [1] states that every positive integer can be written uniquely as a sum of nonadjacent Fibonacci numbers in \((F_n)_{n=2}^\infty\). This sum is often called the Zeckendorf decomposition of integers, which can be found by the greedy algorithm. For example, the largest Fibonacci number in the Zeckendorf decomposition of \(28\) is \(F_{8} = 21\) because \(F_8\) is the largest Fibonacci number not greater than \(28\). The next term in the decomposition is the largest Fibonacci number at most \(28-21 = 7\), which is \(F_5 = 5\). The remainder after taking out \(F_5\) is \(7-5 = 2 = F_3\); hence, \[28 \;=\;21 + 5 + 2 \;=\;F_8 + F_5 + F_3.\] There has been extensive research on the structure of the Zeckendorf decomposition and its generalizations. For a sample of notable work, see [2]–[19].
On the other hand, Chung and Graham [20] proved that every positive integer can be uniquely written as a sum of even-indexed Fibonacci numbers using coefficients \(0, 1\), or \(2\) such that between two coefficients \(2\), there exists a coefficient \(0\). We call the sum the Chung-Graham decomposition of \(n\).
Theorem 1. [20] Every positive integer \(n\) can be uniquely represented as a sum \[n\;=\;\sum_{i = 1}^\infty c_i F_{2i},wherec_i\in \{0, 1, 2\},\] so that if \(c_{i_1} = c_{i_2} = 2\), then there exists \(j\) between \(i_1\) and \(i_2\) such that \(c_j = 0\).
The proof of [20] showed that the Chung-Graham decomposition is also determined by the greedy algorithm. At each step, we find the largest \(j\) such that \(F_{2j}\) is not greater than the remainder. If \(2F_{2j}\) is also less than the remainder, the next term is \(2F_{2j}\); otherwise, the next term is \(F_{2j}\). For example, \[141 \;=\;2F_{10} + F_{8} + F_6 + 2F_2.\]
Recent work generalized the Chung-Graham decomposition to use equally-spaced Fibonacci numbers [21], studied the conversion between Zeckendorf and Chung-Graham decompositions [22], and characterized integers without a fixed term in their Chung-Graham decompositions [23], thus continuing the work by Kimberling [24] who characterized integers without \(F_2\) in their Zeckendorf decompositions and by Griffiths [25] who characterized integers having \(F_k\) in their Zeckendorf decompositions. These results inspired us to discover a correspondence between a lexicographically ordered sublist of Zeckendorf decompositions and letters in the golden string \(\mathcal{S}\). Likewise, we identify a dual correspondence for Chung-Graham decompositions. We then use these correspondences to characterize integers that have \(F_{2k}\) in both Zeckendorf and Chung-Graham decompositions.
To formally state our results, let us recall the golden string \(\mathcal{S}\). We start with \(S_1 = B\), \(S_2 = BA\), and \(S_n = S_{n-1}:S_{n-2}\) for \(n\ge 3\), where \(S_{n-1}:S_{n-2}\) is the concatenation of the two finite strings. For example, \[\begin{align} S_3 &\;=\;S_2: S_1\;=\;BAB,\\ S_4 &\;=\;S_3:S_2\;=\;BABBA,and\\ S_5 &\;=\;S_4:S_3\;=\;BABBABAB. \end{align}\] It follows that \(|S_n| = F_{n+1}\) for all \(n\ge 1\). The golden string \(\mathcal{S}\) is the infinite string whose first \(F_{n+1}\) letters is the same as the finite string \(S_n\). In other words, \(\mathcal{S} = \lim_{n\rightarrow \infty} S_n\) in the sense that for every \(i\), the \(i\)th letter of \(\mathcal{S}\), denoted by \(\mathcal{S}(i)\), is the same as the \(i\)th letter of \(S_n\) for sufficiently large \(n\). The first few letters of \(\mathcal{S}\) are \[BABBABABBABBABABBABAB\ldots\,.\]
Throughout the paper, we fix \(k\ge 1\). Let \(A_{2k}\) be the set of all positive integers whose Zeckendorf decomposition has \(F_{2k}\) as the smallest summand. Let \(p(j)\) be the \(j\)th smallest integer in \(A_{2k}\). Similarly, let \(B_{2k}\) be the set of all positive integers whose Chung-Graham decomposition has \(F_{2k}\) or \(2F_{2k}\) as the smallest summand. Let \(q(j)\) be the \(j\)th smallest integer in \(B_{2k}\). For a positive integer \(n\), we use \(Z(n)\) and \(CG(n)\) to denote the set of all Fibonacci numbers in the Zeckendorf decomposition and the Chung-Graham decomposition of \(n\), respectively.
| \(A_{2k}\) | \(Z(p(j))\) | \(F_{2k}\in CG(p(j))\) ? | \(\mathcal{S}\) | ||||||
|---|---|---|---|---|---|---|---|---|---|
| \(p(1)\) | \(F_{2k}\) | Y | |||||||
| \(p(2)\) | \(F_{2k}\) | \(F_{2k+2}\) | Y | B | |||||
| \(p(3)\) | \(F_{2k}\) | \(F_{2k+3}\) | N | A | |||||
| \(p(4)\) | \(F_{2k}\) | \(F_{2k+4}\) | Y | B | |||||
| \(p(5)\) | \(F_{2k}\) | \(F_{2k+2}\) | \(F_{2k+4}\) | Y | B | ||||
| \(p(6)\) | \(F_{2k}\) | \(F_{2k+5}\) | N | A | |||||
| \(p(7)\) | \(F_{2k}\) | \(F_{2k+2}\) | \(F_{2k+5}\) | Y | B | ||||
| \(p(8)\) | \(F_{2k}\) | \(F_{2k+3}\) | \(F_{2k+5}\) | N | A | ||||
| \(p(9)\) | \(F_{2k}\) | \(F_{2k+6}\) | Y | B | |||||
| \(p(10)\) | \(F_{2k}\) | \(F_{2k+2}\) | \(F_{2k+6}\) | Y | B | ||||
| \(p(11)\) | \(F_{2k}\) | \(F_{2k+3}\) | \(F_{2k+6}\) | N | A | ||||
| \(p(12)\) | \(F_{2k}\) | \(F_{2k+4}\) | \(F_{2k+6}\) | Y | B | ||||
| \(p(13)\) | \(F_{2k}\) | \(F_{2k+2}\) | \(F_{2k+4}\) | \(F_{2k+6}\) | Y | B | |||
| ⋮ |
| \(B_{2k}\) | \(CG(q(j))\) | \(F_{2k}\in Z(q(j))\)? | \(\mathcal{S}\) | |||||
|---|---|---|---|---|---|---|---|---|
| \(q(1)\) | \(F_{2k}\) | Y | ||||||
| \(q(2)\) | \(2F_{2k}\) | N | B | |||||
| \(q(3)\) | \(F_{2k}\) | \(F_{2k+2}\) | Y | A | ||||
| \(q(4)\) | \(2F_{2k}\) | \(F_{2k+2}\) | N | B | ||||
| \(q(5)\) | \(F_{2k}\) | \(2F_{2k+2}\) | N | B | ||||
| \(q(6)\) | \(F_{2k}\) | \(F_{2k+4}\) | Y | A | ||||
| \(q(7)\) | \(2F_{2k}\) | \(F_{2k+4}\) | N | B | ||||
| \(q(8)\) | \(F_{2k}\) | \(F_{2k+2}\) | \(F_{2k+4}\) | Y | A | |||
| \(q(9)\) | \(2F_{2k}\) | \(F_{2k+2}\) | \(F_{2k+4}\) | N | B | |||
| \(q(10)\) | \(F_{2k}\) | \(2F_{2k+2}\) | \(F_{2k+4}\) | N | B | |||
| \(q(11)\) | \(F_{2k}\) | \(2F_{2k+4}\) | Y | A | ||||
| \(q(12)\) | \(2F_{2k}\) | \(2F_{2k+4}\) | N | B | ||||
| \(q(13)\) | \(F_{2k}\) | \(F_{2k+2}\) | \(2F_{2k+4}\) | N | B | |||
| ⋮ |
Tables 1 and 2 list the values of \(A_{2k}\) and \(B_{2k}\), and they suggest the following duality of correspondences between the decompositions and the golden string \(\mathcal{S}\).
Theorem 2. For \(j\ge 2\), the integer \(p(j)\) in \(A_{2k}\) has \(F_{2k}\in CG(p(j))\) if and only if \(\mathcal{S}(j-1) = B\). Moreover, \(\min CG(p(j))\ge F_{2k}\) for all \(p(j)\in A_{2k}\).
Theorem 3. For \(j\ge 2\), the integer \(q(j)\) in \(B_{2k}\) has \(F_{2k}\in Z(q(j))\) if and only if \(\mathcal{S}(j-1) = A\). Moreover, \(\min Z(q(j))\ge F_{2k-2}\) for all \(q(j)\in B_{2k}\).
Using these correspondences, we obtain the complete description of all integers \(n\) with \(F_{2k}\in Z(n)\cap CG(n)\).
Theorem 4. For \(k\ge 1\), the set of positive integers that have \(F_{2k}\) in both Zeckendorf and Chung-Graham decompositions is \[\{nF_{2k}+\lfloor(n-1)\phi\rfloor F_{2k+1} + j\;:\;n\in \mathbb{N},\, 0\leq j\leq F_{2k-1}-1\}\] where \(\phi = (1+\sqrt{5})/2\), the golden ratio.
Our paper is structured as follows. Section 2 demonstrates the conversions between the two decompositions. Section 3 proves the duality of correspondences, namely Theorems 2 and 3. Finally, Section 4 is devoted to prove Theorem 4. The proofs of the conversion statements in Section 2 are found in Appendix 5.
We discuss conversions between the two decompositions. Each conversion result can be proved by induction on the number of terms. In this section, however, we emphasize the mechanics of the conversions, while their proofs are provided in Appendix 5 for interested readers.
Let us use the subscript tags $ {}$ and $ {}$ to indicate that a decomposition is a Zeckendorf or Chung-Graham decomposition, respectively; for example, \[F_{2} + F_4 + 2F_8 + F_{10} + 2F_{14}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\;=\;F_4 + F_7 + F_{10} + F_{12} + F_{15}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\]
Lemma 5. For \(N\in \mathbb{N}\), let \(\sum_{m=1}^Na_mF_{2k+2m+1}\) be a Zeckendorf decomposition with \(a_N = 1\). Then there exist coefficients \(b\) and \((b_m)_{m=2}^{N}\) with \(b, b_N\in \{1,2\}\) such that \[\label{e1}F_{2k} + \sum_{m=1}^N a_mF_{2k+2m+1}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\;=\;bF_{2k+2} + \sum_{m=2}^N b_mF_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}.\qquad{(1)}\]
Corollary 6 (Conversion to Chung-Graham decompositions). Let \(r\ge 1\) and \(N\ge 2r\). Given each Zeckendorf decomposition below, there exist coefficients \(b\in \{1,2\}\) and \((b_m)_{2\le m\le 2\lfloor N/2\rfloor}\) such that \[\label{e3} F_{2k} + F_{2k+2r+1} + \sum_{m=2r+3}^N a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\;=\;bF_{2k+2} + \sum_{m=4}^{2\lfloor N/2\rfloor} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\qquad{(2)}\] and \[\label{e4} F_{2k} + F_{2k+2r} + \sum_{m=2r+2}^N a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\;=\;F_{2k} + \sum_{m=2}^{2\lfloor N/2\rfloor} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}.\qquad{(3)}\]
Lemma 7 (Conversion to Zeckendorf decompositions). Let \(M\ge 0\) be even and \(b_M\in \{1,2\}\). Given each Chung-Graham decomposition below, there exist coefficients \((a_m)_{m=1}^{M+1}\) such that \[\label{e6} 2F_{2k} + \sum_{m=2}^M b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\;=\;F_{2k-2} + \sum_{m=1}^{M+1} a_m F_{2k+m} _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\qquad{(4)}\] and \[\label{e7} F_{2k} + \sum_{m=2}^M b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\;=\;\begin{cases}F_{2k-2} + \sum_{m=1}^{M+1} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}},\\ F_{2k} + \sum_{m=1}^{M+1} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\end{cases}\qquad{(5)}\] In the case \(k = 1\), we remove \(F_{2k-2} = 0\) from the Zeckendorf decomposition.
In this section, we establish the correspondence between the golden string \(\mathcal{S}\) and the integers \(p(j)\in A_{2k}\) with \(\min CG(p(j)) = F_{2k}\). An analog of the correspondence holds between \(\mathcal{S}\) and the integers \(q(j)\in B_{2k}\) with \(\min Z(q(j)) = F_{2k}\).
Lemma 8. [26]Let \(n = F_c + \sum_{m=c+2}^N a_m F_m _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\), i.e., \(\min Z(n) = c\). Then \(\mathcal{S}(n) = B\) if and only if \(c\) is even.
For each \(j\ge 2\), write \(p(j) = F_{2k} + \sum_{m=2}^\infty a_m F_{2k+m} _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\) and define the function \(p^*: \mathbb{N}_{\ge 2}\rightarrow \mathbb{N}\) as \(p^*(j) := \sum_{m=2}^\infty a_m F_m\).
Proposition 9. For \(j\ge 2\), we have \(p^*(j) = j-1\).
Proof. Note that \(p^*\) is surjective because sums of nonadjacent Fibonacci numbers in \((F_n)_{n\ge 2}\) give all natural numbers. We prove that \(p^*\) is strictly increasing. Let \(j < j'\) with \[p(j)\;=\;F_{2k} + \sum_{m=2}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}} and p(j')\;=\;F_{2k} + \sum_{m=2}^{\infty} a'_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\] Let \(r\) be the largest index such that \(a'_r\neq a_r\). The lexicographical order of Zeckendorf decompositions implies that \(a'_r = 1\) and \(a_r = 0\), and thus, \[p^*(j)\;=\;\sum_{m=2}^\infty a_m F_m \;<\;\sum_{m=2}^\infty a'_m F_{m}\;=\;p^*(j').\] It follows that \(p^*(j) = j-1\). ◻
Proof of Theorem 2. The second statement follows from Corollary 6. We prove the first statement. By Corollary 6, \(F_{2k}\in CG(p(j))\) if and only if \[p(j)\;=\;F_{2k} + F_{2k+2r} + \sum_{m=2r+2}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}},\] which gives \[p^*(j)\;=\;F_{2r} + \sum_{m=2r+2}^\infty a_m F_m.\] By Proposition 9, \[j - 1 \;=\;F_{2r} + \sum_{m=2r+2}^\infty a_m F_m.\] By Lemma 8, \[\mathcal{S}(j-1) \;=\;B.\] ◻
To prove Theorem 3, we need the analog of Proposition 9 for \(q(j)\in B_{2k}\), which is obtained with the help of the following result.
Corollary 10. For each \(j\ge 2\), there exists \(r\ge 1\) such that \[q(j)\;=\;\begin{cases}F_{2k} + F_{2k+2r} + \sum_{m=2r+2}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}},\\ F_{2k-2} + F_{2k+2r-1} + \sum_{m=2r+1}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\end{cases}\]
Proof. By Lemma 7, we know that either \[q(j) \;=\;F_{2k} + \sum_{m=2}^{\infty} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\quad or \quad q(j) \;=\;F_{2k-2} + \sum_{m=1}^{\infty} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\]
Case 1: \(q(j) = F_{2k} + \sum_{m=2}^{\infty} a_m F_{2k+m} _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\). Since \(j\ge 2\), we have \(q(j) > F_{2k}\), so \(\sum_{m=2}^{\infty} a_m F_{2k+m} > 0\). Let \(m^* = \min \{m\ge 2: a_m\neq 0\}\). By Corollary 6, \(m^*\) is even, namely \(m^* = 2r\) for some \(r\ge 1\). In this case, \[q(j)\;=\;F_{2k} + F_{2k+2r} + \sum_{m=2r+2}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\]
Case 2: \(q(j) = F_{2k-2} + \sum_{m=1}^{\infty} a_m F_{2k+m} _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\). Let \(m^* = \min \{m\ge 1:a_m\neq 0\}\). Suppose, for a contradiction, that \(m^* = 2r\) for some \(r\ge 1\). Then \[q(j) \;=\;F_{2k-2} + F_{2k+2r} + \sum_{m=2r+2}^{\infty} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\]
Case 2.1: If \(k\ge 2\), then according to ?? , we have \(\min CG(q(j)) = F_{2k-2}\), which contradicts that \(q(j)\in B_{2k}\).
Case 2.2: If \(k = 1\), then \(\min Z(q(j)) = F_{2k+2r}\). By Corollary 6, \(\min CG(q(j))\) is either \(F_{2k+2r}\) or \(F_{2k+2r+2}\), contradicting \(q(j)\in B_{2k}\).
Therefore, \(m^* = 2r-1\) for some \(r\ge 1\), and we have \[q(j)\;=\;F_{2k-2} + F_{2k+2r-1} + \sum_{m=2r+1}^{\infty} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\] ◻
It follows from Corollary 10 that each \(q(j)\in B_{2k}\) can be written as \[\label{re22}q(j)\;=\; c_1 F_{2k-2} + c_2F_{2k} + \sum_{m=1}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}},\tag{1}\] where \(c_1, c_2\in \{0,1\}\) and \(c_1 + c_2 = 1\). Define the function \(q^*: \mathbb{N}_{\ge 2}\rightarrow \mathbb{N}\) as \[q^*(j) \;:=\;\sum_{m=1}^N a_m F_{m+1}.\]
We have the analog of Proposition 9.
Proposition 11. For \(j\ge 2\), \(q^*(j) = j-1\).
Proof. First, we prove that \(q^*\) is surjective. Let \(n\in \mathbb{N}\) with \(n = \sum_{m=1}^\infty a_m F_{m+1} _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\). Let \(m^* = \min \{m\ge 1: a_m\neq 0\}\).
Case 1: \(m^*\) is odd. By ?? , \[F_{2k-2} + F_{2k+m^*} + \sum_{m=m^*+2}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}} \;\in\;B_{2k}.\]
Case 2: \(m^*\) is even. By ?? , \[F_{2k} + F_{2k+m^*} + \sum_{m = m^*+2}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\;\in\;B_{2k}.\]
We see from both cases that exists \(j\ge 2\) with \[q^*(j) \;=\;F_{m^*+1} + \sum_{m=m^*+2}^\infty a_m F_{m+1}\;=\;n.\]
Second, we prove that \(q^*\) is strictly increasing. Let \(2\le j < j'\). According to 1 , we write \[q(j)\;=\;c_1F_{2k-2} + c_2F_{2k} + \sum_{m=1}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\] and \[q(j')\;=\;c'_1F_{2k-2} + c'_2F_{2k} + \sum_{m=1}^\infty a'_m F_{2k+m} _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\]
If \(\sum_{m=1}^\infty a_m F_{2k+m} = \sum_{m=1}^\infty a'_m F_{2k+m}\), then \(q(j) < q(j')\) implies that \((c_1, c_2) = (1,0)\) and \((c'_1, c'_2) = (0,1)\). By Corollary 10, \(\min \{m\ge 1: a_m = 1\}\) is odd, while \(\min \{m\ge 1: a'_m = 1\}\) is even. This contradicts that \(\sum_{m=1}^\infty a_m F_{2k+m} = \sum_{m=1}^\infty a'_m F_{2k+m}\).
If \(\sum_{m=1}^\infty a_m F_{2k+m} \neq \sum_{m=1}^\infty a'_m F_{2k+m}\), then \(q(j) < q(j')\) implies that if \(M\) is the largest integer such that \(a_M\neq a'_M\), then \(a'_M = 1\) and \(a_M = 0\). It follows that \(q^*(j') > q^*(j)\). ◻
Proof of Theorem 3. The second statement follows from Corollary 10. We prove the first statement. By Corollary 10, \(F_{2k}\in Z(q(j))\) if and only if \[q(j)\;=\;F_{2k} + F_{2k+2r} + \sum_{m=2r+2}^\infty a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}},\] which, by Proposition 11, gives \[j-1 \;=\;q^*(j)\;=\;F_{2r+1} + \sum_{m=2r+2}^\infty a_mF_{m+1}.\] By Lemma 8, \(\mathcal{S}(j-1) = A\). ◻
Remark 12. As we see from the proof of Theorems 2 and 3, the index \(m+1\) in the definition of \(q^*\) (instead of \(m\) as in the definition of \(p^*\)) explains why integers in \(B_{2k}\) correspond to \(A\)’s in \(\mathcal{S}\), while integers in \(A_{2k}\) correspond to \(B\)’s in \(\mathcal{S}\).
Let \(C_{2k} = A_{2k} \cap B_{2k}\). Define \(r(j)\) to be the \(j\)th smallest number in \(C_{2k}\). Let \(\beta(j)\) denote the position of the \(j\)th appearance of the letter \(B\) in \(\mathcal{S}\). We record several useful properties of \(\mathcal{S}\) to be used in due course.
Lemma 13. Let \(n\ge 1\).
If \(\mathcal{S}(n) = A\), then \(\mathcal{S}(n+1) = B\).
The number of \(B\)’s in the first \(n\) letters of \(\mathcal{S}\) is \(\left\lfloor \frac{n+1}{\phi}\right\rfloor\) ([26]).
The \(n\)th \(B\) of \(\mathcal{S}\) occurs at position \(\lfloor n\phi\rfloor\), i.e., \(\beta(n) = \lfloor n\phi\rfloor\) ([26]).
Proof. Item [ps8] is easily proved by induction, while interested readers may refer to [26] for the proof of items [ps2] and [ps3]. ◻
Next, we have the correspondence between terms in \(A_{2k}\) and letters of \(\mathcal{S}\) and establish its analog for \(C_{2k}\).
Lemma 14. [25]For \(j\ge 1\), \[p(j+1)-p(j)\;=\;\begin{cases}F_{2k+1},if A is the jth character of \mathcal{S};\\ F_{2k+2},if B is the jth character of \mathcal{S}.\end{cases}\]
Lemma 15. For \(j\ge 2\), \[r(j+1) - r(j)\;=\;\begin{cases}F_{2k+2}, if B is the (\beta(j)-1)th letter of \mathcal{S};\\ F_{2k+3},if A is the (\beta(j)-1)th letter of \mathcal{S}.\end{cases}\]
Proof. By Theorem 2, we have \[r(j+1)\;=\;p(\beta(j)+1) for all j\ge 1.\] Hence, \[r(j+1) - r(j)\;= \;p(\beta(j)+1) - p(\beta(j-1)+1) for all j\ge 2.\]
Case 1: If \(\mathcal{S}(\beta(j)-1) = B\), then \(\beta(j-1) = \beta(j)-1\). By Lemma 14, \[r(j+1) - r(j)\;=\;p(\beta(j)+1)-p(\beta(j))\;=\;F_{2k+2}.\]
Case 2: If \(\mathcal{S}(\beta(j)-1) = A\), then Lemma 13, item [ps8] gives \(\beta(j-1) = \beta(j)-2\). By Lemma 14, we have \[\begin{align} r(j+1) - r(j)&\;=\;p(\beta(j)+1)-p(\beta(j)-1)\\ &\;=\;p(\beta(j)+1) - p(\beta(j)) + p(\beta(j)) - p(\beta(j)-1)\\ &\;=\;F_{2k+2} + F_{2k+1}\;=\;F_{2k+3}. \end{align}\] ◻
Proof of Theorem 4. For \(n\ge 1\), let \(a(n)\) denote the number of \(A\)’s in the first \(n\) letters of \(\mathcal{S}\). According to Lemma 15, for \(j\ge 2\), the difference \(r(j+1)-r(j)\) depends on whether the \(j\)th appearance of \(B\) is after an \(A\) or a \(B\) in \(\mathcal{S}\): in the case of \(AB\), \(r(j+1) - r(j) = F_{2k+3}\), while in the case of \(BB\), \(r(j+1)-r(j) = F_{2k+2}\). Therefore, the number of times that \(r(j+1) - r(j) = F_{2k+3}\) is equal to the number of \(A\)’s in the first \(\beta(n)\) letters of \(\mathcal{S}\). By Lemma 13, item [ps3], we have for \(n\ge 1\), \[\begin{align} r(n+1)&\;=\;a(\beta(n))F_{2k+3} + (n-a(\beta(n))-1)F_{2k+2} + r(2)\\ &\;=\;a(\lfloor n\cdot \phi\rfloor)F_{2k+3} + (n-a(\lfloor n\cdot \phi\rfloor)-1)F_{2k+2} + r(2)\\ &\;=\;a(\lfloor n\cdot \phi\rfloor)F_{2k+1} + (n-1)F_{2k+2} + F_{2k} + F_{2k+2}\\ &\;=\;F_{2k} + a(\lfloor n\cdot \phi\rfloor)F_{2k+1} + nF_{2k+2}. \end{align}\] Hence, \[C_{2k}\;=\;\{F_{2k}+a\left(\lfloor(n-1)\cdot \phi\rfloor\right)F_{2k+1}+(n-1)F_{2k+2}\;:\;n\in \mathbb{N}\}.\] It follows from Lemma 13, item [ps2] that \[\begin{align} a\left(\lfloor(n-1)\cdot \phi\rfloor\right)&\;=\;\lfloor(n-1)\cdot \phi\rfloor - \left\lfloor \frac{\lfloor(n-1)\cdot \phi\rfloor+1}{\phi}\right\rfloor &\;=\;\lfloor(n-1)\cdot \phi\rfloor - (n-1), \end{align}\] because \[n-1\;=\;\bigg\lfloor\dfrac{(n-1)\phi}{\phi}\bigg\rfloor\;\le\;\bigg\lfloor\dfrac{\lfloor(n-1)\phi\rfloor+1}{\phi}\bigg\rfloor\;\le\;\bigg\lfloor\dfrac{(n-1)\phi+1}{\phi}\bigg\rfloor\;=\;n-1.\] As a result, \[C_{2k}\;=\;\{nF_{2k}+\lfloor(n-1)\phi\rfloor F_{2k+1}\;:\;n\in \mathbb{N}\}.\]
Using \(C_{2k}\), we now find the set \(I_{2k}\) consisting of all positive integers \(n\) with \(F_{2k} \in Z(n)\cap CG(n)\). Pick \(n\in \mathbb{N}\) whose Zeckendorf decomposition is \[n\;=\;\underbrace{\sum_{i=2}^{2k-2}c_iF_{i}}_{=: L}+\underbrace{\sum_{i=2k}^\infty c_iF_{i}}_{=: R}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\] By Corollary 6, \(\max CG(L) \le F_{2k-2}\) and \(\min CG(R) \ge F_{2k}\). Let \[L\;=\;\sum_{i=1}^{k-1} d_i F_{2i}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\quadand \quad R\;=\;\sum_{i=k}^{\infty} d_i F_{2i}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}.\]
We claim that \[n \;=\; \underbrace{\sum_{i=1}^{k-1} d_i F_{2i}}_{L} + \underbrace{\sum_{i=k}^\infty d_i F_{2i}}_R\] is the Chung-Graham decomposition of \(n\). Suppose not; then there exist \(j_1\le k-1\) and \(j_2\ge k\) such that \[d_{j_1}\;= \;d_{j_2}\;=\;2\quadand \quad d_{j_1+1} \;=\;d_{j_1 + 2} \;=\;\cdots \;=\;d_{j_2 - 1} \;=\;1.\] However, this implies \[L\;\ge\;2F_{2j_1} + \sum_{i = j_1 + 1}^{k-1} F_{2i}\;=\;F_{2k-1} + F_{2j_1} - F_{2j_1 -1}\;\ge\;F_{2k-1},\] which contradicts \(L = \sum_{i=2}^{2k-2} c_i F_{i} _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\).
Therefore, \(F_{2k}\in Z(n)\cap CG(n)\) if and only if \(F_{2k}\in Z(R)\cap CG(R)\), which is the same as \(R\in C_{2k}\). In other words, \(n\in I_{2k}\) if and only if \(R\in C_{2k}\). This gives \[I_{2k} \;=\;\{nF_{2k}+\lfloor(n-1)\phi\rfloor F_{2k+1} + j\;:\;n\in \mathbb{N},\, 0\leq j\leq F_{2k-1}-1\},\] as claimed. ◻
Proof of Lemma 5. We proceed by induction. Let \(u:=F_{2k} + \sum_{m=1}^N a_mF_{2k+2m+1}\). For \(N = 1\), we have \(u = F_{2k} + F_{2k+3}\;=\;2F_{2k+2}\). Suppose that ?? is true for all \(N\le j\) for some \(j\ge 1\). We show that ?? is true for \(N = j+1\).
Case 1: \(a_m = 0\) for each \(m\in [1,j]\). We have \[u \;=\;F_{2k}+ F_{2k+2j+3} \;=\;2F_{2k+2} + \sum_{m=2}^{j+1} F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}.\]
Case 2: \(a_m \neq 0\) for some \(m\in [1,j]\). Let \(j^* = \max\{1\le m\le j: a_m = 1\}\). By the inductive hypothesis, we have \[\begin{align} \label{e2} u\;=\;F_{2k} + \sum_{m=1}^{j+1}a_m F_{2k+2m+1}&\;=\;F_{2k} + \sum_{m=1}^{j^*} a_m F_{2k+2m+1} + F_{2k+2j+3}\nonumber\\ &\;=\;bF_{2k+2} + \sum_{m=2}^{j^*} b_mF_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}} + F_{2k+2j+3}. \end{align}\tag{2}\]
Case 2.1: \(j^* = 1\). Then \[\begin{align} u \;=\;F_{2k} + F_{2k+3} + F_{2k+2j+3}&\;=\;F_{2k+2} + F_{2k+2} + F_{2k+2j+3}\\ &\;=\;F_{2k+2} + 2F_{2k+4} + \sum_{m=3}^{j+1}F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}. \end{align}\]
Case 2.2: \(j^*\ge 2\) and \(b_{j^*} = 1\). From 2 , we write \(u\) as \[\begin{align} &bF_{2k+2} + \sum_{m=2}^{j^*-1} b_mF_{2k+2m} + F_{2k+2j^*} + F_{2k+2j+3}\\ \;=\;&bF_{2k+2} + \sum_{m=2}^{j^*-1} b_m F_{2k+2m} + 2F_{2k+2j^*+2} + \sum_{m = j^*+2}^{j+1} F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}. \end{align}\]
Case 2.3: \(j^*\ge 2\) and \(b_{j^*} = 2\). From 2 , we write \(u\) as \[\begin{align} &bF_{2k+2} + \sum_{m=2}^{j^*-1} b_mF_{2k+2m} + 2F_{2k+2j^*} + F_{2k+2j+3}\\ \;=\;&bF_{2k+2} + \sum_{m=2}^{j^*-1} b_mF_{2k+2m} + F_{2k+2j^*} + 2F_{2k+2j^*+2} +\sum_{m=j^*+2}^{j+1} F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}. \end{align}\]
We have verified ?? for all cases. ◻
Proof of Corollary 6. First, we prove ?? . If \(2r\le N\le 2r+2\), then \[F_{2k} + F_{2k+2r+1}\;=\;2F_{2k+2} + \sum_{m=2}^{r} F_{2k+2m},\] and ?? is true.
Suppose that \(N\ge 2r+3\). Let \(m_1 < m_2 < \cdots < m_s\) be all even integers in \([2r+3, N]\) with \(a_{m_i} = 1\) for each \(i\le s\). Let \(b_{i,j}\) denote the coefficients of the corresponding Chung-Graham decompositions. By Lemma 5, we have \[\begin{align} &F_{2k} + F_{2k+2r+1} + \sum_{m=2r+3}^N a_m F_{2k+m}\\ \;=\;&F_{2k} + F_{2k+2r+1} + \sum_{m=2r+3}^{m_1-3} a_mF_{2k+m} + \sum_{j=1}^{s-1} \left(F_{2k+m_j} + \sum_{m=m_j+3}^{m_{j+1}-3} a_mF_{2k+m}\right) \\ &\;+ F_{2k+m_s} + \sum_{m=m_s+3}^{N} a_m F_{2k+m}\\ \;=\;& b_0F_{2k+2} + \sum_{m=2}^{m_1/2-2} b_{0, m} F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}} + \sum_{j=1}^{s-1} \sum_{m = m_j/2}^{m_{j+1}/2-2} b_{j,m} F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\\ &+ \sum_{m = m_s/2}^{\lfloor N/2\rfloor} b_{s,m}F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\\ \;=\;& bF_{2k+2} + \sum_{m=4}^{2\lfloor N/2\rfloor} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}. \end{align}\]
Next, ?? is the same as \[\label{e5}F_{2k+2r} + \sum_{m=2r+2}^N a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\;=\; \sum_{m=2}^{2\lfloor N/2\rfloor} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}.\tag{3}\]
If \(2r\le N\le 2r+1\), then \(2\lfloor N/2\rfloor = 2r\), and \[F_{2k+2r} + \sum_{m=2r+2}^N a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\;=\;F_{2k+2r},\] so 3 is true. Suppose that \(N\ge 2r + 2\). Let \(m_1 < m_2 < \cdots < m_s\) be all even integers in \([2r+2, N]\) with \(a_{m_i} = 1\) for each \(i\le s\). Let \(b_{i,j}\) denote the coefficients of the corresponding Chung-Graham decompositions. By Lemma 5, we have \[\begin{align} &F_{2k+2r} + \sum_{m=2r+2}^N a_m F_{2k+m}\\ \;=\;&F_{2k+2r} + \sum_{m=2r+2}^{m_1-3} a_mF_{2k+m} + \sum_{j=1}^{s-1}\left(F_{2k+m_j} + \sum_{m=m_j+3}^{m_{j+1}-3} a_mF_{2k+m}\right) + \\ &F_{2k+m_s} + \sum_{m= m_s + 3}^{N} a_m F_{2k+m}\\ \;=\;&\sum_{m=r}^{m_1/2-2}b_{0,m} F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}} + \sum_{j=1}^{s-1}\sum_{m = m_j/2}^{m_{j+1}/2-2} b_{j,m}F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}} + \sum_{m = m_s/2}^{\lfloor N/2\rfloor} b_{s,m}F_{2k+2m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\\ \;=\;&\sum_{m=2}^{2\lfloor N/2\rfloor} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}. \end{align}\] ◻
Proof of Lemma 7, Equation ?? . We proceed by induction. It is readily verified that ?? holds for \(M\in \{0, 2, 4\}\). Suppose that ?? holds for \(M = j\) for some even \(j\ge 4\). We show that ?? holds for \(M = j+2\). We have \[\begin{align} 2F_{2k} + \sum_{m=2}^{j+2} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}} &\;=\;2F_{2k} + \sum_{m=2}^j b_m F_{2k+m} + b_{j+2} F_{2k+j+2}\\ & \;=\;F_{2k-2} + \sum_{m=1}^{j+1} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}} + b_{j+2} F_{2k+j+2}. \end{align}\]
Case 1: \(b_{j+2} = 1\) and \(a_{j+1} = 0\). Then \[2F_{2k} + \sum_{m=2}^{j+2} b_m F_{2k+m}\;=\;F_{2k-2} + \sum_{m=1}^{j} a_m F_{2k+m} + F_{2k+j+2}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\]
Case 2: \(b_{j+2} = 1\) and \(a_{j+1} = 1\). Then \[2F_{2k} + \sum_{m=2}^{j+2} b_m F_{2k+m}\;=\;F_{2k-2} + \sum_{m=1}^{j} a_m F_{2k+m} + F_{2k+j+3}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}.\]
Case 3: \(b_{j+2} = 2\). Let \(j^* = \max\{m: 2\le m\le j, 2|m, b_{m} = 0\}\). Then \[\begin{align} &2F_{2k} + \sum_{m=2}^{j+2} b_m F_{2k+m}\\ \;=\;&2F_{2k} + \sum_{m=2}^{j^*-2} b_m F_{2k+m} + \sum_{\substack{j^*+2\le m\le j\\ 2|m}} F_{2k + m} + 2F_{2k+j+2}\\ \;=\;&F_{2k-2} + \sum_{m=1}^{j^*-1} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}} + 2F_{2k+j^*+2} + \sum_{\substack{j^*+5\le m\le j+3\\ 2\nmid m}} F_{2k+m}. \end{align}\]
Case 3.1: \(a_{j^*-1} = 0\). Then \[\begin{align} &2F_{2k} + \sum_{m=2}^{j+2} b_m F_{2k+m}\\ \;=\;&F_{2k-2} + \sum_{m=1}^{j^*-2} a_m F_{2k+m} + F_{2k+j^*} + F_{2k+j^*+3} + \sum_{\substack{j^*+5\le m\le j+3\\ 2\nmid m}} F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}. \end{align}\]
Case 3.2: \(a_{j^*-1} = 1\). Then \[\begin{align} &2F_{2k} + \sum_{m=2}^{j+2} b_m F_{2k+m}\\ \;=\;&F_{2k-2} + \sum_{m=1}^{j^*-3} a_m F_{2k+m} + F_{2k+j^*+1} + F_{2k+j^*+3} + \sum_{\substack{j^*+5\le m\le j+3\\ 2\nmid m}} F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}. \end{align}\]
◻
Proof of Lemma 7, Equation ?? . We prove by induction. It is readily verified that ?? is true when \(M \in \{0, 2, 4\}\). Assume that ?? holds for \(M = j\) for some even \(j\ge 4\). We show that ?? holds for \(M = j+2\).
Case 1: \(b_{j+2} = 1\). By the induction hypothesis, we have \[\begin{align} F_{2k} + \sum_{m=1}^{j+2} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}&\;=\;F_{2k} + \sum_{m=1}^{j} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}} + F_{2k+j+2}\\ &\;=\;\begin{cases}F_{2k-2}\\ F_{2k}\end{cases} + \sum_{m=1}^{j+1} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}} + F_{2k+j+2}\\ &\;=\;\begin{cases}F_{2k-2}\\ F_{2k}\end{cases} + \sum_{m=1}^{j} a_m F_{2k+m} + \begin{cases}F_{2k+j+2}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\\ F_{2k+j+3}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}\end{cases}\\ &\;=\;\begin{cases}F_{2k-2}\\ F_{2k}\end{cases} + \sum_{m=1}^{j+3} a_m F_{2k+m} _{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}. \end{align}\]
Case 2: \(b_{j+2} = 2\). Let \(A = \{2\le m\le j: 2|m, b_m = 0\}\).
Case 2.1: \(A = \emptyset\). Then \[\begin{align} &F_{2k} + \sum_{m=1}^{j+2} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\\ \;=\;&F_{2k} + F_{2k+2} + F_{2k+4} + \cdots + F_{2k+j} + 2F_{2k+j+2}\\ \;=\;&F_{2k-2} + F_{2k+1} + F_{2k+3} + \cdots + F_{2k+j+1} + F_{2k+j+3}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}. \end{align}\]
Case 2.2: \(A\neq \emptyset\). Let \(j^* = \max A\). Then by the inductive hypothesis, \[\begin{align} \label{re21} &F_{2k} + \sum_{m=1}^{j+2} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\nonumber\\ \;=\;&F_{2k} + \sum_{m=2}^{j^*-2} b_m F_{2k+m} + \sum_{\substack{j^*+2\le m\le j\\ 2|m}} F_{2k+m} + 2F_{2k+j+2}\nonumber\\ \;=\;&\begin{cases}F_{2k-2}\\ F_{2k}\end{cases} + \sum_{m=1}^{j^*-1} a_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}} + F_{2k+j^*} + F_{2k+j^*+3} + \sum_{\substack{j^*+5\le m\le j+3\\ 2\nmid m}} F_{2k+m}. \end{align}\tag{4}\] If \(a_{j^*-1} = 0\), then 4 is the Zeckendorf decomposition of \(F_{2k} + \sum_{m=1}^{j+2} b_m F_{2k+m}\). If \(a_{j^*-1} = 1\), then \[\begin{align} &F_{2k} + \sum_{m=1}^{j+2} b_m F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha CG}}\\ \;=\;& \begin{cases}F_{2k-2}\\ F_{2k}\end{cases} + \sum_{m=1}^{j^*-3} a_m F_{2k+m} + F_{2k+j^*+1} + F_{2k+j^*+3} + \sum_{\substack{j^*+5\le m\le j+3\\ 2\nmid m}} F_{2k+m}_{\raisebox{-0.7ex}{\scriptstyle \alpha Z}}. \end{align}\]
◻
The authors thank the anonymous referees for their careful reading and helpful suggestions, which have improved the exposition of the paper.
This work was partially supported by the College of Arts & Sciences at Texas A&M University. The first, third, fourth, and fifth named authors are undergraduate students at Texas A&M University at the time of the paper, working under the guidance of the second and sixth named authors.↩︎