Задача
COM-B2-M03-P017 Инволюция для знакопеременной суммы
#17
★★★★☆ Уровень 4 из 5
Докажите биективно, что \(\sum_{k=0}^{n}(-1)^k\binom nk=0\) при \(n\ge1\).
Сократите чётные и нечётные подмножества инволюцией.
Сумма считает чётные подмножества со знаком \(+\) и нечётные со знаком \(-\). Зафиксируем элемент \(1\). Отображение \(S\mapsto S\triangle\{1\}\) меняет чётность размера и является обратным самому себе. Значит, каждое чётное подмножество спарено с нечётным, и вклад пар сокращается. Сумма равна \(0\).
Это базовая знакопеременная инволюция.