What's the Lucas version of the Möbius test for Fibonacci numbers?

213 Views Asked by At

I recently came across the following, attributed to Möbius: $$(a\in\mathbb N)=F_n\iff\left[\varphi a-\tfrac{1}{a},\varphi a+\tfrac{1}{a}\right]\ni(b\in\mathbb N)$$ It is the lesser-known test used to tell if a positive integer $a$ is a Fibonacci number, and it can be applied with considerable ease. It works on the principle that a number is Fibonacci if and only if the interval between $\varphi a-\tfrac{1}{a}$ and $\varphi a+\tfrac{1}{a}$ contains an integer. $\varphi$ is the golden ratio, $\frac{1+\sqrt{5}}{2}$.

My question is:

What is the similar test to see if a number is Lucas or not?

I'm not referring to the other test that employs perfect squares, a coefficient of $5$, or the term $\pm20$; I already know of that test, but it bears no resemblance to this one.

(I'm guessing it would use $\varphi a+\tfrac{a}\varphi$ somehow, but I could be mistaken.)

1

There are 1 best solutions below

5
On BEST ANSWER

The analogous test would be that the interval

$$\left[\xi a - \frac{1}{a},\xi a+\frac{1}{a}\right]$$

contains an integer, where $\xi = \frac{\varphi}{\sqrt{5}} = \frac{\varphi^2+1}{5} = \frac{5+\sqrt{5}}{10}$.

We have $L_n = \varphi^n + \psi^n$, where $\psi = 1-\varphi = -\frac{1}{\varphi} = \frac{1-\sqrt{5}}{2}$, and so

$$\frac{\varphi}{\sqrt{5}}L_n = \frac{\varphi^{n+1} - \psi^{n-1}}{\sqrt{5}} = \frac{\varphi^{n+1}-\psi^{n+1}}{\sqrt{5}} + \frac{\psi^n(\psi - \psi^{-1})}{\sqrt{5}} = F_{n+1} + \frac{\psi^n}{\sqrt{5}}.$$

Since

$$\left\lvert \xi L_n - F_{n+1}\right\rvert = \frac{\lvert\psi\rvert^n}{\sqrt{5}} = \frac{1}{\sqrt{5}\,\varphi^n} < \frac{1}{L_n},$$

all Lucas numbers pass this test.

The converse, that only the Lucas numbers pass the test, is not so obvious. It is equivalent to saying that if

$$\left\lvert \frac{5+\sqrt{5}}{10} - \frac{b}{a}\right\rvert \leqslant \frac{1}{a^2}$$

for positive integers $a,b$, then $\frac{b}{a}$ is a convergent of $\xi$. (Since the continued fraction expansion of $\xi$ is $[0,1,2,\overline{1}]$, the nonzero convergents of $\xi$ are precisely the $\frac{F_{n+1}}{L_n}$ for $n\geqslant 1$; $L_0 = 2$ is a special case.)

Suppose that $L_n < a < L_{n+1}$ for an $n > 2$. We need to show that for all $b$ we have

$$\left\lvert\xi - \frac{b}{a} \right\rvert > \frac{1}{a^2}.$$

Since the convergents are alternatingly smaller and larger than $\xi$, we have

$$\frac{F_{n+1}}{L_n} \lessgtr \xi \lessgtr \frac{F_{n+2}}{L_{n+1}} \lessgtr \frac{F_n}{L_{n-1}},$$

and $\frac{F_{n+2}}{L_{n+1}}$ is the unique fraction with the smallest denominator lying between $\frac{F_{n+1}}{L_n}$ and $\frac{F_n}{L_{n-1}}$. Therefore $\frac{F_{k+1}}{L_k}$ lies between $\xi$ and $\frac{b}{a}$ for either $k = n$ or $k = n-1$ (unless $a = 2L_{n-1}$ and $b = 2F_n$, but then $\left\lvert\xi - \frac{b}{a}\right\rvert > \frac{1}{a^2} = \frac{1}{4 L_{n-1}^2}$ follows from general estimates of the quality of approximations by convergents). Then

$$\begin{align} \left\lvert\xi - \frac{b}{a}\right\rvert &= \left\lvert\xi - \frac{F_{k+1}}{L_k}\right\rvert + \left\lvert\frac{F_{k+1}}{L_k} - \frac{b}{a} \right\rvert\\ &> \left\lvert\frac{F_{k+1}}{L_k} - \frac{b}{a} \right\rvert\\ &= \frac{\lvert aF_{k+1} - bL_k\rvert}{aL_k}\\ &\geqslant \frac{1}{a L_k}\\ &> \frac{1}{a^2}, \end{align}$$

since $a > L_k$. So $a$ doesn't pass the test, and it is established that only Lucas numbers pass.