32. $[\mathbf{1 8}]$ Let $p$ be a prime positive integer. Define a mod- $p$ recurrence of degree $n$ to be a sequence $\left\{a_{k}\right\}_{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(\bmod p)$. Compute the number of distinct linear recurrences of degree at most $n$ in terms of $p$ and $n$.
Answer: $1-n \frac{p-1}{p+1}+\frac{p^{2}\left(p^{2 n}-1\right)}{(p+1)^{2}}$
In the solution all polynomials are taken modulo $p$. Call a polynomial nice if it is monic with nonzero constant coefficient. We can associate each recurrence relation with a polynomial: associate
$$
c_{n} a_{i+n}+c_{n-1} a_{i+n-1}+\ldots+c_{1} a_{i+1}+c_{0} a_{i}=0
$$
with
$$
c_{n} x^{n}+c_{n-1} x^{n-1}+\ldots+c_{1} x+c_{0} .
$$

Let $D_{i}$ be the set of mod- $p$ recurrences $\left\{a_{k}\right\}_{k \geq 0}$ where $i$ is the least integer so that $\left\{a_{k}\right\}_{k \geq 0}$ has degree $i$, and let $d_{i}=\left|D_{i}\right|$.
Let $S_{n}$ be the set of pairs $\left(\left\{a_{k}\right\}_{k \geq 0}, P\right)$ where $\left\{a_{k}\right\}_{k \geq 0}$ is a mod- $p$ recurrence, and $P$ is a nice polynomial associated to a recurrence relation of degree at most $n$ satisfied by $\left\{a_{k}\right\}_{k \geq 0}$. To find $d_{n}$ generally, we count the number of elements in $S_{n}$ in two ways.
One the one hand, for each sequence $\left\{a_{k}\right\}_{k \geq 0}$ in $D_{i}$, there exist $p^{n-i}$ polynomials $P$ such that $\left(\left\{a_{k}\right\}_{k \geq 0}, P\right) \in S$. Indeed, $\left\{a_{k}\right\}_{k \geq 0}$ satisfies any recurrence relation associated with a polynomial multiple of $P$. When $j=i$ there is just one nice degree $j$ polynomial that is a multiple of $P, P$ itself. For $j>i$, there are $(p-1) p^{j-i-1}$ nice polynomials of degree $j$ that are multiples of $P$, namely $Q P$ where $Q$ is a nice polynomial of degree $j-i$. (There are $p$ choices for the coefficients of $x, \ldots, x^{j-i-1}$ and $p-1$ choices for the constant term.) So the number of nice polynomial multiples of degree at most $n$ is
$$
1+\sum_{j=i+1}^{n}(p-1) p^{j-i-1}=1+(p-1)\left(\frac{p^{n-i}-1}{p-1}\right)=p^{n-i} .
$$

Hence
$$
\left|S_{n}\right|=\sum_{i=0}^{n} d_{i} p^{n-i}
$$

On the other hand, given a monic polynomial $P$ of degree $i$, there are $p^{i}$ recurrences $\left\{a_{k}\right\}_{k \geq 0}$ such that $\left(\left\{a_{k}\right\}_{k \geq 0}, P\right) \in S$, since $a_{0}, \ldots, a_{i-1}$ can be chosen arbitrarily and the rest of the terms are determined. Since there are $(p-1) p^{i-1}$ nice polynomials of degree $i \neq 0$ (and 1 nice polynomial for $i=0$ ), summing over $i$ gives
$$
\left|S_{n}\right|=1+\sum_{i=1}^{n}(p-1) p^{2 i-1}
$$

Now clearly $d_{0}=1$. Setting (1) and (2) equal for $n$ and $n+1$ give
$$
\begin{aligned}
\sum_{i=0}^{n+1} d_{i} p^{n+1-i} & =1+(p-1) \sum_{i=1}^{n+1} p^{2 i-1} \\
\sum_{i=0}^{n} d_{i} p^{n-i} & =1+(p-1) \sum_{i=1}^{n} p^{2 i-1} \\
\Longrightarrow \sum_{i=0}^{n} d_{i} p^{n+1-i} & =p+(p-1) \sum_{i=1}^{n} p^{2 i} .
\end{aligned}
$$

Subtracting (4) from (3) yields:
$$
\begin{aligned}
d_{n+1} & =1-p+(p-1) \sum_{i=1}^{2 n+1}(-1)^{i+1} p^{i} \\
& =(p-1) \sum_{i=0}^{2 n+1}(-1)^{i+1} p^{i} \\
& =(p-1)^{2} \sum_{i=0}^{n} p^{2 m} \\
& =(p-1)^{2}\left(\frac{p^{2 n+2}-1}{p^{2}-1}\right) \\
& =\frac{(p-1)\left(p^{2 n+2}-1\right)}{p+1}
\end{aligned}
$$

Thus the answer is
$$
\begin{aligned}
\sum_{i=0}^{n} d_{i} & =1+\frac{p-1}{p+1} \sum_{i=1}^{n}\left(p^{2 i}-1\right) \\
& =1+\frac{p-1}{p+1}\left(-n+p^{2} \cdot \frac{p^{2 n}-1}{p^{2}-1}\right) \\
& =1-n \frac{p-1}{p+1}+\frac{p^{2}\left(p^{2 n}-1\right)}{(p+1)^{2}}
\end{aligned}
$$