Областная олимпиада по математике, 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

Решение на LTE слишком геморное попробуйте через Если мы положим:

S(k,n) = 1^n + 2^n + 3^n + .... + k^n

то, как указано в других ответах, это дается формулой Фаульхабера. Вы также можете вычислить это итеративно, используя рекурсию:

S(k,n+1) = (n+1) [ F(k,n) + k F(-1,n) ]

где

F(k,n) = интеграл от t = 0 до k от S(t,n)dt.

Это справедливо для k > 0, поэтому мы можем начать с S(k,1) = 1/2 k (k+1) и получить выражения для S(k,n) путем многократного интегрирования. Дальше можно легко (k+1)! доказать и для него