Question 38
Let $p$ be a prime positive integer. Define a mod-$p$ recurrence of degree $n$ to be a sequence $\{a_k\}_{k \geq 0}$ of numbers modulo $p$ satisfying a relation of the form $a_{i+n} = c_{n-1} a_{i+n-1} + \ldots + c_1 a_{i+1} + c_0 a_i$ for all $i \geq 0$, where $c_0, c_1, \ldots, c_{n-1}$ are integers and $c_0 \not\equiv 0 \pmod{p}$. Compute the number of distinct linear recurrences of degree at most $n$ in terms of $p$ and $n$.