Given $f$ an algebraic curve, let $N_f(p,k)$ the points of $f$ over $\mathbb{F}_{p^k}$ I need to prove that there exists a recursive formula of order $2g+2$ where $g$ is the genus of $f$. I know that according to Shparlinkski (page 160 from https://www.springer.com/la/book/9780792356622) it can be deduced from the expression $$N_f(p,k)=p^k+1-\sum_{i=1}^{2g}{w_i}^k$$ where $w_i\in \mathbb{C}$ are such that $|w_i|=\sqrt{p}$ and $\overline{w}_i=w_{i+g}$.
Any help would be appreciated.
Thanks!
Surely you mean $$N_f(p,k)=p^k+1-\sum_{i=1}^{2g}w_i^k?$$
If $b_1,\ldots,b_m$ and $c_1,\ldots,c_m$ are any numbers and we define $$a_n=\sum_{k=1}^m b_kc_k^n$$ then the sequence $(a_n)$ satisfies the recurrence $$a_n=-\sum_{k=1}^m u_ka_{m-k}$$ where $$\prod_{j=1}^m(X-c_j)=X^m+\sum_{j=1}^n u_jX^{m-j}.$$
In your example, the $c_k$ are $p,1,w_1,\ldots,w_{2g}$ and the $b_k$ are $1,1,-1,\ldots,-1$.