Let $r(m) = m^2 + m -1$ and $q(m) =(r(m) +2)^2 – 2$ where $m$ is a positive integer.
For a particular $m$,
let $A_1=m^3+2m^2 +2m$
$ A_2 = q(m) A_1 + r(m) $
$A_n = q(m) A_{n-1}-A_{n-2}+r(m)$
It appears $A_n$ is always composite for all positive integers $m$ and $n$ except when $m=1$ and $n=1$ in which case $A_1=5$ is prime.
Is this observation true?
My attempt: For a particular $m$, we have
$A_1 \equiv 0 $ (mod $m$)
$A_2 \equiv – 1$ (mod $m$)
$A_3 \equiv 0 $ (mod $m$)
$A_4 \equiv 0 $ (mod $m$)
$A_5 \equiv – 1$ (mod $m$)
By induction, it can be shown that $A_n \equiv – 1$ (mod $m$) if $n \equiv 2 (\ $ mod $3$) and $A_n \equiv 0 $ (mod $m$) if $n \not\equiv 2 (\ $ mod $3$)
If $m>1$ and $n \not\equiv 2 (\ $ mod $3$) , $A_n$ is composite because $m \ | \ A_n$. The remaining cases to prove are $m=1$ and $n \equiv 2 (\ $ mod $3$)
NB: All terms of the sequence $A_n$ appear to be positive integer solutions in $z$ to the diophantine equation $(xz+1)(yz+1)=z^4+z^3 +z^2 +z+1$. More on this Diophantine equation https://mathoverflow.net/questions/403542/positive-integer-solutions-to-the-diophantine-equation-xz1yz1-z4z3-z/404278#404278
I found out a paper that considers a more general equation $(xz+1)(yz+1)=z^4+c_1z^3 +c_2z^2 +c_3z+1$ where $c_1, c_2, c_3$ are known integers. https://www.worldscientific.com/doi/abs/10.1142/S1793042117500129. However, it uses Mathematics am not familiar with. Also am more interested in the case when $z$ is prime. The paper provides an algorithm for constructing all solutions $x, y, z$ to the more general equation but does not discuss the primality of solutions in $z$. If the claim about $A_n$ is true, then to test $n = p^4 +p^3 +p^2 +p+1$, $p$ prime, for primality, one simply checks if $n$ passes the Fermat test and if $b^{(n-1)/p} \not\equiv 1$ ( mod $n$) for some base $b$
https://arxiv.org/abs/2005.02327 ( General purpose promality test – Theorem 2.2)
Best Answer
I finally found a full solution. I prefer to put it as a separate answer here since the method is somewhat different. As explained in the OP, we may assume $m=1$ ; then $A_n$ reduces to the sequence $a_n$ defined by $a_1=5,a_2=36$ and $a_n=7a_{n-1}-a_{n-2}+1$ for $n\geq 2$.
Now, consider the Fibonacci-type sequence $(f_n)_{n\geq 2}$ defined by
$$ f_2=3,f_3=4,f_n=f_{n-1}+f_{n-2} (n\geq 4) $$
and the complementary sequence $(g_n)_{n\geq 2}$ defined by
$$ g_2=12,g_3=62,g_4=243,g_5=1060, $$
$$ g_n=3g_{n-1}+6g_{n-2}-3g_{n-3}-g_{n-4} (n\geq 6) $$
Using the usual linear recurrence machinery, we see that $f_n$ is a linear combination of powers of the roots of $F=X^2-X-1$, and $g_n$ is a linear combination of powers of the roots of $G=X^4-3X^3-6X^2+3X+1=(X^2+X-1)(X^2-4X-1)$.
It follows that $h_n=f_ng_n$ is a linear combination of powers of the roots of $H$, the polynomials whose roots are exactly the product of one root of $F$ by one root of $G$. Using PARI-GP, I computed that $H=(X-1)^2(X^2-7X+1)(X^2+3X+1)$.
Now, because $X-1$ and $X^2-7X+1$ are factors of $H$, we see that $a_n$ satisfies the linear recurrence defined by $H$. One can check by hand that $a_n=h_n$ for $2\leq n \leq 9$ ; we deduce that this identity is satisfied for all $n$ because of the linear recurrence.
Conclusion : $a_n=f_ng_n$ for $n\geq 2$ with $f_n\geq 3$, so $a_n$ is composite.