Делимость суммы определенных биномиальных коэффициентов.

[Руст]

Доказать, что сумма биномиальных коэффициентов

$$S=\sum_{0< k< n, p-1|k} \binom{n}{k}$$

делится на простое число $p$. В сумме участвуют только те $k\ge 1$, которые делятся на $p-1$.

[maxal]

Рассмотрю случай $p>2$ и $p-1\nmid n$.

Нетрудно понять, что $S+1$ - это коэффициент при $x^n$ в

$$(1+x)^n (1+x^{p-1}+x^{2(p-1)}+\dots) = \frac{(1+x)^n}{1-x^{p-1}}.$$

Используя обращение Лагранжа (точнее формулу Лагранжа-Бюрмана), получаем, что $S+1$ - это коэффициет при $t^n$ в

$$f(t) = \frac{(1-t)^{p-2}}{(1-t)^{p-1} - t^{p-1}}.$$

Заметим, что

$$f(t) = \frac{(1-t)^{p-1}}{(1-t)^p - t^{p-1}(1-t)} \equiv \frac{(1-t)^{p-1}}{1-t^{p-1}} \equiv \frac{1+t+t^2+\dots+t^{p-1}}{1-t^{p-1}}\pmod{p}.$$

Учитывая, что $p-1\nmid n$, заключаем, что $S+1\equiv 1\pmod{p}$, т.е. $S\equiv 0\pmod{p}$.

Остальные случаи аналогичны.

[Руст]

Можно гораздо проще.
Запишем степени через биномиальные коэффициенты:

$$1^n=0^n+0+...+1,$$

$$2^n=1^n+\binom{n}{1}+...+1,$$

.....

$$(a+1)^n=a^n+\binom{n}{1}a^{n-1}+...+1,$$

Сложим эти равенства по а от 0 до р-1 и получим

$$p^n-p=\sum_{k=1}^{n-1}\binom{n}{k}S_k.$$

Здесь $S_k=\sum_{a=0}^{p-1}a^k=--1\mod k,$ если $p-1|k$ иначе $S_k=0\mod p$.

[maxal]

Руст в сообщении #1238416 писал(а):

Можно гораздо проще.

Это дело вкуса. Кроме того, я по сути, нашел производящую функцию чисел $S$ ($n=1,2,\dots$) при фиксированном $p$.