Sum of Fibonacci sequence evaluated at a Dirichlet character Let $F_n$ be the Fibonacci sequence and $\chi$ a non-principal primitive Dirichlet character. Does there exist $n$ such that $\chi(F_n) \neq 0,1$?
One way to prove this would be to obtain non-trivial bounds for sums of the shape $\sum_{n \leq x} \chi(F_n)$.
It is foreseeable that there could be some "bad" Dirichlet characters where one does not obtain the result, so I'm very happy to ignore finitely many Dirichlet characters of any given order (say).
More generally, I'd like to know a version of this where $F_n$ is replaced by an arbitrary Lucas sequence.
 A: The question is not new. In April 2014 I conjectured that for any prime $p>3$ there is a positive Fibonacci number $F_n<p/2$ such that $\left(\frac{F_n}p\right)=-1$, where $(-)$ is the Legendre symbol. See http://oeis.org/A241568 for related data. Moreover, in Section 2 of a published paper available from http://maths.nju.edu.cn/~zwsun/195g.pdf, I gave some heuristic arguments to support this, and also presented some similar conjectures for Lucas numbers.
A: This is a partial answer.
Let $\chi$ be a Dirichlet character of modulus $k$.
Let $\alpha(k)$ denote the rank of apparition of $k$, that is the smallest index $n$ (larger than zero) such that $k|\mathcal{F}_n$.
If
$$
\alpha(k) \text{ is odd} 
$$
and
$$
\chi(-1)\not=1
$$
then
$$
\chi(\mathcal{F}_{\alpha(k)-1}) \not\in \{0,1\}.
$$
Proof.
We assume $\chi(\mathcal{F}_{\alpha(k)-1})=0$.
The definition of the Fibonacci numbers implies
$$
\begin{array}{c|ccccccc}
n & \ldots & \alpha(k)-3 & \alpha(k)-2 & \alpha(k)-1 & \alpha(k) & \alpha(k) + 1 & \alpha(k)+2 \\
\hline
\mathcal{F}_n \mod k & \ldots & 2 \mathcal{F}_{\alpha(k)-1} & -  \mathcal{F}_{\alpha(k)-1} & \mathcal{F}_{\alpha(k)-1} & 0 & \mathcal{F}_{\alpha(k)-1}& \ldots
\end{array}
$$
that the whole sequence $\chi(\mathcal{F}_n)$ is $0$, which is a contradiction.
To exclude the other case, we assume $\chi(\mathcal{F}_{\alpha(k)-1})=1$.
Since, by extending the above table all the way down to $n=1$,
$$
\mathcal{F}_{\alpha(k)-1}^2 \equiv (-1)^{\alpha(k)} \mod k
$$
we have by assumption $ \mathcal{F}_{\alpha(k)-1}^2 \equiv -1 \mod k$.
If we now apply the character we get $ 1=\chi(\mathcal{F}_{\alpha(k)-1})^2 = \chi(-1)\not=1$, a contradiction.
If the modulus $k$ of the character is prime the above is true without any restriction on $\alpha(k)$.
In that situation either $\mathcal{F}_{\alpha(k)-1}= -1$ or $\mathcal{F}_{\alpha(k)-2}= -1$.
