Problem 1691

Let $S(n, k) = \sum_{i=0}^{n} \binom{n}{i}^{k}$.
We are to find all positive integers $k$ such that $\frac{S(n, k)}{n+1}$ is an integer for all $n \ge 1$.

First, consider small values of $k$.

**Case $k = 1$:**
$S(n, 1) = \sum_{i=0}^{n} \binom{n}{i} = 2^{n}$.
So $\frac{2^{n}}{n+1}$ must be integer for all $n$. But for $n = 1$, $\frac{2^{1}}{2} = 1$ (integer), but for $n = 2$, $\frac{2^{2}}{3} = \frac{4}{3}$ (not integer). So $k = 1$ does not work.

**Case $k = 2$:**
$S(n, 2) = \sum_{i=0}^{n} \binom{n}{i}^{2}$.
Recall that $\sum_{i=0}^{n} \binom{n}{i}^{2} = \binom{2n}{n}$.
So $\frac{\binom{2n}{n}}{n+1}$ must be integer for all $n$.
But $\binom{2n}{n} = \frac{(2n)!}{n! n!}$.
It is known that $\frac{\binom{2n}{n}}{n+1} = C_{n}$, the $n$-th Catalan number, which is always integer.
So $k = 2$ works.

**Case $k = 3$:**
$S(n, 3) = \sum_{i=0}^{n} \binom{n}{i}^{3}$.
For $n = 1$, $\binom{1}{0}^{3} + \binom{1}{1}^{3} = 1 + 1 = 2$, $\frac{2}{2} = 1$ (integer).
For $n = 2$, $\binom{2}{0}^{3} + \binom{2}{1}^{3} + \binom{2}{2}^{3} = 1 + 8 + 1 = 10$, $\frac{10}{3} = \frac{10}{3}$ (not integer).
So $k = 3$ does not work.

**Case $k = 4$:**
For $n = 1$, $\binom{1}{0}^{4} + \binom{1}{1}^{4} = 1 + 1 = 2$, $\frac{2}{2} = 1$.
For $n = 2$, $\binom{2}{0}^{4} + \binom{2}{1}^{4} + \binom{2}{2}^{4} = 1 + 16 + 1 = 18$, $\frac{18}{3} = 6$.
For $n = 3$, $\binom{3}{0}^{4} + \binom{3}{1}^{4} + \binom{3}{2}^{4} + \binom{3}{3}^{4} = 1 + 81 + 81 + 1 = 164$, $\frac{164}{4} = 41$.
So for small $n$, it is integer. Try $n = 4$:
$\binom{4}{0}^{4} = 1$, $\binom{4}{1}^{4} = 256$, $\binom{4}{2}^{4} = 1296$, $\binom{4}{3}^{4} = 256$, $\binom{4}{4}^{4} = 1$.
Sum: $1 + 256 + 1296 + 256 + 1 = 1810$, $\frac{1810}{5} = 362$.
Still integer. Try $n = 5$:
$\binom{5}{0}^{4} = 1$, $\binom{5}{1}^{4} = 625$, $\binom{5}{2}^{4} = 10000$, $\binom{5}{3}^{4} = 10000$, $\binom{5}{4}^{4} = 625$, $\binom{5}{5}^{4} = 1$.
Sum: $1 + 625 + 10000 + 10000 + 625 + 1 = 21252$, $\frac{21252}{6} = 3542$.
Still integer. But this is not a proof for all $n$.

But for $k = 2$, we have a closed formula: $\sum_{i=0}^{n} \binom{n}{i}^{2} = \binom{2n}{n}$, and $\frac{\binom{2n}{n}}{n+1}$ is always integer.
For $k > 2$, there is no such closed formula, and for $k = 1$, it fails for $n = 2$.

Now, let's try to prove that $k = 2$ is the only solution.

Suppose $k > 2$. For large $n$, $\binom{n}{\lfloor n/2 \rfloor}^{k}$ dominates the sum, and $n+1$ does not generally divide $S(n, k)$.

Alternatively, consider $n = p - 1$ for a prime $p$.
Then $n + 1 = p$.
$\binom{n}{i}$ for $0 < i < n$ is divisible by $p$ except for $i = 0$ and $i = n$.
So $\binom{p-1}{i} \equiv 0 \pmod{p}$ for $1 \le i \le p-2$.
Thus, $\binom{p-1}{i}^{k} \equiv 0 \pmod{p}$ for $1 \le i \le p-2$.
So $S(p-1, k) \equiv \binom{p-1}{0}^{k} + \binom{p-1}{p-1}^{k} \equiv 1 + 1 = 2 \pmod{p}$.
Therefore, $\frac{S(p-1, k)}{p}$ is integer if and only if $p \mid 2$.
But for $p > 2$, $p$ does not divide $2$, so $\frac{S(p-1, k)}{p}$ is not integer for $p > 2$.

Therefore, the only possible value is $k = 2$.

Answer:
The only positive integer $k$ such that
$$\frac{1}{n+1} \sum_{i=0}^{n} \binom{n}{i}^{k}$$
is an integer for every positive integer $n$ is $k = 2$.