Утверждение 1.4

а) + + +…+ = 2 ⁿ,

б) + + +…= + + +…= 2 ^n-1

Доказательство а). Из бинома Ньютона при a = b =1

(1 + 1)ⁿ = + + +…+ .

Доказательство а) для умных, но ленивых. Сумма

+ + +…+ равна количеству всех подмножеств в множестве Х из п элементов, включая Æ и само множество Х.

Это количество можно посчитать иначе. Для выделения любого подмножества в Х мы для каждого элемента из Х должны указать, входит этот элемент в наше подмножество или нет. Таким образом, для каждого элемента имеется 2 возможности – быть включенным в любое подмножество или нет, а для п элементов из Х имеется 2 ⁿ возможностей быть включенными или нет в различные подмножества. Включая или не включая произвольный элемент в подмножества, мы получаем различные подмножества. Таким образом, количество различных подмножеств в Х равно 2 ⁿ.



Упражнение. Доказать утверждение 1.4, б) с помощью формулы бинома Ньютона при a = 1, b = - 1.

Лекция 2.