Делимость числовой последовательности

[Nikys]

Подкиньте, пожалуйста, идеи к решению задачи:
Доказать, что $1^{2011} + 2^{2011} + ... + n^{2011}$ не делится нацело на $n+2$ $\forall n \in \mathbb N
Если есть общая формула суммы числовой последовательности вида $1^k + 2^k + ... + n^k$ $\forall {n;k} \in \mathbb N - подскажите, пожалуйста. Буду благодарен.

[Nikys]

Мат.индукцией бить задачу пока не получалось, так как постоянно меняется делитель, следовательно несколько усложняется доказательство... Пробовал также связывать между собой различные остатки - не получалось пока. Думаю над решением задачи, но если у кого будет информация по второму вопросу - буду очень рад прочитать ответ на него здесь.

[svv]

Похоже, степень $2011$ можно заменить на любую нечетную степень $k \in \mathbb N$. Такой вариант и буду рассматривать.
Пусть $m=n+2$.
Тогда надо доказать, что $1^k+2^k+...+(m-2)^k$ не делится на $m$, где $k$ -- нечетное натуральное число.

Я проверил на компьютере, что $2 (1^k+2^k+...+m^k)$ делится на $m$.
Надеюсь, доказать это будет проще, чем исходное. Допустим, доказали.

Пусть $a \mod b$ означает остаток от деления $a$ на $b$.
Итак, $\left(2 (1^k+2^k+...+m^k)\right) \mod m = 0$
Но поскольку
$m^k \mod m =0$,
$(m-1)^k \mod m = m-1$ (очевидно? разложите бином Ньютона),
то $\left(2 (1^k+2^k+...+(m-2)^k)\right) \mod m = 2$
Значит, $(1^k+2^k+...+(m-2)^k) \mod m \neq 0$.

[Sonic86]

Nikys в сообщении #502287 писал(а):

Если есть общая формула суммы числовой последовательности вида $1^k + 2^k + ... + n^k$ $\forall {n;k} \in \mathbb N - подскажите, пожалуйста. Буду благодарен.

Есть, через числа Бернулли:
http://kvant.mccme.ru/1974/06/chisla_bernulli.htm
http://ru.math.wikia.com/wiki/%D0%A7%D0 ... 0%BB%D0%B8
Только она вряд ли поможет.

svv в сообщении #502317 писал(а):

Я проверил на компьютере, что $2 (1^k+2^k+...+m^k)$ делится на $m$.

(длинное, замудренное, беспонтовое и потому никому не нужное доказательство, читайте посты дальше)

Если $m$ нечетно, то это равносильно $1^k+2^k+...+m^k \equiv 0 \pmod m$, если $m$ четно, то полагая $m=2m_1$ получаем $2(1^k+2^k+...+m^k) \equiv 0 \pmod {2m_1} \Leftrightarrow$ $1^k+2^k+...+(m_1-1)^k+(m_1+1)^k...+(m_1+m_1-1)^k \equiv 0 \pmod {m_1}$ $\Leftrightarrow 2(1^k+2^k+...+(m_1-1)^k) \equiv 0 \pmod {m_1}$. Опускаясь по индукции по степени двойки $m$ в итоге приходим к тому, что $m_1$ нечетно и значит утверждение $2(1^k+2^k+...+m^k) \equiv 0 \pmod m$ вытекает из $1^k+2^k+...+m^k \equiv 0 \pmod m$ для нечетных $m$. Дальше пользуемся нечетностью ($x \to -x$ - автоморфизм $\mathbb{Z}_m^+$)
$1^k+2^k+...+m^k \equiv 0 \pmod m \Leftrightarrow 1^k+2^k+...+(m-1)^k \equiv 0 \pmod m$. Число слагаемых четно, значит можем сгруппировать $j$-е слагаемое с $m-j$-м попарно: $j^k + (m-j)^k \equiv 0 \pmod m$, а значит
$1^k+2^k+...+(m-1)^k \equiv 0 \pmod m \Leftrightarrow$ $ 1^k+(m-1)^k+2^k+(m-2)^k+...\equiv 0 \pmod m$ - верно.

[nnosipov]

Что-то длинновато как-то. Можно отбросить последнее слагаемое и доказывать, что $2(1^k+\ldots+(m-1)^k)$ делится на $m$. При нечётном $m$ это очевидно (достаточно разбить слагаемые на пары), а если $m$ чётно, то серединка $2(m/2)^k$ тоже поделится на $m$.

[Sonic86]

nnosipov в сообщении #502327 писал(а):

Что-то длинновато как-то. Можно отбросить последнее слагаемое и доказывать, что $2(1^k+\ldots+(m-1)^k)$ делится на $m$. При нечётном $m$ это очевидно (достаточно разбить слагаемые на пары), а если $m$ чётно, то серединка $2(m/2)^k$ тоже поделится на $m$.

Да, так лучше.

[RIP]

То же самое, но попроще: $2\left(1^k+\ldots+(m-1)^k\right)=\left(1^k+(m-1)^k\right)+\left(2^k+(m-2)^k\right)+\ldots+\left((m-1)^k+1^k\right)$.

[Nikys]

Спасибо за предложение рассмотреть в общем виде! Подскажите, верно ли предположение (как я понял, полное решение по правилам форума я как постановщик вопроса могу изложить...)
Рассмотрим два случая, пользуясь теорией остатков (конгруентностей, прошу простить, если написано неправильно, исхожу из правил украинской грамматики).
1) m - четное число, отличное от двух (т.к. $m=n+2$, $n \in \mathbb N$). Тогда несложно заметить, что:
$1^k \equiv 1^k (mod m)$
$2^k \equiv 2^k (mod m)$
...
$(\frac{m}{2})^k \equiv (\frac{m}{2})^k (mod m)$
$(\frac{m}{2} + 1)^k \equiv (\frac{m}{2} + 1 - m)^k \equiv -(\frac{m}{2} - 1)^k (mod m)$
...
$(m-3)^k \equiv (-3)^k (mod m)$
$(m-2)^k \equiv (-2)^k (mod m)$
Отметим, что k - нечетное. Ввиду этого $(-l)^k$ остается отрицательным. То есть:
$1^k + 2^k + ... + (m-2)^k \equiv 1^k + 2^k + ... + (\frac{m}{2})^k - (\frac{m}{2} - 1)^k - ... - 2^k \equiv (\frac{m}{2})^k + 1^k (mod m)$
Докажем, что $\forall m>2$ не исполняется равенство $(\frac{m}{2})^k + 1 \equiv 0 (mod m) $. Предположим, что это так. Тогда $(\frac{m}{2}) \equiv -1 \equiv m-1 (mod m) $. Несложными преобразованиями легко получить $m \equiv 2 (mod m) $, что противоречит условию m>2$.
Поэтому, когда m - четное, то данная сума на m не делится нацело.

2) Если m - нечетное число. Тогда $\frac{m}{2}$ не является целым, но являются целыми $\frac{m+1}{2}$ и $\frac{m-1}{2}$. Тогда аналогично:
$1^k \equiv 1^k (mod m)$
$2^k \equiv 2^k (mod m)$
...
$(\frac{m-1}{2})^k \equiv (\frac{m-1}{2})^k (mod m)$
$(\frac{m+1}{2})^k \equiv (\frac{m+1}{2} - m)^k \equiv -(\frac{m-1}{2})^k (mod m)$
...
$(m-3)^k \equiv (-3)^k (mod m)$
$(m-2)^k \equiv (-2)^k (mod m)$
Но тут ситуация будет выглядеть гораздо проще, чем в первом случае:
$1^k + 2^k + ... + (m-2)^k \equiv 1^k + 2^k + ... + (\frac{m-1}{2})^k - (\frac{m-1}{2})^k - ... - 2^k \equiv 1 (mod m)$
Поскольку $m\ge3$, то $m\ne1$.

Соответственно, поскольку сумма $1^k + 2^k + ... + (m-2)^k$ не делится нацело на m, то и не делится нацело сумма $1^{2011} + 2^{2011} + ... + n^{2011} на число n.

Что и следовало доказать!

-- 11.11.2011, 22:18 --

Sonic86
Огромное спасибо, сохраню на будущее!

[Shadow]

Вас советовали воспользоватся тем, что $a^k+b^k\vdots(a+b)$ при нечетном к. И записать сумму в виде:

$S(n-2)=1+[2^{2011}+(n-2)^{2011}]+[3^{2011}+(n-3)^{2011}]+...$
Все суммы в квадратных скобках делятся на $n$. Т.е при нечетном $n$ все ясно $S(n-2)\equiv1 \mod n$.
При четном $n$ слагаемое в середине останется без подружки, т.е надо рассмотреть отдельно
$1+(\frac n 2)^{2011}$ на делимость на $n$.
При $n=4k, (2k)^{2011}$ делится на $4k$, т.е опять $S(n-2)\equiv 1$. При $n=4k+2, (2k+1)^p\equiv 2k+1 \mod 4k+2$. T.e

$ S(n-2)=\begin{cases} 1, &n\ne 4k+2\\ 2k+2, & n=4k+2 \end{cases}\mod n $
Но ваше право выбрать решение.

[Nikys]

Shadow
Собственно, получается, я просто через конгруенцию выводил для нечетного то же, что вы и записали, но записал это более объемно, и тоже получил для нечетного то же самое слагаемое.
Но в общем плане последний вариант проще...я просто нередко "славлюсь" умением усложнять даже простое и идти в обход легких и красивых путей...)

-- 11.11.2011, 23:23 --

Sonic86
А вообще да, пользы не сильно много было, я просто думал, есть ли какая-нибудь сложная неоднопараметрическая формула, которая приводит эти суммы к виду, схожему с суммами:
$1+2+...+n=\frac{n(n+1)}{2}$
$1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$
$1^3+2^3+...+n^3=\frac{n^2(n+1)^2}{4}$
Но у меня большие сомнения на этот счет и, я думаю, так и обстоит дело с отсутствием таких формул...

[svv]

(Nikys)

Земляче, чудово, майже бездоганно пишете російською. Ось хіба єдине зауваження: конгруэнтность, конгруэнция.

[Shadow]

А Вас кстати советовали хитро рассмотреть $2S$. Там без вариантов и без дополнительных уговорок остаток 2.

[Nikys]

Shadow
Да, сейчас обратил внимание...Просто первый толчек дал мысль, дальше пошел сам, мало вникая в предложенные идеи и решая по-своему... Слишком уж углубляюсь в свое собственное решение.

(svv)

Дякую, так вже повелося, що навколо багато російськомовних людей. Але й тут є дірки, що потрібно корегувати... Ще раз дякую, візьму за позначку