Пара задачек на комбинаторику...

[Jurec]

Короче пристал ко мне препод по дискретной математике с этими двумя задачками(решить надо одну из двух) и другие давать не хочет на зачет...
На зачете решал часов 5 - 6 наверно и еще дома, нихрена не решается. Однокурсники тож ничем помочь не могут(((

Буду очень благодарен, если хотя бы идеи к решению подскажите. А еще лучше все решение)))
Заранее Спасибо!

[RIP]

Если сгодится любое решение, то задачи становятся простыми, если воспользоваться равенством

$$\frac1{\binom nk}=(n+1)\int\limits_0^1x^k(1-x)^{n-k}dx$$

Это позволяет избавиться от биномиального коэффициента в знаменателе.
Равенство доказывается так

$$\int\limits_0^1x^k(1-x)^{n-k}dx=B(k+1,n-k+1)=\frac{\Gamma(k+1)\Gamma(n-k+1)}{\Gamma(n+2)}=\frac{k!(n-k)!}{(n+1)!}=\frac1{(n+1)\binom nk}$$

$B(p,q),\Gamma(s)$ - Эйлеровы интегралы первого и второго рода.

[Jurec]

а откуда такое равенство, если не секрет?
и все таки до конца не понятно, чем оно становится проще? и че дальше делать с этим интегралом?

[RIP]

Дальше можно поменять местами суммирование и интегрирование и свести к биному Ньютона.

Добавлено спустя 21 минуту 34 секунды:

Второй пример можно решить и вот так:
Преобразовать

$$\frac{\binom{n-1}{i-1}}{\binom{2n-1}i}=\frac{(n-1)!}{(2n-1)!}\cdot\frac{i(2n-1-i)!}{(n-i)!}$$

Если теперь сделать замену переменной суммирования $i=n-k$, то сумма сведется к паре простых вида

$$\sum_{k=0}^m\binom{n+k}n=\binom{n+m+1}m$$

Это легко доказать, например, индукцией по $m$.
Думаю, что первый пример можно сделать аналогично, но лень проверять. Тем более, что достаточно решить один пример.

[Jurec]

Спасибо большое!
Я уже все разрюхал через первую формулу....
Но второе решение больше подходит.

Еще раз огромное спасибо!

З.Ы. Можно закрывать.