Why does this linear recurrence mod $p$ prime have zeros every $\frac{p \pm 1}{2}$ steps? Why does the recurrence $a_n=((q+1)\cdot a_{n-1} - a_{n-2}) \mod p$ for $p, q$ odd prime, $a_0=0,a_1=q, p > q$ seem to have zeros every $\frac{p+1}{2}$ or $\frac{p-1}{2}$ steps?
I've written up some code to check it for $p,q<200$ and it seems to hold. The suggested questions talk about 'quadratic residues', which I've heard of and it looks similar, but I've never learned about them formally.
In addition, it appears that the period switches from $\frac{p-1}{2}$ to $\frac{p+1}{2}$ or vice versa every time there is a odd number that isn't prime. Does that hold, and if so, why is that the case?
 A: I shall work over $\mathbb{F}_{p^2}$.  Consider the polynomial $x^2-(q+1)x+1\in\mathbb{F}_p[x]$.  Let the roots of this polynomial be $\alpha,\beta\in\mathbb{F}_{p^2}$.  Note that
$$(\alpha-\beta)^2=(q+1)^2-4=(q-1)(q+3)\neq 0$$
(due to the fact that that $p>q$).  That is, $\alpha\neq \beta$.  The sequence is given by
$$a_n=q\left(\frac{\alpha^n-\beta^n}{\alpha-\beta}\right)\,.$$
Case I: $\alpha,\beta \in \mathbb{F}_p$ (equivalently, $\left(\frac{q-1}{p}\right)=\left(\frac{q+3}{p}\right)$).  In this case, the relation $\alpha\beta=1$ implies that either both are square or both are non-square.  Thus, $\alpha^{\frac{p-1}{2}}=\left(\frac{\alpha}{p}\right)=\left(\frac{\beta}{p}\right)=\beta^{\frac{p-1}{2}}$, implying that $a_{k\left(\frac{p-1}{2}\right)}=0$ in $\mathbb{F}_p$ for every $k=0,1,2,\ldots$.
Case II: $\alpha,\beta\notin\mathbb{F}_p$ (equivalently, $\left(\frac{q-1}{p}\right)=-\left(\frac{q+3}{p}\right)$).  In this case, we note that $$\alpha^p\beta^p=(\alpha\beta)^p=1\text{ and }\alpha^p+\beta^p=(\alpha+\beta)^p=(q+1)^p=q+1\,.$$
Hence, $\alpha^p$ and $\beta^p$ are also roots of $x^2-(q+1)x+1$.  However, $\alpha^p\neq \alpha$ (otherwise, $\alpha\in\mathbb{F}_p$).  Therefore, $\alpha^p=\beta$ (and so $\beta^p=\alpha$).  Consequently, $$\alpha^{p+1}=\alpha\beta=1\,,$$
whence
$$\alpha^{\frac{p+1}{2}}=\left(\frac{1}{\alpha}\right)^{\frac{p+1}{2}}=\beta^{\frac{p+1}{2}}\,.$$
This shows that $a_{k\left(\frac{p+1}{2}\right)}=0$ in $\mathbb{F}_p$ for all $k=0,1,2,\ldots$.

Extra
The condition that $p>q$ or that $q$ is an odd prime is not necessary ($q$ can even be negative integers).  You only need $p\nmid q$, $p\nmid q-1$, and $p\nmid q+3$ for the claim to hold.  However, in the case $p\nmid q$, but $p\mid q-1$ or $p\mid q+3$, there is a version of this claim.  Indeed, one can show that
$$a_n=qns^{n-1}\,,$$
where $s:=+1$ if $p\mid q-1$, and $s:=-1$ if $p\mid q+3$.  Hence, $a_n=0$ in $\mathbb{F}_p$ if and only if $p\mid n$.  In the case $p\mid q$, then $a_n=0$ in $\mathbb{F}_p$ for every $n\in\mathbb{Z}_{\geq 0}$.
