Сумма биномиальных коэффициентов

[DLL]

Добрый день. Не соображу как посчитать эту сумму:

$$\sum\limits_{k = 0}^d {C_{d + n - 1 - k}^{n - 1} } $$

По логике должно получиться нечто типа:

$$C_{d + n}^n $$

.

[R_e_n]

$ \sum_{k=0}^d C_{d + n - 1 - k}^{n - 1} = \sum_{k=0}^d C_{n - 1 + k}^{n - 1} $ - просто меняется порядок суммирования. А дальше я пока не придумал)

[TOTAL]

$C_{d + n - 1 - k}^{n - 1}$ - это коэффициент при $x^{n-1}$ в $(1+x)^{d+n-1-k}.$ Дальше очевидно.

[R_e_n]

R_e_n в сообщении #704776 писал(а):

$ \sum_{k=0}^d C_{d + n - 1 - k}^{n - 1} = \sum_{k=0}^d C_{n - 1 + k}^{n - 1} $ - просто меняется порядок суммирования. А дальше я пока не придумал)

О, я дальше подсмотрел как надо. Вот тут http://e-maxx.ru/algo/binomial_coeff свойство "Суммирование по n" правда оно там без доказательства.

$ \sum_{k=0}^d C_{d + n - 1 - k}^{n - 1} = \sum_{k=0}^d C_{n - 1 + k}^{n - 1} = \sum_{k=n-1}^{d+n-1} C_{k}^{n - 1} = \sum_{k=0}^{d+n-1} C_{k}^{n - 1} - \sum_{k=0}^{n-2} C_{k}^{n - 1} = C_{d+n}^{n} - C_{n-1}^{n} $

И все бы хорошо, но как считать вот это $ C_{n-1}^{n} = \frac{(n-1)!}{n! \cdot(-1)!} $ я не знаю. Наверное люди как то считают раз вывели формулу суммирования по n.

А вообще моё решение попахивает бредом, с радостью узнаю, где я ошибся:)

[Руст]

Еще проще, если представить
$C_{d+n-1-k}^{n-1}=C_{d+n-k}^n-C_{d+n-1-k}^n$.

[R_e_n]

А может кто-нибудь представить полное решение? А то мне обе идеи решения не понятны. Хочу заметить, что суммирование предполагается по нижнему индексу и суммируется до d, а не до n какого-нибудь, как в биноме Ньютона

[TOTAL]

R_e_n в сообщении #704827 писал(а):

А может кто-нибудь представить полное решение?

$$(1+x)^{n-1}+ \cdots +(1+x)^{n-1+d}$$

Найдите коэффициент при $x^{n-1}$ в сумме этой геометрической прогрессии.

[DLL]

R_e_n в сообщении #704809 писал(а):

И все бы хорошо, но как считать вот это $ C_{n-1}^{n} = \frac{(n-1)!}{n! \cdot(-1)!} $ я не знаю. Наверное люди как то считают раз вывели формулу суммирования по n.

А вообще моё решение попахивает бредом, с радостью узнаю, где я ошибся:)

Не смотрел полностью. Но там должно быть одно слагаемое, где возникает формальная запись (-1)!.
Просто это слагаемое надо было исключить предварительно из суммирование и не пользоваться формулой.

[R_e_n]

TOTAL в сообщении #705073 писал(а):

R_e_n в сообщении #704827 писал(а):

А может кто-нибудь представить полное решение?

$$(1+x)^{n-1}+ \cdots +(1+x)^{n-1+d}$$

Найдите коэффициент при $x^{n-1}$ в сумме этой геометрической прогрессии.

$(1+x)^{n-1}=\sum_{i=0}^{n-1}{C_{n-1}^ix^i}=\sum_{i=0}^{n-2}C_{n-1}^ix^i+C_{n-1}^{n-1}x^{n-1}=(1+x)^{n-1}$
$(1+x)^{n-1+1}=\sum_{i=0}^{n-1+1}{C_{n-1+1}^ix^i}=\sum_{i=0}^{n-2}C_{n-1+1}^ix^i+C_{n-1+1}^{n-1}x^{n-1}+C_{n-1+1}^{n-1+1}x^{n-1+1}=(1+x)^{n-1+1}$
...............................................................................................
$(1+x)^{n-1+d}=\sum_{i=0}^{n-1+d}C_{n-1+d}^ix^i=\sum_{i=0}^{n-2}C_{n-1+d}^ix^i+C_{n-1+d}^{n-1}x^{n-1}+\sum_{i=n-1+1}^{n-1+d}C_{n-1+d}^ix^i=(1+x)^{n-1+d}$

Откуда
$C_{n-1}^{n-1}x^{n-1}=(1+x)^{n-1}-\sum_{i=0}^{n-2}C_{n-1}^ix^i$

$C_{n-1+1}^{n-1}x^{n-1}=(1+x)^{n-1+1}-\sum_{i=0}^{n-2}C_{n-1+1}^ix^i-C_{n-1+1}^{n-1+1}x^{n-1+1}$
...............................................................................................
$C_{n-1+d}^{n-1}x^{n-1}=(1+x)^{n-1+d}-\sum_{i=0}^{n-2}C_{n-1+d}^ix^i-\sum_{i=n-1+1}^{n-1+d}C_{n-1+d}^ix^i$

При x=1
$C_{n-1}^{n-1}=2^{n-1}-\sum_{i=0}^{n-2}C_{n-1}^i$
$C_{n-1+1}^{n-1}=2^{n-1+1}-\sum_{i=0}^{n-2}C_{n-1+1}^i-C_{n-1+1}^{n-1+1}$
...............................................................................................
$C_{n-1+d}^{n-1}=2^{n-1+d}-\sum_{i=0}^{n-2}C_{n-1+d}^i-\sum_{i=n-1+1}^{n-1+d}C_{n-1+d}^i$

Суммируем
$\sum_{i=0}^dC_{n-1+i}^{n-1}=\frac{(2^{n-1}+2^{n-1+d})}2(d+1)-\sum_{j=0}^d\sum_{i=0}^{n-2}C_{n-1+j}^i-\sum_{j=0}^d\sum_{i=n-1+1+j}^{n-1+d}C_{n-1+j}^i$

Фух, вроде бы нигде не ошибся. А дальше что? :)

[TOTAL]

R_e_n в сообщении #705855 писал(а):

Фух, вроде бы нигде не ошибся. А дальше что? :)

Дальше не надо. Теперь садитесь в самолет и летите из того места, куда успели забраться, снова на старт.
Сначала найдите сумму геометрической прогрессии.

[Руст]

Почему не используете то, что я вам подсказал. При $k=0$ получаем первый член $C_{n+d}^n$ и второй член $-C_{n+d-1}^n$, далее он сокращается первым для $k=1$, а второй член для $k=1$ сокращается с первым для $k=2$ и т.д. Остается только самый первый, т.е. $C_{n+d}^n$.