alt text

задан 7 Окт '17 13:13

Можно поинтересоваться, откуда задание?

(7 Окт '17 16:38) Williams Wol...
10|600 символов нужно символов осталось
1

Суммы вида $%C_n^0+C_n^2+\cdots$% легко вычисляются: при всех $%n\ge1$% они составляют половину от общей суммы биномиальных коэффициентов, равной $%2^n$%, то есть сумма равна $%2^{n-1}$%, а её двоичный логарифм равен $%n-1$%.

Одно из доказательств чисто комбинаторное: речь идёт о количестве подмножеств $%n$%-элементного множества с чётным числом элементов. Их столько же, сколько подмножеств с нечётным числом элементов. Действительно, можно зафиксировать элемент $%a$%, и установить биекцию между множествами одного и другого типа. Она устроена просто: если элемент $%a$% принадлежит подмножеству, то его удаляем, а если не принадлежит, то добавляем. Всего подмножеств у нас $%2^n$%, поэтому тех и других будет поровну, то есть по $%2^{n-1}$%.

Второе доказательство -- при помощи биномиальной формулы. С одной стороны, $%2^n=(1+1)^n=C_n^0+C_n^1+C_n^2+C_n^3+\cdots$%. С другой стороны, $%0=(1-1)^n=C_n^0-C_n^1+C_n^2-C_n^3+\cdots$%. Складывая, имеем удвоенную сумму из условия, находящуюся под знаком логарифма.

ссылка

отвечен 7 Окт '17 16:37

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×250

задан
7 Окт '17 13:13

показан
332 раза

обновлен
7 Окт '17 16:38

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

по почте:

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

по RSS:

Ответы

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

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