Сумма биномиальных коэффициентов $%C_n^0+C_n^1+C_n^2+..+C_n^n$% равна $%2^n$%.

Помогите, пожалуйста, доказать по индукции.

задан 22 Май '15 22:09

изменен 23 Май '15 7:59

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

@svain: У Вас пропущено первое слагаемое.

База. Для $%n=1$% очевидно.

Предполагая, что утверждение верно для $%n$%, докажем его для $%n+1$%:

$$C_{n+1}^0+C_{n+1}^1+C_{n+1}^2+...+C_{n+1}^n+C_{n+1}^{n+1}=$$ $$=C_{n+1}^0+(C_n^0+C_n^1)+(C_n^1+C_n^2)+...+(C_n^{n-1}+C_n^n)+C_{n+1}^{n+1}=$$ $$=C_n^0+(C_n^0+C_n^1)+(C_n^1+C_n^2)+...+(C_n^{n-1}+C_n^n)+C_n^n=$$ $$=2(C_n^0+C_n^1+C_n^2+...+C_n^{n-1}+C_n^n)=2\cdot2^n=2^{n+1}.$$

(22 Май '15 22:20) EdwardTurJ

Спасибо! Точно, я исправил.

(22 Май '15 22:37) svain

@svain: если ставилась задача доказательства по индукции, то, конечно, так и надо делать. Но вообще-то здесь можно этот факт доказать без вычислений: $%2^n$% есть количество всех подмножеств $%n$%-элементного множества, а сумма сочетаний означает то же самое ($%C_n^k$% есть число $%k$%-элементных подмножеств, и при этом $%k$% от $%0$% до $%n$%). Это на всякий случай.

(22 Май '15 23:10) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×3,019

задан
22 Май '15 22:09

показан
249 раз

обновлен
22 Май '15 23:10

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

по почте:

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

по RSS:

Ответы

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

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