OLK
Новичок
|
   
Помогите доказать тождество:
Сn0 +1/2 *Cn1 +… + 1/(n+1)* Cnn = (2^(n+1) – 1)/(n+1), где
Сn0 - число сочетаний из n по 0
Cn1 - число сочетаний из n по 1 и т.д.
Пыталась использовать все известные мне соотношения, как то: Сn0=1, Cn1=n, Cnn=1, Cn0 + Cn1 +...+Cnn =2^n, но ничего не получается... Подскажите, с чего начать.
|
Всего сообщений: 2 | Присоединился: май 2007 | Отправлено: 7 мая 2007 12:56 | IP
|
|
niko
Новичок
|
   
исползуя метода индукции
проверая n=1
допуская правильность n=k
и доказат для n=k+1
|
Всего сообщений: 16 | Присоединился: январь 2006 | Отправлено: 7 мая 2007 13:31 | IP
|
|
MEHT
Долгожитель
|
Вместо Сnk обозначу биноминальные коэффициенты через C(n;k).
Левая часть.
С(n;0) +1/2 *C(n;1) +...+ 1/(n+1)* C(n;n) =
= sum {C(n;k)/(k+1)} - суммирование по k = 0,1,2,...,n.
Но
C(n;k) = n!/[k! * (n-k)!], значит
sum {C(n;k)/(k+1)} = sum {n!/[(k+1)! * (n-k)!]} =
= [1/(n+1)] * sum {(n+1)!/[(k+1)! * (n-k)!]} =
= [1/(n+1)] * sum {C(n+1;k+1).
Правая часть.
Распишем 2^(n+1) по формуле бинома Ньютона, т.е.
2^(n+1) = (1+1)^(n+1) = 1 + C(n+1;1) + C(n+1;2) +...+ C(n+1;n+1) =
= 1 + sum {C(n+1;k+1)} - суммирование по k = 0,1,2,...,n.
Подставляя это выражение для 2^(n+1) в правую часть, получим
(2^(n+1) – 1)/(n+1) = [1/(n+1)] * sum {C(n+1;k+1).
Таким образом левая и правая части совпадают.
|
Всего сообщений: 1548 | Присоединился: июнь 2005 | Отправлено: 7 мая 2007 14:51 | IP
|
|
MEHT
Долгожитель
|
Существующая тема: Комбинаторика и множества
|
Всего сообщений: 1548 | Присоединился: июнь 2005 | Отправлено: 7 мая 2007 14:52 | IP
|
|
|
Форум
Задача по комбинаторике
