Rewriting the recurrence as \[2a_n = \sum_{k=0}^n\binom{n}{k}a_k\] we find that the power series \[\mathcal{A}(z) = \sum_{n=0}^{\infty}\frac{a_nz^n}{n!}\] satisfies the relation \[\mathcal{A}(z)e^z = 2\mathcal{A}(z) - 1\Longrightarrow \] \[\mathcal{A}(z) = \frac{1}{2-e^z} = \frac 12\left(1+\frac{e^z}{2}+\frac{e^{2z}}{2^2}+\frac{e^{3z}}{2^3}+\dots\right)\] implying that for $n\ge 1$, we have \[a_n = \frac{1}{2}\cdot \left(\sum_{\ell = 1}^{\infty} \frac{\ell^n}{2^{\ell}}\right).\] Now with this closed form expression, the conclusion is trivial, since we will have \[\ell^{p^mq+r}\equiv \ell^{p^{m-1}q+r}\equiv 0\pmod {p^m}\] necessarily from \[\ell^{p^m}\equiv \ell^{p^{m-1}}\pmod {p^{m}}\] for each integer $\ell$. Hence, it is forced that $$a_{p^mq+r} \equiv a_{p^{m-1}q+r} \pmod{p^m}$$ as desired$.\;\blacksquare$ Unfortunately, the above solution only works for odd primes $p$. If I solve the problem for $p=2$, I will try and post a solution later.

Let's solve the remaining case $p = 2$. If $m = 1$ then the conclusion says every $a_n$ is odd, which is true by direct induction. Suppose $m \geq 2$, then we have $$ l^{2^mq + r} \equiv l^{2^{m-1}q + r} ~(mod ~p^{m+1}), \forall q, r > 0.$$Now write $$a_{2^mq + r} - a_{2^{m-1}q + r} = 2^m \left(\sum_{l = 1}^{\infty} 2^{-l} \cdot \frac{l^{2^mq + r} - l^{2^{m-1}q + r}}{2^{m+1}}\right). $$To complete the proof, it suffices to establish the following lemma: Lemma: For any polynomial $f(l)$ that takes integer values at integers, the infinite sum $\sum_{l=1}^{\infty} 2^{-l} f(l)$ is an integer. Proof. Let $S$ denote the sum, then $2S = \sum_{l = 0}^{\infty} 2^{-l} f(l+1) = f(1) + S + \sum_{l=1}^{\infty} 2^{-l} (f(l+1)- f(l))$. So $S = f(1) + \sum_{l=1}^{\infty} 2^{-l} (f(l+1)- f(l))$. But $f(l+1) - f(l)$ is another integer-valued polynomial, only with lower degree. The lemma follows from induction!

Just a remark,the series $\{a_i\}_{i=0}^{\infty}$ also appears as $F(n)$ in the problem: Let $F(n)$ be the number of functions $f : \{1, 2, ..., n\}\mapsto \{1, 2, ..., n\}$ with the property that if $i$ is in the range of $f$, then so is $j$ for all $j < i$. Which was on the Miklos Schweitzer competition.

nice solution

Claim. The number of ways $n$ runners can finish a race, allowing ties, is equal to $a_n$. Proof. Proceed by strong induction with $n = 0$ trivial. For $n \ge 1$ runners, once the group of runners (say, of size $k$) coming in first place is chosen, there are $a_{n - k}$ ways for the remaining runners to finish. Then \[a_n = \sum_{k = 1}^{n} \binom{n}{k} a_{n - k} = \sum_{k = 0}^{n - 1} \binom{n}{n - k} a_k = \sum_{k = 0}^{n - 1} \binom{n}{k} a_k\]as desired. $\square$ Suppose there are $p^m q + r$ runners in the race; label them $c_{i, j}$ (for $1 \le i \le q$, $j \in \mathbb{Z} / p^m\mathbb{Z}$) and $d_1, \dots, d_r$. Consider a placing $\mathcal{P}_0$ of the runners and its images $\mathcal{P}_1, \dots, \mathcal{P}_{p^m - 1}$ under the cyclic shift \[c_{i, j} \to c_{i, j + 1} \to c_{i, j + 2} \to \dots \to c_{i, j + p^m - 1}.\]We show there are exactly $a_{p^{m - 1} q + r}$ placings $\mathcal{P}_0$ whose cyclic shifts are not all distinct. Indeed, if two of them coincide, as $p^m$ is a prime power it necessarily follows that $\mathcal{P}_0 = \mathcal{P}_{p^{m - 1}}$. Then, $c_{i, j}$ and $c_{i, j + p^{m - 1}}$ must be tied for all $i, j$; giving $p^{m - 1} q + r$ "people" in the race: namely, \[\{c_{i, j}, c_{i, j + p^{m - 1}}, \dots, c_{i, j + (p - 1)p^{m - 1}}\} \quad \text{for} \; 1 \le i \le q, 1 \le j \le p^{m - 1} \qquad \text{and} \qquad d_1, \dots, d_r.\]Evidently, there are $a_{p^m q + r} - a_{p^{m - 1} q + r}$ placings whose $p^m$ cyclic shifts are all distinct. Thus, these $a_{p^m q + r} - a_{p^{m - 1} q + r}$ placings may be partitioned into groups of size $p^m$, hence \[a_{p^m q + r} \equiv a_{p^{m - 1} q + r} \pmod{p^m}.\]