комбинаторные тождества

[maxal]

Тождество 10. Для целых чисел $n>m\geq 0$ докажите, что

$$\sum_{k=0}^n (-1)^k\binom{2n+1}{n-k} (2k+1)^{2m+1} = 0.$$

[iifat]

А кто есть $m$? Произвольное число?

[grizzly]

iifat в сообщении #1319522 писал(а):

А кто есть $m$? Произвольное число?

Думаю, что целое неотрицательное. Исхожу из этого:

maxal в сообщении #1319484 писал(а):

Для целых чисел $n>m\geq 0$

[maxal]

maxal в сообщении #333354 писал(а):

Тождество 4:

$$\sum_{k=1}^n \binom{n}{k}^2 H_k = \binom{2n}{n}(2H_n-H_{2n}),$$

где $H_m$ - гармонические числа.

С виду кажется очень похожим:

Тождество 11. Для $n\geq 1$, докажите:

$$\sum_{k=1}^n (-1)^{n-k}\binom{n}{k}2^k H_k = 2H_n-H_{\lfloor n/2\rfloor}.$$

(Crux Mathematicorum, problem 3886)

[kotenok gav]

maxal в сообщении #334374 писал(а):

caxap
Подсказка для 4-го:

$$H_k = \int_0^1 \frac{1-x^k}{1-x}\,dx$$

Полезно также вспомнить доказательство тождества:

$$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$$

и попробовать его скомбинировать с вышеприведённым интегралом.

Полное решение доступно по ссылке.

А откуда у вас появляется y?

[maxal]

kotenok gav в сообщении #1320066 писал(а):

А откуда у вас появляется y?

Как появляется, так и исчезает - через оператор $[y^n]$ взятия коэффициента при $y^n$.

[maxal]

Тождество 12. Для всякого целого $n>0$ докажите, что

$$\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k} \frac{2n-3k}{n-k} 2^k = 2^n.$$

[Farest2]

Заметим, что $2n-3k=(n-k)+(n-2k)$. (Кстати, Mathematica этого не замечает и выдает в качестве ответа гигантскую простыню ${}_4F_3$ функций.) Поэтому исходная сумма приводится к виду

$$ a_n\stackrel{\rm def}{=} \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}\frac{2n-3k}{n-k}\,2^k =\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}\,2^k +\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-1-k}{k}\,2^k. $$

Поскольку и исходная сумма, и получившиеся слагаемые являются naturally terminating (не знаю, как благозвучно перевести на русский), то можно суммирование делать по всем целым $k$, а биномиальные коэффициенты сами выберут "своих".

Зная ответ, к исходному равенству можно добавить и случай $a_0=1$, т.е. при $n=0$ трактовать неопределённую дробь как

$$ \frac{2n-3k}{n-k}=\frac{2n-3\cdot\tfrac{n}{2}}{n-\tfrac{n}{2}}=1. $$

Пусть теперь

$$ \lambda_n(x)\stackrel{\rm def}{=} \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}\,x^k, $$

т.е. $a_n=\lambda_n(2)+\lambda_{n-1}(2)$.

В принципе, если вспомнить полиномы Чебышёва второго рода

$$ U_n(x)=\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k\binom{n-k}{k}(2x)^{n-2k} $$

и их производящую функцию

$$ \sum_{n=0}^\infty U_n(x)z^n=\frac{1}{1-2xz+z^2}, $$

то всё легко находится:

$$ \begin{gathered} U_n(x)=(2x)^n \lambda_n\Bigl(-\frac{1}{4x^2}\Bigr)\quad\Rightarrow\quad \lambda_n(x)=\Bigl(\frac{\sqrt x}{i}\Bigr)^n U_n\Bigl(\frac{i}{2\sqrt x}\Bigr),\\ \sum_{n=0}^\infty \lambda_n(x)z^n=\sum_{n=0}^\infty U_n\Bigl(\frac{i}{2\sqrt x}\Bigr)\Bigl(\frac{z\sqrt x}{i}\Bigr)^n =\frac{1}{1-z-xz^2},\\ \sum_{n=0}^\infty a_n z^n =\sum_{n=0}^\infty \bigl\{\lambda_n(2)+\lambda_{n-1}(2)\bigr\} z^n =\frac{1+z}{1-z-2z^2}=\frac{1}{1-2z}\quad\Rightarrow\quad a_n=2^n. \end{gathered} $$

Мне, однако, больше нравится подход, когда заранее ничего не надо знать:

$$ \begin{gathered} \sum_{n=0}^\infty \lambda_n(x)z^n =\sum_{\delta=0,1}\sum_{n=0}^\infty \lambda_{2n+\delta}(x)z^{2n+\delta} =\sum_{\delta=0,1}\sum_{n=0}^\infty z^{2n+\delta} \sum_{k=0}^n \binom{2n+\delta-k}{k}\,x^k={}\\ {}=\sum_{\delta=0,1}\sum_{k=0}^\infty \sum_{n=k}^\infty z^{2n+\delta}\binom{2n+\delta-k}{k}\,x^k =\sum_{\delta=0,1}\sum_{k=0}^\infty \sum_{n=0}^\infty z^{2n+2k+\delta}\binom{2n+\delta+k}{k}\,x^k={}\\ {}=\sum_{n=0}^\infty \sum_{k=0}^\infty z^{n+2k}\binom{n+k}{k}\,x^k =\sum_{n=0}^\infty z^n\sum_{k=0}^\infty \binom{n+k}{k}(xz^2)^k={}\\ {}=\sum_{n=0}^\infty \frac{z^n}{(1-xz^2)^{n+1}} =\frac{1}{(1-xz^2)\Bigl(1-\dfrac{z}{1-xz^2}\Bigr)}=\frac{1}{1-z-xz^2}. \end{gathered} $$

Теперь вычисляем $\lambda_n(x)$ через обратные корни полинома в знаменателе:

$$ \lambda_n(x)=[z^n]\frac{1}{1-z-xz^2}=[z^n]\frac{1}{(1-z_1z)(1-z_2z)} =\frac{1}{z_1-z_2}[z^n]\Bigl\{\frac{z_1}{1-z_1z}-\frac{z_2}{1-z_2z}\Bigr\} =\frac{z_1^{n+1}-z_2^{n+1}}{z_1-z_2}. $$

При $x=2$ корни полинома $1-z-xz^2$ -- это $\tfrac12$ и $-1$, поэтому обратные корни -- это $z_1=2$ и $z_2=-1$. Ну и дальше всё очевидно.

[maxal]

Farest2, похоже на правду. У меня тождество 12 вылезло из этой задачки, где оно получается подстановкой $x=1$.

[12d3]

Что-то тождества мало поддаются народу. Попробую использовать для доказательства такой подход: придумать комбинаторную задачу, в которой ответ можно посчитать двумя способами, одним способом получится левая часть тождества, другим способом - правая.

maxal в сообщении #120593 писал(а):

$$\sum_{k=0}^{2n} {n\choose k} {4n-2k\choose 2n-k} (-3)^k = \sum_{k=0}^{\lfloor 2n/3\rfloor} {n\choose k}{n\choose 2n-3k}$$

Рассмотрим таблички из 4 строк и $n$ столбцов, в клетках которых стоят 0 либо 1, и количество нулей равно количеству единиц. Назовем столбец хорошим, если в первых трех клетках стоят одинаковые числа, либо три нуля, либо три единицы. Задача: сколько существует таких табличек, в которых все столбцы хорошие?
Решим эту задачу первым способом. Для начала маленькая подзадача: найдем, сколько существует табличек, в которых первые $k$ столбцов - нехорошие. В каждом нехорошем столбце в верхних трех элементах обязательно есть ровно 1 нолик, ниже которого расположена единичка, причем мы считаем, что после третьей строчки идет первая. Например, в столбце $(1,0,1,0)$ после нолика на втором месте идет единичка на третьем месте, а в столбце $(1,1,0,1)$ мы считаем, что после нолика на третьем месте идет единичка на первом месте. Если мы выберем положение такого нолика одним из трех способов, то это автоматически определяет, что в клетке ниже (в упомянутом ранее смысле) стоит единичка, а остальные две клетки в столбце могут быть какими угодно. Так вот, если мы в каждом из $k$ нехороших столбцов выберем положение такого нолика одним из трех способов, то во всей табличке будет зафиксировано содержимое $2k$ клеток, в которых будет $k$ ноликов и $k$ единичек. Остается в остальных $4n-2k$ клетках расположить поровну ноликов и единичек. Т.е. ответом к этой маленькой подзадаче будет $\displaystyle {3^k \cdot {4n-2k \choose 2n-k}$. А теперь вернемся к нашей основной задаче. Количество табличек только с хорошими столбцами по формуле включений и исключений равно $\displaystyle {4n \choose 2n} - 3 {n\choose 1}{4n-2 \choose 2n-1}+ 3^2 {n\choose 2}{4n-4 \choose 2n-2} - \dots = \sum_{k=0}^{n} {n\choose k} {4n-2k\choose 2n-k} (-3)^k$. Получили левую часть тождества.
Теперь решим задачу вторым способом. Рассматривать будем только таблички с хорошими столбцами. Пусть у нас $k$ столбцов, в которых на первых трех местах стоят единички. Значит, среди первых трех строк будет $3k$ единичек и $3n-3k$ ноликов. Поскольку всего в таблице $2n$ единичек, то в нижней строчке должно быть $2n-3k$ единичек. Мы можем выбрать независимо $k$ столбцов с единицами на первых трех местах и $2n-3k$ столбцов с единицами на последнем месте. Итого, у нас получится, что количество таблиц со всеми хорошими столбцами равно $\displaystyle \sum_{k=0}^{n} {n\choose k}{n\choose 2n-3k}$. Вот и правая часть тождества.
Кстати, у этой задачи с табличками есть эквивалентная, более короткая формулировка: чему равно количество последовательностей длины $n$, элементы которой принадлежат множеству $\{-2,-1,1,2\}$, и у которой сумма элементов равна нулю.

[maxal]

12d3 в сообщении #1466051 писал(а):

Кстати, у этой задачи с табличками есть эквивалентная, более короткая формулировка: чему равно количество последовательностей длины $n$, элементы которой принадлежат множеству $\{-2,-1,1,2\}$, и у которой сумма элементов равна нулю.

Да, тождество 1 происходит из последовательности A092765, для которой есть несколько разных методов подсчёта (и формул).