Problem: Find all positive integers $k$ such that: for every positive integer $n$, the sum
\[ \binom n0^k + \binom n1^k + \dots + \binom nn^k \]
is divisible by $n+1$.

Solution: The answer is all even $k$.

Let's abbreviate $S(n) \coloneq \binom n0^k + \dots + \binom nn^k$ for the sum in the problem.

\paragraph{Proof that even $k$ is necessary.}
Choose $n=2$. We need $3 \mid S(2) = 2+2^k$,
which requires $k$ to be even.

\begin{remark*}
  It's actually not much more difficult to just use $n = p-1$ for prime $p$,
  since $\binom{p-1}{i} \equiv (-1)^i \pmod p$.
  Hence $S(p-1) \equiv 1 + (-1)^k + 1 + (-1)^k + \dots + 1 \pmod p$,
  and this also requires $k$ to be even.
  This special case is instructive in figuring out the proof to follow.
\end{remark*}

\paragraph{Proof that $k$ is sufficient.}
From now on we treat $k$ as fixed, and we let $p^e$ be a prime fully dividing $n+1$.
The basic idea is to reduce from $n+1$ to $(n+1)/p$ by an induction.

\begin{remark*}
  Here is a concrete illustration that makes it clear what's going on.
  Let $p = 5$.
  When $n = p-1 = 4$, we have
  \[ S(4) = 1^k + 4^k + 6^k + 4^k + 1^k \equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 5. \]
  When $n = p^2-1 = 24$, the $25$ terms of $S(24)$ in order are, modulo $25$,
  \begin{align*}
    S(24) &\equiv 1^k + 1^k + 1^k + 1^k + 1^k\\
    &+ 4^k + 4^k + 4^k + 4^k + 4^k \\
    &+ 6^k + 6^k + 6^k + 6^k + 6^k \\
    &+ 4^k + 4^k + 4^k + 4^k + 4^k \\
    &+ 1^k + 1^k + 1^k + 1^k + 1^k \\
    &= 5(1^k + 4^k + 6^k + 4^k + 1^k).
  \end{align*}
  The point is that $S(24)$ has five copies of $S(4)$, modulo $25$.
\end{remark*}

To make the pattern in the remark explicit, we prove the following lemma
on each \emph{individual} binomial coefficient.
\begin{lemma}
  Suppose $p^e$ is a prime power which fully divides $n+1$. Then
  \[ \binom{n}{i} \equiv \pm \binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor} \pmod{p^e}. \]
\end{lemma}

\begin{proof}
  [Proof of lemma]
  It's easiest to understand the proof by
  looking at the cases $\left\lfloor i/p \right\rfloor \in \{0,1,2\}$ first.
  \begin{itemize}
  \ii For $0 \le i < p$, since $n \equiv -1 \mod p^e$, we have
  \[ \binom{n}{i} = \frac{n(n-1) \dots (n-i+1)}{1 \cdot 2 \cdot \dots \cdot i}
    \equiv \frac{(-1)(-2) \dots (-i)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \pm 1 \pmod{p^e}. \]
  \ii For $p \le i < 2p$ we have
  \begin{align*}
    \binom{n}{i}
    &\equiv \pm 1 \cdot \frac{n-p+1}{p} \cdot \frac{(n-p)(n-p-1) \dots (n-i+1)}{(p+1)(p+2) \dots i} \\
    &\equiv \pm 1 \cdot \frac{\frac{n-p+1}{p}}{1} \cdot \pm 1 \\
    &\equiv \pm \binom{\frac{n+1}{p}-1}{1} \pmod{p^e}.
  \end{align*}
  \ii For $2p \le i < 3p$ the analogous reasoning gives
  \begin{align*}
    \binom ni
    &\equiv \pm 1 \cdot \frac{n-p+1}{p} \cdot \pm 1 \cdot \frac{n-2p+1}{2p} \cdot \pm 1 \\
    &\equiv \pm \frac{\left(\frac{n+1}{p}-1\right)\left( \frac{n+1}{p}-2 \right) }{1 \cdot 2} \\
    &\equiv \pm \binom{\frac{n+1}{p}-1}{2} \pmod{p^e}.
  \end{align*}
  \end{itemize}
  And so on. The point is that in general, if we write
  \[ \binom ni = \prod_{1 \le j \le i} \frac{n-(j-1)}{j} \]
  then the fractions for $p \nmid j$ are all $\pm 1 \pmod{p^e}$.
  So only considers those $j$ with $p \mid j$; in that case
  one obtains the claimed $\binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor}$ exactly
  (even without having to take modulo $p^e$).
\end{proof}

From the lemma, it follows if $p^e$ is a prime power which fully divides $n+1$, then
\[ S(n) \equiv p \cdot S\left( \frac{n+1}{p}-1 \right) \pmod{p^e} \]
by grouping the $n+1$ terms (for $0 \le i \le n$)
into consecutive ranges of length $p$ (by the value of $\left\lfloor i/p \right\rfloor$).

\begin{remark*}
  Actually, with the exact same proof (with better $\pm$ bookkeeping) one may show that
  \[ n+1 \mid \sum_{i=0}^n \left( (-1)^i \binom ni \right)^k \]
  holds for \emph{all} nonnegative integers $k$, not just $k$ even.
  So in some sense this result is more natural than the one in the problem statement.
\end{remark*}