Frobenius trace recurrence
= Frobenius trace recurrence
{c}
{title2=$t_n=t\,t_{n-1}-q\,t_{n-2},\quad t_0=2,\ t_1=t$}
For an <elliptic curve> over $\mathbb F_q$, the <Frobenius isogeny> has characteristic polynomial $T^2-tT+q$. Taking traces of its powers gives this recurrence. If $\alpha,\beta$ are the roots, then $t_n=\alpha^n+\beta^n$ and $\#E(\mathbb F_{q^n})=q^n+1-t_n$. The <Hasse bound> implies $|\alpha|=|\beta|=\sqrt q$, including the repeated-root case.