HMMT February

Solution:

By applying the recursion multiple times, we find that $a_{1,1} = 1$, $a_{2, n} = n^{n} + (n+1)^{n+1}$, and $a_{3, n} = n^{n} + 2(n+1)^{n+1} + (n+2)^{n+2}$. At this point, we can conjecture and prove by induction that
$$a_{m, n} = \sum_{k=0}^{m-1} \binom{m-1}{k} (n+k)^{n+k} = \sum_{k \geq 0} \binom{m-1}{k} (n+k)^{n+k}$$
(The second expression is convenient for dealing with boundary cases. The induction relies on $\binom{m}{0} = \binom{m-1}{0}$ on the $k=0$ boundary, as well as $\binom{m}{k} = \binom{m-1}{k} + \binom{m-1}{k-1}$ for $k \geq 1$.) We fix $m = 128$. Note that $\binom{127}{k} \equiv 1 \pmod{2}$ for all $1 \leq k \leq 127$ and $\binom{127}{k} \equiv 0 \pmod{5}$ for $3 \leq k \leq 124$, by Lucas' theorem on binomial coefficients. Therefore, we find that
$$a_{128,1} = \sum_{k=0}^{127} \binom{127}{k} (k+1)^{k+1} \equiv \sum_{k=0}^{127} (k+1)^{k+1} \equiv 0$$
and
$$a_{128,1} \equiv \sum_{k \in [0,2] \cup [125,127]} \binom{127}{k} (k+1)^{k+1} \equiv 4 \quad (\bmod 5).$$
Therefore, $a_{128,1} \equiv 4 \pmod{10}$.