Областная олимпиада по математике, 2016 год, 11 класс

Докажите, что для любых натуральных чисел $n$ и $k$ произведение $\left( {k + 1} \right)! \cdot \left( {{1^k} + {2^k} + \ldots +{n^k}} \right)$ делится на $n{(n + 1)}$.

Комментарий/решение

Решение. По Биному $(m+1)^{k+1}-m^{k+1}=∑_{j=0}^k {k+1 \choose j} m^j$. Просуммируем все такие тождества от $m=1$ до $m=n$: $(n+1)^{k+1}-1=∑_{j=0}^k {k+1\choose j} (1^j+2^j+⋯+n^j)$ (тождество Паскаля). Тогда $(k+1)!(1^k+2^k+⋯+n^k )=k![(n+1)^{k+1}-1-n-∑_{j=1}^{k-1}{k+1\choose j}(1^j+2^j+⋯+n^j)]$.

По предположению индукции (по $k$, база $k=1$ очевидна) каждое из $k!(1^j+2^j+⋯+n^j)$ делится на $n(n+1)$. Также $(n+1)^{k+1}-(n+1)$ делится на $n(n+1)$. Что и требовалось.

Ее можно решить с помощью LTE. Просто рассмотрите n = 2k, n = 2k + 1 и для каждого простого делителя из n и n + 1 использовать LTE