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](https://oeis.org/A001109) $c=6$
with a Pell equation.


Counterexamples are welcome.



Is the sequence $a_n=c a_{n-1} - a_{n-2}$ always composite for $n > 5$?
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$.


