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

[maxal]

Boris Skovoroda в сообщении #1704684 писал(а):

Тождество 8A. Для любых натуральных чисел $n,k,n_1,\dots,n_k$ таких, что $n_1+\dots+n_k=n$ и $k>1$, и для любого натурального числа $j$, которое меньше $k$, справедливо тождество:

$$ \sum_{m=1}^k (-1)^{k-m} \sum_{i_1,\dots,i_m}(n_{i_1}+\dots+n_{i_m})^{j}=0,$$

где внутренняя сумма вычисляется по всем неупорядоченным наборам чисел $i_1,\dots,i_m$ из множества чисел $1,\dots,k.$

Это тождество на форуме уже вылезало тут: post1143381.html#p1143381

-- Tue Oct 07, 2025 08:42:11 --

Boris Skovoroda в сообщении #1704684 писал(а):

Комбинаторное доказательство у меня оказалось значительно сложнее.

Комбинаторное доказательство не такое сложное, если заметить, что правая часть имеет вид формулы включений-исключений. С этой подсказкой ChatGPT находит такое доказательство. Я бы его подсократил раза в 2, но в целом идея правильная.

[SomePupil]

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

$$(-1)^n (n!)^2 \sum\limits_{l+m=n \atop l,m \ge 0} \frac{(2l+m)!(l+2m)!}{(l!)^5(m!)^5}\left(1+(m-l)(H_{2l+m}+2H_{m+2l}-5H_{m})\right) = \sum_{l=0}^n \binom{n}{l}^2\binom{n+l}{l}^2.$$

[Boris Skovoroda]

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

Тождество 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}.$$

Преобразуем левую часть тождества

$$\sum_{k=1}^n (-1)^{n-k}\binom{n}{k}2^k H_k =\sum_{k=1}^n (-1)^{n-k}\binom{n}{k}2^k\int\limits_{0}^{1}\frac{1-x^k}{1-x} dx= $$

$$=\int\limits_{0}^{1}\frac{(-1)^n}{1-x}\left(\sum_{k=0}^n (-1)^{k}\binom{n}{k}2^k-\sum_{k=0}^n (-1)^{k}\binom{n}{k}(2x)^k\right)dx=\int\limits_{0}^{1}\frac{(-1)^n}{1-x}\left((-1)^n-(1-2x)^n\right)dx=$$

Сделаем замену переменной: $x=1-t$

$$=\int\limits_{0}^{1}\frac{1-(1-2t)^n}{t}dt=\int\limits_{0}^{1}\sum_{k=1}^n (-1)^{k+1}\binom{n}{k}2^kt^{k-1}dt=\sum_{k=1}^n (-1)^{k+1}\binom{n}{k}\frac{2^k}{k}.$$

Следовательно, тождество 11 можно записать в следующем виде:

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

Для доказательства можно использовать метод математической индукции. Если считать, что $H_0=0,$ то тождество верно при $n=1.$ Предположим, что оно верно при некотором $n$ и докажем, что оно верно в случае, когда $n$ заменим на $n+1.$

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

$$=2H_n-H_{\lfloor n/2\rfloor}+\int\limits_{0}^{2}\sum_{k=1}^{n+1} (-1)^{k+1}\binom{n}{k-1}x^{k-1}dx=2H_n-H_{\lfloor n/2\rfloor}+\int\limits_{0}^{2}(1-x)^ndx= $$

$$=2H_n-H_{\lfloor n/2\rfloor}+\frac{(-1)^n+1}{n+1}=2H_{n+1}-H_{\lfloor( n+1)/2\rfloor}.$$

[Boris Skovoroda]

SomePupil, в тождестве 15 есть выражение: $H_{2l+m}+2H_{m+2l}$. Поскольку $H_{2l+m}=H_{m+2l}$, то появился вопрос, всё ли вы правильно написали?

[SomePupil]

Boris Skovoroda, всё правильно написал) Можно судить по значениям для малых n, которые совпадают для левых и правых частей (1, 5, 73, ...) Если хотите, могу в ЛС отправить источник,

(Оффтоп)

но тогда пропадет возможность получить удовольствие от самостоятельного доказательства этой формулы...

[Boris Skovoroda]

SomePupil в сообщении #1708715 писал(а):

Boris Skovoroda, всё правильно написал) Можно судить по значениям для малых n, которые совпадают для левых и правых частей (1, 5, 73, ...)

Не совпадают уже при $n=1, $ левая часть равна $9$, а правая равна $5$. Если вы правильно переписали тождество из "источника", то там есть опечатка.

[Boris Skovoroda]

В процессе доказательства тождества 5 придумалось тождество, которое доказывается аналогично, но проще.
Тождество 5А.

$$\sum\limits_{k=1}^{n}(-1)^{k+1}\begin{pmatrix} n+1 \\k+1\end{pmatrix}H_k=H_n,\;n\in\mathbb{N}.$$