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

[Whitaker]

Здравствуйте!
Возникла такая подзадача в решении одной комбинаторной задачи.
Нужно упростить такую сумму:
$C_{k}^{k}+C_{k+1}^{k}+C_{k+2}^{k+}+...+C_{n}^{k}$.
Наверное это можно сделать производящими функциями, но пока с производящими функциями я не имел дело.
А есть ли какой-нибудь другой способ?

С уважением, Whitaker.

[ИСН]

А посмотреть на них в треугольнике Паскаля? А виртуально добавить к верхнему ещё один, стоящий в строке рядом с ним - может, всё свернётся?

[Sonic86]

Если не сможете - ответ есть в Кнуте в Конкретной математике.
Я не знаю как советовать решать подобные задачи. Можете попробовать вычислить сумму для $n=k;k+1,k+2$, потом попытаться увидеть закономерность.

[Whitaker]

У меня была следующая мысль, но реализовать я ее не смог.
Раскроем следующие выражения используя Бином Ньютона.
$(1+x)^k=....+x^kC_{k}^{k}$
$(1+x)^{k+1}=....+x^kC_{k+1}^{k}+..$
$(1+x)^{k+2}=....+x^kC_{k+2}^{k}+..$
......
$(1+x)^n=....+x^kC_{n}^{k}+..$
Суммируя эту систему получим:
$(1+x)^k+(1+x)^{k+1}+..+(1+x)^n=..+x^k \Big(C_{k}^{k}+C_{k+1}^{k}+....+C_{n}^{k} \Big)+...$
Мы видим, что коэффициент перед $x^k$ есть и интересующая нас сумма.

-- Вт сен 20, 2011 20:46:20 --

Да ответ я сам знаю уже он равен по-моему $C_{n+1}^{k}$, но хотелось бы ее вывести.

[ИСН]

Я что-то слишком простое сказал или слишком сложное?

[Joker_vD]

А еще есть такая штука как тождество Вандермонда:

$$C_{m+n}^{r} = \sum\limits_{i=0}^r C_{m}^{r-i} C_{n}^{i}.$$

[Whitaker]

Нужно найти сумму $(1+x)^k+(1+x)^{k+1}+...+(1+x)^n$ используя формулу геометрической прогрессии. Нам необходимо найти коэффициент при $x^{k+1}$ в данной сумме. Потому что там в знаменателе возникает $x$, поэтому нобходимо найти кэф при $x^{k+1}$.
Надеюсь то, что я написал верно.
Сейчас сам проверю на бумажке

-- Вт сен 20, 2011 21:21:48 --

У меня в ответе получилось $C_{n+1}^{k+1}$

[PAV]

Можно и чисто из комбинаторных соображений получить, практически аналогично тому, как было в одной из прошлых тем.

[Whitaker]

Да Да PAV! Согласен это наиболее легче. К тому же чисто комбинаторное доказательство. Но к сожалению не догадался до такого

-- Вт сен 20, 2011 21:45:53 --

Также Благодарен Вам ИСН за красивое решение

-- Вт сен 20, 2011 21:46:43 --

А мой способ решения по-моему не совсем хороший