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

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

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

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

Только что полученная формула очень похожа на равенство, которое требовалось доказать. И это не случайно. Дело в том, что биномиальный коэффициент и количество подмножеств  – это одно и то же число. Пример 42. Доказать равенство

Только что полученная формула очень похожа на равенство, которое требовалось доказать. И это не случайно. Дело в том, что биномиальный коэффициент и количество подмножеств  – это одно и то же число.

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

Мы наметим лишь план доказательства. Сначала равенство проверяется для случаев k = 0 и k = n. Затем доказывается равенство, аналогичное равенству из примера 40:

Мы наметим лишь план доказательства. Сначала равенство проверяется для случаев k = 0 и k = n. Затем доказывается равенство, аналогичное равенству из примера 40:

Доказать это равенство чрезвычайно просто. Надо рассмотреть два способа записи разложения степени бинома (1 + x)n+1 по возрастающим степеням x. Первый способ – стандартный, с использованием коэффициентов Второй способ таков: возводим (1 + x) в степень n, располагаем по степеням x с использованием коэффициентов а затем это разложение умножаем на (1 + x) и развёртываем в многочлен. Если теперь приравнять коэффициенты при одинаковых степенях переменной, то получим равенство (****). Далее, для получения равенства (***) рассуждаем по индукции. Этому рассуждению можно придать легко запоминающуюся форму. Рассмотрим так называемый треугольник Паскаля:

Доказать это равенство чрезвычайно просто. Надо рассмотреть два способа записи разложения степени бинома (1 + x)n+1 по возрастающим степеням x. Первый способ – стандартный, с использованием коэффициентов