HMMT-Feb 2015 guts, Problem 21

Define a sequence $a_{i, j}$ of integers such that $a_{1, n}=n^{n}$ for $n \geq 1$ and $a_{i, j}=a_{i-1, j}+a_{i-1, j+1}$ for all $i, j \geq 1$. Find the last (decimal) digit of $a_{128,1}$.

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}\left(\begin{array}{c} m-1 \\ k \end{array}\right)(n+k)^{n+k}=\sum_{k \geq 0}\left(\begin{array}{c} m-1 \\ k \end{array}\right)(n+k)^{n+k} \] (The second expression is convenient for dealing with boundary cases. The induction relies on $\left(\begin{array}{c}m \\ 0\end{array}\right)=$ $\left(\begin{array}{c}m-1 \\ 0\end{array}\right)$ on the $k=0$ boundary, as well as $\left(\begin{array}{c}m \\ k\end{array}\right)=\left(\begin{array}{c}m-1 \\ k\end{array}\right)+\left(\begin{array}{c}m-1 \\ k-1\end{array}\right)$ for $k \geq 1$.) We fix $m=128$. Note that $\left(\begin{array}{c}127 \\ k\end{array}\right) \equiv 1(\bmod 2)$ for all $1 \leq k \leq 127$ and $\left(\begin{array}{c}127 \\ k\end{array}\right) \equiv 0(\bmod 5)$ for $3 \leq k \leq 124$, by Lucas' theorem on binomial coefficients. Therefore, we find that \[ a_{128,1}=\sum_{k=0}^{127}\left(\begin{array}{c} 127 \\ k \end{array}\right)(k+1)^{k+1} \equiv \sum_{k=0}^{127}(k+1)^{k+1} \equiv 0 \quad(\bmod 2) \] and \[ a_{128,1} \equiv \sum_{k \in[0,2] \cup[125,127]}\left(\begin{array}{c} 127 \\ k \end{array}\right)(k+1)^{k+1} \equiv 4 \quad(\bmod 5) \] Therefore, $a_{128,1} \equiv 4(\bmod 10)$. $\fbox{4}$.

Answer: 4