Harvard-MIT Mathematics Tournament

Solution:

Answer: $1 - n \frac{p-1}{p+1} + \frac{p^{2}(p^{2n}-1)}{(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 $\{a_{k}\}_{k \geq 0}$ where $i$ is the least integer so that $\{a_{k}\}_{k \geq 0}$ has degree $i$, and let $d_{i} = |D_{i}|$.
Let $S_{n}$ be the set of pairs $\left(\{a_{k}\}_{k \geq 0}, P\right)$ where $\{a_{k}\}_{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 $\{a_{k}\}_{k \geq 0}$. To find $d_{n}$ generally, we count the number of elements in $S_{n}$ in two ways.

On the one hand, for each sequence $\{a_{k}\}_{k \geq 0}$ in $D_{i}$, there exist $p^{n-i}$ polynomials $P$ such that $\left(\{a_{k}\}_{k \geq 0}, P\right) \in S$. Indeed, $\{a_{k}\}_{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
$$|S_{n}| = \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 $\{a_{k}\}_{k \geq 0}$ such that $\left(\{a_{k}\}_{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
$$|S_{n}| = 1 + \sum_{i=1}^{n} (p-1) p^{2i-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^{2i-1} \\ \sum_{i=0}^{n} d_{i} p^{n-i} & = 1 + (p-1) \sum_{i=1}^{n} p^{2i-1} \\ \Longrightarrow \sum_{i=0}^{n} d_{i} p^{n+1-i} & = p + (p-1) \sum_{i=1}^{n} p^{2i} \end{aligned}$$
Subtracting (4) from (3) yields:
$$\begin{aligned} d_{n+1} & = 1 - p + (p-1) \sum_{i=1}^{2n+1} (-1)^{i+1} p^{i} \\ & = (p-1) \sum_{i=0}^{2n+1} (-1)^{i+1} p^{i} \\ & = (p-1)^{2} \sum_{i=0}^{n} p^{2m} \\ & = (p-1)^{2}\left(\frac{p^{2n+2}-1}{p^{2}-1}\right) \\ & = \frac{(p-1)(p^{2n+2}-1)}{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} (p^{2i} - 1) \\ & = 1 + \frac{p-1}{p+1}(-n + p^{2} \cdot \frac{p^{2n}-1}{p^{2}-1}) \\ & = 1 - n \frac{p-1}{p+1} + \frac{p^{2}(p^{2n}-1)}{(p+1)^{2}} \end{aligned}$$