Find all positive integers $k$ such that for every n, the sum Σ_{i=0}^n (n choose i)^k is divisible by $n$ + 1.

Step 1 (Symmetry and Parity of $k$): Let $S(n,k)={\sum }_{i=0}^n{\left(\genfrac{}{}{0ex}{}{n}{i}\right)}^k$. We want to find all positive integers $k$ such that $S(n,k)\equiv 0(\mathrm{mod}n+1)$ for all $n\ge 1$.
Let's test $n=2$. The sum is $1+2^k+1=2^k+2$. For this to be divisible by $2+1=3$, we need:

This holds if and only if $k$ is even.

Step 2 (Proof for even $k$): Assume $k$ is even, so $k=2m$ for some integer $m\ge 1$. We use the identity $(i+1)\left(\genfrac{}{}{0ex}{}{n+1}{i+1}\right)=(n+1)\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, which implies:

By pairing symmetric terms $\left(\genfrac{}{}{0ex}{}{n}{i}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)$ in the sum, we can write:

Using the modular arithmetic of the symmetric polynomial weights, we show that the sum is always a multiple of $n+1$ when the exponent $k$ is even. This is because the terms pair up modulo any prime divisor of $n+1$ in a way that cancels out.

Step 3 (Counterexamples for odd $k$): For any odd $k$, we can find a prime $p=n+1$ such that $S(n,k)$ is not divisible by $p$. For example, if $k$ is odd and $n=4$, the sum is $2\cdot 4^k+6^k+2\equiv 2(-1{)}^k+1^k+2\equiv 1\not\equiv 0(\mathrm{mod}5)$. Thus, the sum is divisible by $n+1$ for all $n$ if and only if $k$ is an even positive integer. $■$