Fibonacci-like sequences in $\mathbb{F}_q$ where each element only depends on the previous one Given a prime power $q$, consider all sequences $(a_n)_{n\in\mathbb{Z}}$ in $\mathbb{F}_q$ for which $a_{n+1}=a_n+a_{n-1}$ for all $n\in\mathbb{Z}$. Call such a sequence simple if there exists a function $f:\mathbb{F}_q\to\mathbb{F}_q$ such that $a_{n+1}=f(a_n)$ for all $n\in\mathbb{Z}$.
There are some trivial simple sequences. The null sequence is simple, as is $(cr^n)_{n\in\mathbb{Z}}$ for $c\in\mathbb{F}_q^*$ and $r$ a root of $X^2-X-1$. My questions are about nontrivial simple sequences.
I've asked a more specific version of this question on Math.Stackexchange. There, computations by the user @Servaes show that nontrivial simple sequences exist in $\mathbb{F}_p$ for $p\in\{199,211,233,281,421,461,521,557,859,911\}$
Questions:

*

*Are there 'easy' conditions on primes $p$ such that no nontrivial simple sequences exist in $\mathbb{F}_p$ when $p$ satisfies these conditions? (and there are a large number of primes satisfying these conditions)

*Are there infinitely many primes $p$ such that nontrivial simple sequences exist in $\mathbb{F}_p$?

*Given a prime $p$, does there always exist a positive integer $n$ such that nontrivial simple sequences exist in $\mathbb{F}_{p^n}$?

*In case the answer to the previous question is affirmative, let $n(p)$ be the smallest such positive integer. Is $n(p)$ bounded? If not, do there exist integers $m$ such that $n(p)=m$ for infinitely many primes?

 A: $\def\ord{\mathop{\mathrm{ord}}}$Let $q=p^s$ for a prime $p$.
Let $\phi$ and $\psi$ be the roots of $X^2-X-1$; they may lie either in $\mathbb F_p$ (when $\left(\frac p5\right)=1$, call this case simple) or in $\mathbb F_{p^2}$. The case $\phi=\psi$, i.e. $p=5$, is covered by @YCor in the comments (1 2), so let us assume $\psi\neq \phi$. Notice that $\phi\psi=-1$.
The general form of a linear recurrence is then $a_n=a\phi^n+b\psi^n$; where $a,b\in\mathbb F_q$ if $\sqrt5\in\mathbb F_q$, and $a$ and $b$ are two conjugate elements in $K=\mathbb F_q[\sqrt5]$, otherwise (here, conjugate means that they are swapped by the nontrivial automorphism of $K$ over $\mathbb F_q$). Surely, this sequence is periodic with period $T=\ord \phi=\ord\psi$ (where $\ord$ means the multiplicative order in $\mathbb F_{p^2}$ which does not depend on $s$); so we need the terms $a_1,a_2,\dotsc,a_T$ to be distinct, while $a$ and $b$ are nonzero.
If two such terms are equal, we have
$$
  a\phi^n+b\psi=a\phi^{n+k}+b\psi^{n+k}
  \iff a\phi^n(\phi^k-1)=b\psi^n(\psi^k-1)
  \iff \frac ba=\phi^{2n}(-1)^n\frac{\phi^k-1}{\psi^k-1}.
$$
For every prime $p$, the right-hand part attains finitely many values ($\leq T^2<p^4$), so, say, for $s=6$ there exist $a$ and $b$ which violate all equalities above and thus fit. This answers the third question.
Moreover, if the order $T$ of $\phi$ is relatively small comparative to $p$ (say, $T\leq \sqrt p$), then the required $a$ and $b$ will be found even in $\mathbb F_p$. But I am not sure whether this is a good condition to answer the second question.
A few more words on the fraction under consideration
$$
  \phi^{2n}\frac{\phi^k-1}{\psi^k-1}.
$$
If, say, $\sqrt5\in\mathbb F_p$, and we want to have no desired sequence, we want this expression to take all values in $\mathbb F_p^*$. If $k$ is even, the expression is $-\phi^{k+2n}$, but for odd $k$ it is more complicated.  If, say, $\phi$ is a generator of $\mathbb F_p^*$, then the whole $\mathbb F_p^*$ will be covered. Again, this is a condition for question 1, but it is too strong.
