2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Доказательство комбинаторной формулы
Сообщение17.11.2012, 15:35 
Аватара пользователя
Помогите доказать или скиньте ссылку на сайт, где это доказывается
$C_n^k=C_{n-1}^{k-1}+C_{n-2}^{k-1}+...+C_{k-1}^{k-1}=\sum_{i=0}^{n-k}C_{k+i-1}^{k-1}$

UPD:
$C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k}$
Отсюда: $C_{n-1}^{k}=C_{n-2}^{k-1}+...+C_{k-1}^{k-1}$
Опять же: $C_{n-1}^{k} = C_{n-2}^{k-1} + C_{n-2}^{k}$ и $C_{n-2}^{k}=C_{n-3}^{k-1}+...+C_{k-1}^{k-1}$

Спасибо за эту подсказку, как последовательно перейти из одного к другому я понял. Но количество таких переходов условно бесконечно. Подскажите как сформулировать это? Просто написать "И так далее" или как-то через индукцию?

 
 
 
 Re: Доказательство комбинаторной формулы
Сообщение17.11.2012, 16:01 
Подсказка: $C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$.

 
 
 
 Re: Доказательство комбинаторной формулы
Сообщение17.11.2012, 16:09 
Аватара пользователя
Я пытался применить, но не смог выдавить из этого пользу(

 
 
 
 Re: Доказательство комбинаторной формулы
Сообщение17.11.2012, 16:20 
Аватара пользователя
$C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k}$
А из этой выдавите? (Первое слагаемое справа уже какое надо, поэтому его не трогайте, а давите на второе слагаемое.)

Или сравните коэффициенты перед $x^k$ справа и слева
$$\left[(x+1)^n -1\right]=\left[(x+1) -1\right]\cdot\left[(x+1)^{n-1}+(x+1)^{n-2}+ \cdots + (x+1)^{2}+(x+1)-1\right]$$

 
 
 
 Re: Доказательство комбинаторной формулы
Сообщение17.11.2012, 17:11 
Аватара пользователя
 i  Тема перемещена в Карантин.

1. Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

2. Подсказали Вам достаточно, теперь приведите свои попытки решения задачи.

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено.

 
 
 
 Posted automatically
Сообщение17.11.2012, 23:28 
Аватара пользователя
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: та вроде культурненько всё...

 
 
 
 Re: Доказательство комбинаторной формулы
Сообщение17.11.2012, 23:40 
А биномом Ньютона тут нельзя воспользоваться?..

 
 
 
 Re: Доказательство комбинаторной формулы
Сообщение17.11.2012, 23:44 
Аватара пользователя
Хотелось бы доказать именно так, как уже подсказали. Но интересует вопрос как описать именно то бесконечное количество переходов? Индуктивностью? Или достаточным будет сказать, что "продолжая размышлять таким образом придем к окончательному ответу"?

 
 
 
 Re: Доказательство комбинаторной формулы
Сообщение18.11.2012, 08:32 
nulpatrol в сообщении #645813 писал(а):
Но интересует вопрос как описать именно то бесконечное количество переходов?
Оно не бесконечное, а конечное, потому индукции достаточно. Хотя, конечно, неограниченное.

 
 
 
 Re: Доказательство комбинаторной формулы
Сообщение18.11.2012, 15:33 
nulpatrol в сообщении #645813 писал(а):
Или достаточным будет сказать, что "продолжая размышлять таким образом придем к окончательному ответу"?
Ну, это пишут, когда лень расписывать доказательство по индукции, когда она достаточно очевидна. Если здесь вы сразу видите, как надо доказывать по индукции, и верите, что проверяющему задание такого убеждения хватит, то можно написать это.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group