**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?


*Additional infos:*


* 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$?](https://math.stackexchange.com/questions/167653/for-a-trigonometric-polynomial-p-can-lim-limits-n-to-infty-pn2-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.



For a linear recurrence sequence $(u_n)_{n\geq 0}$, can $\{i \mid u_i > 0\}$ be the set of Fibonacci numbers?
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$.


