Апология математики (сборник статей)

Постараемся доказать равенство (*) как можно нагляднее. Возьмём множество M, имеющее 2n элементов, произвольно отберём из него n элементов и назовём их «белыми»; остальные n элементов назовём «чёрными». Каждое подмножество K множества M, содержащее n элементов, есть объединение двух частей – «белой» части A, состоящей только из «белых» элементов, и «чёрной» части B, состоящей только из «чёрных» элементов: K = A ∪ B. Число элементов в каждой из этих частей может варьироваться от 0 до n. Приготовим n + 1 «комнату», на которых выставим номера от 0 до n. Все подмножества мощности n множества M распределим по этим «комнатам», соблюдая следующее правило: в «комнату» с номером k помещаются те подмножества, число «белых» элементов в которых равно k. В каждой «комнате» поставим «столов» и подмножества, попавшие в эту «комнату», распределим по этим «столам». Число «белых» подмножеств мощности k множества M, т. е. подмножеств, содержащих k «белых» элементов и ноль «чёрных», равно т. е. числу «столов». Для каждого такого «белого» подмножества взаимно однозначно выберем свой «стол». На этом «столе» располагаются подмножества мощности n множества M, у которых «белая» часть уже фиксирована, а «чёрная» часть варьируется. «Белая» часть имеет мощность k. «Чёрной» частью может быть любое множество мощности (n – k), элементы которого выбраны из n «чёрных» элементов, присутствующих в M. Так что для заданного стола число возможных «чёрных» частей есть Столько же подмножеств множества M лежит на нашем «столе». Итак, в «комнате» «столов», а на каждом из них подмножеств. Значит, в «комнате» подмножеств. Осталось вспомнить равенство из примера 37 и сложить количества подмножеств по всем «комнатам», чтобы получить общее количество n элементных подмножеств множества M в виде левой части равенства (*). А в правой части стоит символ, по определению выражающий это количество.

Пример 40. Доказать равенство

В множестве мощности (n + 1) выделим какой-то элемент. Совокупность k элементных подмножеств этого множества распадается на два класса: содержащих элемент и не содержащих выделенного элемента

Пример 41. Доказать равенство

Для доказательства полезно привлечь так называемые биномиальные коэффициенты.

Биномиальные коэффициенты – это коэффициенты разложения бинома (1 + x)ⁿ по возрастающим степеням x:

Из выписанной формулы видно, как они обозначаются. Если в этой формуле положить x = –1, то получим: