Равенство с биномиальными коэффициентами

[bundos]

Пусть $p$- простое. Доказать, что

$$\sum\limits_{j=0}^{p}{p\choose j}{p+j\choose j}\equiv 2^p+1 (\mod p^2)$$

[Sonic86]

Тут надо сначала перейти к сравнению по модулю $p$, воспользовавшись соотношением $\binom{2p}{p} \equiv 2 \pmod {p^2}$ (хотя на самом деле $\binom{2p}{p} \equiv 2 \pmod {p^3}$ при $p>2$). Дальше догадаетесь.

[bundos]

Блин, туплю. Никак не могу понять как из соотношения ${2p\choose p}$ перейти к сравнению по модулю $p$. $\sum\limits_{j=0}^{p}{p\choose j}{p+j\choose j}\equiv 2^p+1 (\mod p^2)\Leftrightarrow\sum\limits_{j=1}^{p-1}{p\choose j}{p+j\choose j}+{2p\choose p}\equiv 2^p (\mod p^2)$

[Sonic86]

Ну Вы знаете, что при $0<j<p$ будет $p|\binom{p}{j}$. То есть у Вас тождество вида $Kp+A \equiv B \pmod{p^2}$. При каком условии отсюда можно перейти к сравнению по модулю $p$ и как перейти, если можно? Ну по-другому: попробуйте подставить $p=5$. Ну еще малую теорему Ферма вспомните.

[bundos]

Проверил для нескольких первых простых $p|(2^p-2)$. А как это доказать для произвольльного нечётного простого? И выполняется ли это вообще?

Точно, это же малая теорема Ферма. Позабыл

-- Вт авг 02, 2011 16:46:05 --

Т.е. $\sum\limits_{j=1}^{p-1}{p\choose j}{p+j\choose j}-pD\equiv 0(\mod p^2)\Leftrightarrow -\sum\limits_{j=1}^{p-1}\frac{(-1)^j}{j}-D\equiv 0(\mod p)$, $pD=2^p-2$. Подскажите как $D$ связать с $\sum\limits_{j=1}^{p-1}\frac{(-1)^j}{j}$.

[Sonic86]

Так, а откуда у Вас в сумме $(-1)^j$ вылезло? У меня такого нету.
Вообще, у меня получилось упростить сумму справа (но не так, как Вы ). Для этого я перешел к сравнению по модулю $p$. А потом можно просто вернуться обратно, т.е. значение $D$ не понадобится. Можете просто писать $\frac{2^p-2}{p}$.

[bundos]

$\sum\limits_{j=1}^{p-1}{p\choose j}{p+j\choose j}-pD\equiv 0 (\mod p^2)\Leftrightarrow\sum\limits_{j=1}^{p-1}\frac{(p-(j-1))\ldots (p-1)}{1\cdot 2\ldots j}{p+j\choose j}-D\equiv 0(\mod p)$
Т.к. ${p+j\choose j}=\frac{(p+1)\ldots (p+j)}{1\cdot 2\ldots j}$, то ${p+j\choose j}\equiv 1(\mod p)$, а ${p\choose j}\equiv\frac{(-1)^{j-1}}{j} (\mod p)$. Разве нет?

[Sonic86]

(фигня удалена) Не трогайте 1-й коэффициент, он хороший.
Еще: теорема Вильсона: $(p-1)! \equiv -1 \pmod p$. Хотя она даже не нужна. Главное - упростить 2-й коэффициент.

[bundos]

Про упростить второй коэффициэнт Вы имели в виду ${p+j\choose j}\equiv 1(\mod p)$?

[Sonic86]

bundos в сообщении #472853 писал(а):

Ну я же сократил на $p$ и получил $\frac1{p}{p\choose j}=\frac1{p}\frac{(p-(j-1))\ldots p}{j!}=\frac{(p-(j-1)\ldots (p-1)}{j!}$

Не, я там глупость написал. Упрощайте только 2-й коэффициент.

-- Вт авг 02, 2011 13:39:37 --

bundos в сообщении #472853 писал(а):

Про упростить второй коэффициэнт Вы имели в виду ${p+j\choose j}\equiv 1(\mod p)$?

Да, конечно.

[bundos]

Всё, вроде разобрался $\sum\limits_{j=1}^{p-1}{p\choose j}{p+j\choose j}-\frac{2^p-2}{p}\equiv 0(\mod p)\Leftrightarrow\sum\limits_{j=1}^{p-1}{p\choose j}-2^p+2\equiv 0(\mod p^2)\Leftrightarrow$
$\Leftrightarrow 0\equiv 0 (\mod p^2)$.
Спасибо за помощь!

[Sonic86]

Поздравляю!

[bundos]

Помогите решить следующую задачу: Вычисить:

$$\sum\limits_{j=0}^{n}{n\choose j}2^{n-j}{j\choose [\frac{j}{2}]}$$

.

-- Вт авг 02, 2011 18:33:25 --

Подскажите, что можно с ${j\choose [\frac{j}{2}]}$ сделать?

[Sonic86]

В книге Кнута Грэхема Паташника Конкретная математика есть целый раздел, посвященный вычислению сумм с биномиальными коэффициентами. Вам может помочь прием, описанный в главке "Выполовинивание".

-- Вт авг 02, 2011 14:35:50 --

bundos в сообщении #472871 писал(а):

Подскажите, что можно с ${j\choose [\frac{j}{2}]}$ сделать?

Вот там как раз есть формула для $\frac{1}{2^n}\binom{2n}{n}$.

[bundos]

С приёмом, который в Кнуте так и не смог разобраться, к сожалению . Воспользовался другой подсказкой, что ${j\choose [\frac{j}{2}]}$- коэффициент при $x^0$ в $(x+1)(x^{-1}+x)^j$, тогда всё проходит. Получается $(x+1)\sum\limits_{j=0}^{n}{n\choose j}2^{n-j}(x^{-1}+x)^j=(x+1)(2+x^{-1}+x)^n=\frac{(x+1)^{2n+1}}{x^n}.$ Тогда искомая сумма будет равна коэффициенту при $x^0$ и равна ${2n+1\choose n}$. Поясните пожалуйста приём, который в Кнуте, если не сложно.