Skip to main content

Section 48.3 Degree of Accessibility of Even Fibonacci Numbers

Note: This is Theorem 3 in [48.7.2].

We will prove by contradiction, by providing a 3–colouring that has no monochromatic two terms with difference in \(F_E\text{.}\)

Here is some notation for the proof: For \(x\in\mathbb{R}\text{,}\) \(\{x\}\) is the fractional part of \(x\) defined as \(\{x\}=x-\lfloor x\rfloor\text{.}\)

Next, the norm of \(x\) is defined as, \(\| x\|=\min(\{x \},1-\{x\}])\text{,}\) so \(\| x\|\) is the shortest distance from \(x\) to an integer. By Applying Binet's formula we get:

\begin{equation*} f_{n+1}-\varphi f_n= \frac{\varphi^{n+1}-(-\varphi)^{-n-1}}{\sqrt{5}}-\frac{\varphi^{n+1}+(-\varphi)^{-n+1}}{\sqrt{5}}\\ = -\frac{1}{\sqrt{5}}\left(\frac{1}{(-\varphi)^{n+1}}+\frac{1}{(-\varphi)^{n-1}}\right)\\ = \frac{\varphi^2+1}{\sqrt{5}\varphi}\frac{1}{(-\varphi)^n}= \frac{1}{(-\varphi)^n}\text{.}\\ \end{equation*}

Now we will show that \(\lim_{n\to\infty}\|{\varphi\over2}f_{3n}=\frac{1}{2}\text{:}\)

\begin{equation*} 0=\lim_{n\to\infty}\frac{1}{\varphi^{3n}}= \|f_{3n+1}-\varphi f_{3n}|\\ =\lim_{n\to\infty} \|\frac{1}{2}(f_{3n+1}-\varphi f_{3n})\|=\lim_{n\to\infty}\|\frac{1}{2}- {\varphi\over2} f_{3n})\|\text{,}\\ \end{equation*}

which implies \(\lim_{n\to\infty}\|{\varphi\over2}f_{3n}\|= {1\over2}\text{.}\)

Additionally \(\frac{1}{3}\lt 0.382=\|{\varphi\over2}f_3\|\leq\|{\varphi\over2}f_{3n}\|\text{.}\)

We define a \(3\)–colouring \(\Psi:\mathbb{Z}^+\rightarrow\{1,2,3\}\) in the following way: For \(C_1=[0,{1\over3})\text{,}\) \(C_2=[{1\over3},{2\over3})\text{,}\) and \(C_3=[{2\over3},1)\text{,}\) \(\Psi(i)=j\) if and only if \(\left\{\frac{\varphi i}{2}\right\}\in C_j\text{.}\)

Now we show that that \(F_E\) is not 3–accessible by letting \(a\) and \(f\) be integers with \(f\in F_E\text{:}\)

\begin{equation*} \|{1\over2}\varphi(a+f)-{1\over2}\varphi a\|=\|{1\over2}\varphi f\|>{1\over 3}\text{.} \end{equation*}

Thus \(\Psi(a)\not= \Psi(a+f)\) because \(a\) and \(a+f\) are in distinct \(C_i\)'s.

Here is a drawing to explaining why \(\{{\varphi\over2}a\}=A\) and \(\{{\varphi\over2}(a+f)\}=B\) must lie on distinct \(C_i\) intervals.

The black interval around \(\{a\}\) is an inclusive neighbourhood around \(\{a\}\) of length \({1\over3}\text{,}\) and \(\{a+f\}\) cannot be in this neighbourhood.

We can now prove that \(\text{doa }(F)\leq5\) by a \(6\)–colouring that is not accessible.

We define a colouring \(\Phi:\mathbb{Z}^+\rightarrow\{1,2,3,4,5,6\}\) in the following way:

\begin{equation*} \Phi(x)=\left\{ \begin{array}{cl} \Psi(x)\amp \text{if } x \text{ is even}\\ \Psi(x)+3\amp \text{if } x \text{ is odd.}\\ \end{array} \right. \end{equation*}

Now \(\Phi\)–monochromatic terms must be an even distance apart, and by property of \(\Psi\) there are no monochromatic terms that have a difference of \(f\in F_E\text{.}\)