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

[maxal]

Докажите, что для всяких целых неотрицательных $n$ справедливо тождество:

Тождество 1:

$$\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}$$

[maxal]

Тождество 2:

$$\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose k} \left[ {n\choose k} { 2n+1-2k\choose n+2} + {n\choose k+1} {2n-2k\choose n+2}\right] = \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} {2k\choose k} {n+k\choose k+1} 2^{n-1-2k}$$

[maxal]

Докажите, что для всяких целых неотрицательных $m,n$ справедливо

Тождество 3:

$${}_3F_2(-m,-n,m+n; 1, 1; 1) = \frac{m^2+n^2+mn}{(m+n)^2}\binom{m+n}{m}^2.$$

(см. тут)

[maxal]

Докажите, что для всех натуральных $n$ справедливо

Тождество 4:

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

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

[Yu_K]

Правая часть тождества 3 есть в этом топике http://dxdy.ru/topic17192.html - а что такое стоит в левой части?

[maxal]

Yu_K в сообщении #333726 писал(а):

Правая часть тождества 3 есть в этом топике topic17192.html - а что такое стоит в левой части?

Да, ноги у Тождества 3 растут из той самой задачи. В левой части тождества стоит так называемая гипергеометрическая функция.

[caxap]

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

Тождество 4:

А можно получить небольшую подсказку? Я пробовал и пределы менять и суммирование по частям -- ничего не помогает.
P.S. Остальные тождества уже очень стары, может опубликуете решения? Интересно бы было посмотреть

[maxal]

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}$$

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

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

[caxap]

(Оффтоп)

maxal, а Вами предполагается вообще опубликовать решения, если их никто не решит? Например первые 3 тождества уже 2 года висят.

[maxal]

caxap в сообщении #335830 писал(а):

maxal, а Вами предполагается вообще опубликовать решения, если их никто не решит? Например первые 3 тождества уже 2 года висят.

Вообще-то я с первого раза вопросы понимаю. Хотел на досуге поискать свои доказательства (доказывать заново нет времени), но раз уж вы такой нетерпеливый - то вот вам вместо доказательств подсказка: вычислите значения выражений для несколький последовательных значений $n$ и найдите по ним соответствующие последовательности в OEIS - там должна быть полезная информация.

[maxal]

Тождество 5.

$$ \sum_{k=1}^{n} (-1)^k{n\choose k}{n+k\choose n}(H_{n+k}-H_n)=(-1)^nH_n. $$

(источник)

[maxal]

Тождество 6.

$$\frac1n\sum_{k=0}^{n-1}\frac1{\binom{n-1}k}=\sum_{k=1}^n\frac1{k 2^{n-k}}.$$

(источник)

[maxal]

Тождество 7.

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

(источник)

[maxal]

Тождество 8. Докажите, что для всех целых (неотрицательных) $n,k$ справедливо тождество:

$$S(n,k) = \sum_{j=k}^n (-1)^{j-k}\cdot \binom{n}{j}\cdot S(j,k)\cdot k^{n-j},$$

где $S(\cdot,\cdot)$ -- числа Стирлинга 2-го рода.

По возможности дайте комбинаторное доказательство.

[maxal]

Тождество 9.

$$\sum_{i=0}^{n}{ \sum_{j=0}^{m}{ \left(-1 \right)^{\left\lfloor\tfrac{i}{2}\right\rfloor+j}2^{n-i}\binom{n-\left\lceil \frac{i}{2} \right\rceil}{j}\binom{n-\left\lceil \frac{i}{2} \right\rceil-j}{\left\lfloor \frac{i}{2} \right\rfloor}\binom{i}{m-j}}} = \left(-1 \right)^{m} \binom{2n+1}{2m+1}.$$

(источник)