Let $E/\mathbb{F}_q$ be an elliptic curve with $q=p^m$ for some prime $p$. Let $a_n=q^n+1-\#E(F_{q^n})$ and by convention we let $a_0=2$. Prove that $a_{n+2}=a_1a_{n+1}-qa_n$ for all $n>0$.
This linear recurrence gives a way to compute $a_n$ from the initial values $a_0=2$ and $a_1=q+1-\#E(\mathbb{F}_q)$. I think induction is the way to go but I'm not sure how to untangle $\#E(F_{q^n})$ exactly. What's a good way to prove this linear recurrence?
You can use that there is a complex number $\omega \in \mathbb C$ s.t. $|\omega| = \sqrt{q}$ and
$$\#E(\mathbb F_{q^n}) = q^n +1 - (\omega^n+\overline\omega^n)$$
where $\overline\omega$ is the complex conjugate of $\omega$. (Weil conjecture applied to elliptic curves.)
Applying this formula makes it essentially trivial.
$a_n = q^n +1 - \#E(\mathbb F_{q^n}) = \omega^n + \overline\omega^n$.
Then $$\begin{align*} a_1 a_{n+1} - qa_n &= (\omega+\overline\omega)(\omega^{n+1} + \overline\omega^{n+1}) - q(\omega^n + \overline\omega^n) = \ldots \\ \end{align*}$$