Numerical evidence suggests the following.
For $c \in \mathbb{N}, c > 2$ define the sequence $a_n$ by $a_0=0,a_1=1, \; a_n=c a_{n-1} - a_{n-2}$
For $ 5 < n < 500, \; 2 < c < 100$ there are no primes in $a_n$ though semiprimes exist.
Is it true that $a_n$ is always composite for $n > 5$
If yes is there explicit partial factorization?
Searching OEIS solved the case $c=6$ with a Pell equation.
Counterexamples are welcome.
Here is another approach to show that $a_n$ is not prime when $c \gt 2$ and $n \gt 2$
We have (proof at end) $$a_{n+m}=a_na_{m+1}-a_{n-1}a_{m} \tag{*}$$ So, by induction on $j \ge 1$, $$a_{n+jn}=a_{n}a_{jn+1}-a_{n-1}a_{jn}$$ is always divisible by $a_n.$
Hence the only question is for $p \gt 2$ prime. But for any odd index $2m+1$ we have $$a_{(m+1)+m}=a_{m+1}^2-a_{m}^2=(a_{m+1}+a_m)(a_{m+1}-a_m)$$
That is about enough. We should check that $a_{m+1}-a_{m} \gt 1$. In fact, in the case $c=2$, the sequence is $0,1,2,3,4,5,\cdots$ but for $c \gt 2$ we have $a_{n+1}-a_{n}$ increasing since $$a_{n+1}-a_n =(c-1)a_n-a_{n-1}=(c-2)a_n+(a_n-a_{n-1}).$$
To prove $(*)$, replace $m+n$ by $s$ and write $$a_s=a_{s-m}a_{m+1}-a_{s-m-1}a_{m}$$ where $m \lt s$ so
$\begin{align*} a_s &= a_{s-1}a_2-a_{s-2}a_1 \\ &= a_{s-2}a_3-a_{s-3}a_2 \\ &=a_{s-3}a_4-a_{s-4}a_3 \\ &=\cdots. \end{align*}$
The first line is jut the defining recurrence relation $a_s=a_{s-1}c-a_{s-2}1$ and then the difference between successive lines is $$\left(a_{s-m}a_{m+1}-a_{s-m-1}a_{m}\right)-\left(a_{s-m-1}a_{m+2}-a_{s-m-2}a_{m+1}\right)$$ $$=\left(a_{s-m}+a_{s-m-2}\right)a_{m+1}-a_{s-m-1}\left(a_{m+2}+a_m \right)$$ $$=\left(ca_{s-m-1}\right)a_{m+1}-a_{s-m-1}\left(ca_{m+1} \right)=0$$
Observe that putting $c=i$ yields Fibonacci numbers times powers of $i$: $$0,1,i,-2,-3i,5,8i,-13,\cdots $$
This suggests that the divisibility result above (considering the $a_n$ as monic polynomials in variable $c$) can be sharpened to $$\gcd(a_n,a_m)=a_{\gcd(n,m)} $$ The usual proof applies mutatis mutandis.
This means that for any chosen integer value of $c$ the same fact holds, if $p$ is prime and $k=m$ is the least positive index with $p \mid a_k$ then $p \mid a_n$ exactly when $m \mid n$.
Put $u = (c + \sqrt{c^2-4})/2$. We have
$$a_{2n} = \frac{u^{2n}-u^{-2n}}{u-u^{-1}} = \left( \frac{ u^n-u^{-n}}{u-u^{-1}} \right) \left( \vphantom{\frac{ u^n-u^{-n}}{u-u^{-1}}} u^n + u^{-n} \right)$$
$$a_{2n+1} = \frac{u^{2n+1}-u^{-2n-1}}{u-u^{-1}} = \left( \frac{u^{n+1/2}-u^{-2n-1}}{u^{1/2}-u^{-1/2}} \right) \left( \frac{u^{n+1/2}+u^{-n-1/2}}{u^{1/2}+u^{-1/2}} \right) =$$ $$\left( \frac{u^{n+1/2}-u^{-n-1/2}}{u^{1/2}-u^{-1/2}} \right) \left( \frac{u^{n+1/2}+u^{-n-1/2}}{u^{1/2}+u^{-1/2}} \right)=\left( \frac{u^{n+1}-u^{-n}}{u-1} \right) \left( \frac{u^{n+1}+u^{-n}}{u+1} \right).$$
Put $v_{n} = u^n + u^{-n}$, $x_{n} = \frac{u^{n+1}-u^{-n}}{u-1} $, $y_{n}=\frac{u^{n+1}+u^{-n}}{u+1} $ so $a_{2n} = a_n v_n$ and $a_{2n+1} = x_n y_n$. I claim that each of $v$, $x$ and $y$ are integer valued sequences which are greater than $1$ for $n \geq 2$, thus proving the claim.
The fastest way to see this is to note the recursions: $$v_n = c v_{n-1} - v_{n-2} \quad v_0=2 \quad v_1 =c $$ $$x_n = c x_{n-1} - x_{n-2} \quad x_0=1 \quad x_1 =c+1 $$ $$y_n = c y_{n-1} - y_{n-2} \quad y_0=1 \quad y_1 =c-1 $$
A more conceptual way to see the rationality is to note that the Galois symmetry $\sqrt{c^2-4} \mapsto - \sqrt{c^2-4}$ takes $u$ to $u^{-1}$ and takes each of $v_n$, $x_n$ and $y_n$ to themselves.
For even $n$ it follows by induction that $a_n$ is divisible by $c$. Also, $a_n>c$ for $n\ge3$, so $a_n$ is not a prime.
For odd $n=2m+1$, one can do the following: Consider $c$ as an indeterminate. Then $a_n=P_n(c)$, where $P_n(X)\in\mathbb Z[X]$ (by binomially expanding Paolo's answer). One can show that there is a polynomial $h_m(X)\in\mathbb Z[X]$ of degree $m$ such that $P_n(X)=(-1)^mh_m(-X)h_m(X)$.
An explicit expression of $h_m$ is \begin{equation} h_m(X)=\prod_{k=1}^m(X-\zeta^k-\frac{1}{\zeta^k}), \end{equation} where $\zeta$ is a primitive $n$-th root of unity.
Now if $\lvert\gamma\rvert\ge3$, then each factor of $h_m(\gamma)$ has absolute value $\gt1$, so $h_m(\pm c)\ne\pm1$.
Thus $a_n$ is never a prime for $n\ge3$ and $c\ge 3$.
Just to start with: $$a_n=\frac{1}{\sqrt{c^2-4}}\left(\frac{c+\sqrt{c^2-4}}{2}\right)^n-\frac{1}{\sqrt{c^2-4}}\left(\frac{c-\sqrt{c^2-4}}{2}\right)^n$$
Your $a_n$ is a divisibility sequence, right? That means $a_n \mid a_{mn}$, so to get prime values, you'll pretty much need the index to be prime. Next, note that $a_n$ is approximately $c^n$. So the probability that $a_p$ is prime is approximately $1/p\log(c)$. Hence in the range you've checked, it's not so surprising that you didn't find any primes. This probabilistic model suggests that there are likely to be infinitely many primes in each sequence, i.e., for each $c>2$. But proving this is likely beyond our capabilities, just as we can't currently prove that there are infinitely many Mersenne primes.
