5
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ $\varphi + \frac{1}{\varphi} = \sqrt{5}$, that's not good. $\xi := \frac{\varphi}{\sqrt{5}}$ is a good factor (because the convergents of that are $\frac{F_{n+1}}{L_n}$). Except for $2$ and $3$, all Lucas numbers satisfy $\left[\xi a - \frac{1}{2a}, \xi a+ \frac{1}{2a}\right] \cap \mathbb{N} \neq\varnothing$, and every number $a\in \mathbb{N}$ with that property is a Lucas number. We also catch $2$ and $3$ if we take the interval $\left[\xi a - \frac{1}{a}, \xi a+ \frac{1}{a}\right]$, but I have not yet proven that that implies $a$ is a Lucas number. $\endgroup$ – Daniel Fischer Jun 7 '14 at 16:12
  • $\begingroup$ @DanielFischer I tested that on 4 (Lucas) and got a hit, and on 5 (non-Lucas) and got the expected result as well. $\left[\tfrac{a(\varphi^2+1)}{5}-\tfrac{1}{a},\tfrac{a(\varphi^2+1)}{5}+\tfrac{1}{a}\right]$ appears to work too, as this interval contains a Fibonacci number. $\endgroup$ – Brian J. Fink Jun 7 '14 at 16:34
  • $\begingroup$ @Dan all values of $a$ that I have tested so far have had the expected result. For example $7$ passes, $8,9,10$ fail, $11$ passes, $12,13,14,15,16,17$ fail, $18$ passes, $199$ passes, $200$ fails. Can you post your test in an answer? $\endgroup$ – Brian J. Fink Jun 7 '14 at 17:26
  • $\begingroup$ @DanielFischer how's the proof coming? $\endgroup$ – Brian J. Fink Jun 7 '14 at 18:45
  • $\begingroup$ Just done, just done :D $\endgroup$ – Daniel Fischer Jun 7 '14 at 18:48
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great answer! But why did you use parentheses instead of brackets for this interval? $\endgroup$ – Brian J. Fink Jun 7 '14 at 19:11
  • $\begingroup$ No particular reason. Since $\xi$ is irrational, the boundary points of the interval are irrational too, and hence never an integer, so it's equivalent to take an open or closed interval. I don't know why I picked the open interval here, but the closed one in the comment. $\endgroup$ – Daniel Fischer Jun 7 '14 at 19:16
  • $\begingroup$ For the sake of uniformity, could you edit your answer? I don't have the privilege of editing just 2 characters, or I'd do it myself. $\endgroup$ – Brian J. Fink Jun 7 '14 at 19:21
  • $\begingroup$ Sure, done, no problem. $\endgroup$ – Daniel Fischer Jun 7 '14 at 19:23
  • $\begingroup$ It sticks in my mind that $\xi$ is also equal to $\tfrac\varphi{\varphi+\tfrac{1}\varphi}$. $\endgroup$ – Brian J. Fink Jun 8 '14 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.