2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Делимость суммы определенных биномиальных коэффициентов.
Сообщение02.08.2017, 08:23 
Заслуженный участник


09/02/06
4382
Москва
Доказать, что сумма биномиальных коэффициентов
$$S=\sum_{0< k< n, p-1|k} \binom{n}{k}$$
делится на простое число $p$. В сумме участвуют только те $k\ge 1$, которые делятся на $p-1$.

 Профиль  
                  
 
 Re: Делимость суммы определенных биномиальных коэффициентов.
Сообщение04.08.2017, 21:00 
Модератор
Аватара пользователя


11/01/06
5660
Рассмотрю случай $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}$.

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

 Профиль  
                  
 
 Re: Делимость суммы определенных биномиальных коэффициентов.
Сообщение04.08.2017, 21:09 
Заслуженный участник


09/02/06
4382
Москва
Можно гораздо проще.
Запишем степени через биномиальные коэффициенты:
$$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$.

 Профиль  
                  
 
 Re: Делимость суммы определенных биномиальных коэффициентов.
Сообщение04.08.2017, 21:14 
Модератор
Аватара пользователя


11/01/06
5660
Руст в сообщении #1238416 писал(а):
Можно гораздо проще.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group