Recurrence Relation

Algebra Level 5

Brilli the ant has thought up a diabolical sequence of integers $a_n$ . It has initial values $a_1 = 1$ and $a_2 = 3$ . Subsequent terms are given by

$a_n = (n+1) a_{n-1} - n a_{n-2} \quad \mbox{ for } n\geq 3.$ Brilli the ant wants to know, how many integer values of $n$ from 1 to 1000 (inclusive) are there such that $a_n$ is a multiple of 11?