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