Как доказать, что $%C^1_n+2C^2_n+3^3_n+...+nC^n_n=2^{n-1}n$%? Пожалуйста, без дифференцирования бинома.

задан 19 Мар '18 22:51

10|600 символов нужно символов осталось
2

Используйте следующее соображение: $$kC_n^k=\frac{n!\cdot k}{(n-k)!\cdot k!}=\frac{n!}{(n-k)!\cdot (k-1)!}=\frac{n\cdot (n-1)!}{(n-k)!\cdot (k-1)!}=nC_{n-1}^{k-1}.$$

И, разумеется, бином Ньютона:

$$C_m^0+C_m^1+\ldots+C_m^{m-1}+C_m^m=2^m$$ - для $%m=n-1$%.

ссылка

отвечен 19 Мар '18 23:43

изменен 19 Мар '18 23:45

Да $%kC_n^k=nC_{n-1}^{k-1}$% поучительное соотношение. Фактически это доказательство повторяет комбинаторные рассуждения falcao только языком формул

(20 Мар '18 14:21) abc
10|600 символов нужно символов осталось
2

Есть чисто комбинаторное доказательство, вообще без формул. Оно где-то на форуме уже могло встречаться, но ссылку трудно найти.

Будем рассматривать непустые подмножества множества {1,2,...,n}, в которых один из элементов отмечен. Если подмножество k-элементно, то отметить его элемент можно k способами, а само оно выбирается C_n^k способами. Суммирование по 1<=k<=n даёт выражение в левой части.

Теперь то же подсчитаем другим способом. Выбрать тот элемент, который мы хотим видеть в качестве отмеченного, можно n способами. Далее к нему добираем произаольное подмножество, формируемое из оставшихся n-1 элементов, что можно сделать 2^{n-1} способами. Это даёт выражение из правой части.

ссылка

отвечен 20 Мар '18 0:10

Интересно, а у формулы суммы г.п. есть аналогичное доказательство, вообще без формул?

(20 Мар '18 14:36) abc

@abc: для какого случая? Прогрессия конечная или бесконечная? Каков её знаменатель? Я думаю, что комбинаторное (или вероятностное) доказательство такого рода должно найтись.

(20 Мар '18 17:37) falcao

Прогрессия конечная. Для начала знаменатель натуральный, а там посмотрим

(20 Мар '18 20:16) abc
1

@abc: для тождества $%1+2+\cdots+2^n=2^{n+1}-1$% всё просто. Рассмотрим пример $%1+3+\cdots+3^n=\frac{3^{n+1}-1}2$%. Рассматриваем слова над алфавитом $%\{a,b,c\}$% длиной $%n+1$%, за исключением одного -- степени $%a$%. Их $%3^{n+1}-1$%. В каждом таком слове рассмотрим первое слева вхождение буквы $%b$% или $%c$%. После него идёт слово длиной $%0\le k\le n$%; оно произвольно. Перед ним -- степень $%a$%. Два способа выбора буквы, и $%3^k$% способов выбора слова. Далее суммируем по $%k$%.

(20 Мар '18 22:08) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,300

задан
19 Мар '18 22:51

показан
2789 раз

обновлен
20 Мар '18 22:08

Отслеживать вопрос

по почте:

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

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru