Теория чисел делимость

[rightways]

$k$ и $n$ натуральные числа. Надо доказать, что число

$$(k+1)!(1^k+2^k+...+n^k)$$

всегда делится на $n(n+1)$.

[gris]

Если $k\geqslant n$, то первый факториал содержит необходимые сомножители.
А вот если, например, $k=2;n=3$
$(k+1)!(1^k+2^k+...+n^k)=(2+1)!(1^2+2^2+3^2)=6\cdot14$
$n(n+1)=12$
Хотя для квадратов и кубов почти всё следует из формулы суммы, а что там для более высоких степеней?

[mihiv]

При $k$ нечетном и четном $n$ объединяем попарно слагаемые в исходном выражении: $\left (1^k+n^k\right )+\dots +\left ((\dfrac n2)^k+(\dfrac n2+1)^k\right )$. Выражение в каждой круглой скобке делится на $n+1$.
Можно объединить слагаемые по-другому: $\left (1^k+(n-1)^k\right )+ \left (2^k+(n-2)^k\right )+\dots +\left ((\dfrac n2-1)^k+(\dfrac n2+1)^k\right )+(\dfrac n2)^k+n^k$
Теперь выражение в каждой круглой скобке делится на $n.$ Число $2(\dfrac n2)^k=n(\dfrac n2)^{k-1} $ также делится на $n$ (двойку можем занять из $(k+1)!$). Так как $n$ и $n+1$ взаимно просты все выражение делится на $n(n+1)$. Случай нечетного $n$ доказывается аналогично. При четном $k$ нужно другое доказательство.

[Sonic86]

(более высокие степеня)

gris в сообщении #1088232 писал(а):

а что там для более высоких степеней?

Ну вот:
http://mathworld.wolfram.com/PowerSum.html
Здесь можно также видеть, что суммы четных степеней делятся на $2n+1$, а суммы нечетных степеней выше первой делятся на $n^2(n+1)^2$ - отсюда можно тоже конструировать задачи и доказывать их.

Наверное, надо работать как с суммами характеров:
Пусть $m\in\{n;n+1\}$
$(\forall m)S:=\sum\limits_{j=1}^n j^k \equiv \sum\limits_{j=1}^m j^k \pmod m$
Если существует $c:c^k\not\equiv 1\pmod m$, то $c^kS\equiv S \pmod m$, т.к. $x\to cx \pmod m$ - перестановка на $\mathbb{Z}_m\setminus\{0\}$. Значит $S\equiv 0\pmod m$, и т.к. $n\perp n+1$, то $n(n+1)|S$.
А вот если такого $c$ не существует, то $\operatorname{lcm}(\lambda(n),\lambda(n+1))|k$, т.е. $k$ будет достаточно велико, и тогда должен сработать факториал ($\lambda$ - функция Кармайкла).
Но вот тут я пока явное рассуждение не вижу, тут нужен минимум какой-то перебор.

[gris]

Они делятся как многочлены, но впереди выражения есть дробь. Надо показать, что эта дробь частично сокращается с выражением для суммы, а частично с первым факториалом.

[Sonic86]

gris в сообщении #1088306 писал(а):

Они делятся как многочлены, но впереди выражения есть дробь. Надо показать, что эта дробь частично сокращается с выражением для суммы, а частично с первым факториалом.

Ну это да. Можно также сказать, что я перебрал только все $k\leqslant 10$ и надо еще перебрать все $k>10$, а то мало ли
Я лишь хотел сказать, что отсюда можно построить еще несколько аналогичных задач.

[DeBill]

А давайте сочиним формулу для суммы $k-$х степеней первых $n$ натуральных.
Стартовать можно с замечательной суммы

$C^k_k + C^k_{k+1}+ ... + C^k_{n} = C^{k+1}_{n+1}$

(Если нарисовать в треугольнике Паскаля эту сумму, и чуток опустить первое слагаемое - оно равно 1, то полученный "сапог" моментально свернется в точку - стоящую справа).
Заметим, что

$ C^k_m = \frac{m!}{(m-k)! k!} = \frac{m\cdot(m-1)\cdot...\cdot (m-k+1)}{k!}=\frac{m^k+ ...}{k!}$

где многоточием обозначен многочлен от $m$ степени $k-1$ с целыми коэффициентами и НУЛЕВЫМ свободным членом.
Ну, и теперь индукция по $k$ дает нам нужную делимость, ибо множитель $n\cdot(n+1)$ есть в правой части (а знаменателем её как раз и будет $(k+1)!$).
ЗЫ А не доказал ли я заодно и делимость а)на $\frac{n!}{(n-k)!}$? б) при $k=0$ ? Вроде нет, т.к. а) при шаге индукции использовалсь $k=1$ б) НЕТ