# For a linear recurrence sequence $(u_n)_{n\geq 0}$, can $\{i \mid u_i > 0\}$ be the set of Fibonacci numbers?

Question: Is there a linear recurrence sequence $(u_n)_{n\geq0}$ (on the rationals, but I would also be interested by reals) for which $\text{Pos}(u) = \{i \mid u_i > 0\}$ is precisely the set of Fibonacci numbers?

• It is well known that the set $\{i \mid u_i = 0\}$ is quite easy to describe (semilinear), but the sets with $>$ instead of $=$ can get quite weird. For instance, there is a $(u_n)_{n\geq 0}$ with $\{{k_1} < {k_2} < \cdots \} = \text{Pos}(u)$ such that $\lim_{i \to \infty} k_{i+1} - k_i = \infty$.
• This question is somewhat linked to the question "For a trigonometric polynomial $P$, can $\lim \limits_{n \to \infty} P(n^2) = 0$ without $P(n^2) = 0$?"
• The use of Fibonacci in the current question is not all that relevant—take the squares or the powers of two if it's easier.
• How do the sequences you mention differ from what you want, if the choice of Fibonacci numbers is not important? – Douglas Zare Nov 1 '15 at 6:42
• These $\text{Pos}$ sets behave as inequality of trigonometric polynomials; the example I mention for instance is such that $\text{Pos}(u) = \{n \mid n^2 \times \sin(2\pi\sqrt{2}n)<1\}$. I want to compare these sets with sets that we naturally come up with, other linear sequences, squares, powers, … Frankly, any nontrivial and natural set that is not expressible with $\text{Pos}(u)$ can be of interest. – Michaël Nov 1 '15 at 9:35
• Yes, I figured that your example would look like that, and a slight variation of that should give the Fibonacci numbers. It sounds like you are more interested in what can't arise rather than constructions. – Douglas Zare Nov 1 '15 at 15:06
• @Joël: Sure. The first part is known as the Skolem-Mahler-Lech theorem. The second part can be found in, say, the book of Salomaa and Soittola "Automata-theoretic aspects of formal power series", p.93. – Michaël Nov 1 '15 at 22:33
• @StevenStadnicki: Languages of the form $\{a^n \mid u_n > 0\}$, with $a$ a letter, are known as unary Probabilistic languages, and they are not even closed under basic closure properties (see Paz). – Michaël Nov 13 '15 at 4:57

Solutions to (complex) linear recurrences are of the form

$$\sum_i c_i n^{e_i} \alpha_i^n.$$

To build such a function that is positive only on Fibonacci numbers, take $n^2(\alpha^n + \bar{\alpha}^n-2)+c$ where $\alpha = \exp(2\pi i / \phi), \phi = \frac{\sqrt{5} + 1}{2}$. For this to be positive, $\Re(\alpha^n)$ has to be close to $1$, which means $\alpha^n$ is close to $1$, which means $n/\phi$ is close to an integer.

Numerically, $c=8$ works. The values of $n^2(\alpha^n+\bar{\alpha}^n-2)+8$ are positive and drop toward $0.1043$ at Fibonacci numbers and they are quite negative at non-Fibonacci indices, with the nearest misses at indices of the form $\operatorname{Fibonacci}(n) + \operatorname{Fibonacci}(n-3)$, where it seems to takes the value $-118$ followed by indices of the form $\operatorname{Fibonacci}(n) + \operatorname{Fibonacci}(n-2)$, $-189$. A proof using standard results on simple continued fractions shouldn't be hard, and I'll try to fill in the details later.

I'll prove that $c=9$ works.

If $n = F_k$, the $k$th Fibonacci number, then we have an explicit formula $n = \frac{1}{\sqrt{5}}\left( \phi^k - (-\phi)^{-k}\right)$ and the distance between $F_k/\phi$ and the nearest integer is $1/\phi^k$ as long as $k \ge 2$. The formula is incorrect for $k=1$, but $F_1=1=F_2$, so we can simply assume $k\ne 1$.

$$\begin{eqnarray}n^2 (\alpha^n + \bar\alpha^n - 2) &=& 2n^2(\cos 2\pi n/\phi - 1) \newline &=& 2n^2(\cos 2\pi \phi^{-k} -1) \newline & \ge & 2n^2 \left(-\frac{1}{2}(2\pi \phi^{-k})^2\right) \newline &=& \left(1 - (-1)^k\phi^{-2k}\right)^2 \left(-\frac{4 \pi^2}{5}\right) \end{eqnarray}$$

The estimate was that $\cos x \ge 1-\frac{x^2}{2}$.

When $k$ is even, we get that $-4\pi^2/5 = -7.90$ is a lower bound, so if we add $9$, $n^2(\alpha^n+\bar\alpha^n-2)+9 \gt 0$. For $k$ odd, $k \ge 3$ and then

$$-\frac{4 \pi^2}{5}(1-(-1)^k\phi^{-2k})^2 \ge -\frac{4 \pi^2}{5} (1+\phi^{-6})^2 = - 8.8.$$

So, if $n$ is a Fibonacci number, then $n^2 (\alpha^n + \bar\alpha^n - 2) + 9 \gt 0$.

Suppose $n$ is not a Fibonacci number. Let $m$ be the closest integer to $n/\phi$. Then $\alpha^n + \bar\alpha^n = 2\cos 2\pi n/\phi = 2 \cos(2 \pi m - 2 \pi n/\phi) = 2 \cos 2\pi n(m/n - \phi)$.

If $m/n$ is reduced, then because the denominator is not a Fibonacci number, $m/n$ is not a convergent to the simple continued fraction for $1/\phi$. This implies that

$$\left|\frac{m}{n} - \frac{1}{\phi}\right| \ge \frac{1}{2 n^2}$$

by Theorem 184 in Hardy and Wright, An Introduction to the Theory of Numbers, 4th edition. (In fact, this inequality is far from sharp for approximations to $\phi$ or $1/\phi$, so much better estimates could be used.) Multiply both sides by $2\pi n$:

$$\left|2 \pi m - 2\pi n/\phi \right| \ge \frac{\pi}{n}.$$

If $\left|2 \pi m - 2\pi n/\phi \right| \gt 1$, then $-2n^2 (\cos \left|2 \pi m - 2\pi n/\phi \right|-1)$ can only be small if $n$ is small, and those cases are easy to check numerically. Otherwise, we can use that when $|\theta| < 1, \cos \theta \le 1-\frac{11}{24}\theta^2$ from the first three terms of the power series, which implies that

$$\begin{eqnarray}2n^2 (\cos \left| 2 \pi m - 2\pi n/\phi \right| -1) &\le& 2n^2\left(-\frac{11}{24} \left(\frac{\pi}{n} \right)^2\right) \newline &\le & -\frac{11}{12}\pi^2 \newline &\le& -9.04.\end{eqnarray}$$

If $m/n$ is not reduced, then $m$ and $n$ share a common factor, and then even if $m/n$ is a convergent to the simple continued fraction for $1/\phi$, $\cos 2\pi n (m/n - 1/\phi)$ is too far from $1$.

Thus, if $n$ is not a Fibonacci number, then $n^2(\alpha^n + \bar\alpha^n - 2)+9 \le 0$.

• Wow, mind=blown. I'm not understanding it entirely yet, but nice feat! Would that generalizes to any set of numbers that appear in a linear recurrence sequence? I'd really love to see the "not hard" details :-) – Michaël Nov 1 '15 at 22:36
• If you try it over the rationals this quickly leads to the question whether $\exp(2\pi i/\phi)$ is algebraic, is it? – Fan Zheng Nov 2 '15 at 19:36
• @Fan Zheng: The Gelfond-Schneider theorem says $a^b$ is transcendental for $a$ algebraic other than $0,1$ and $b$ an algebraic irrational. $\exp(2\pi i/\phi) = (-1)^{2/\phi}$, so $\exp (2\pi i/\phi)$ is transcendental. – Douglas Zare Nov 2 '15 at 19:51
• Since you can fix any finite prefix with a rapidly decaying recurrence, it is sufficient that for some $\gamma$ and thresholds $\epsilon_0 \lt \epsilon_1$, for sufficiently large $n$, $n/\gamma$ is within $\epsilon_0/n$ of an integer for $n$ in the sequence, but not within $\epsilon_1/n$ of an integer for $n$ not in the sequence. Whether the numerators of the convergents of the simple continued fraction for $\gamma$ work depends on the coefficients of the simple continued fraction. You want them not to differ by a factor of about $4$ from each other, and it might help if they are larger. – Douglas Zare Nov 14 '15 at 1:03
• I translated the statements into ones about rational approximations, and then used classical results on Diophantine approximation and the Farey sequence. Most of these classical results can be found in Hardy and Wright, An Introduction to the Theory of Numbers. See theorems numbered around 180-184 which say in what sense the convergents to the simple continued fraction are good approximations, how good they are, how they compare to nonconvergents, and that very good approximations must be convergents. – Douglas Zare Jan 6 '16 at 10:52