http://img.pslan.com/uploads/be59e442475f8c2a6bdfa305a1f2498a.jpg
Формулу включений-исключений можно доказать по индукции [1][5].
При формула включений-исключений тривиальна:
Пусть формула верна для , докажем ее для .
Пусть каждый элемент множества может обладать или не обладать любым из свойств . Применим формулу включений-исключений для свойств :
Теперь применим формулу для свойств к множеству объектов, для которых выполнено свойство :
Наконец, применим формулу для одного свойства к совокупности , объектов, которые не обладают свойствами :
Комбинируя выписанные три формулы, получим формулу включений-исключений для свойств . Что и требовалось доказать.
Комбинаторное доказательство
Рассмотрим произвольный элемент и подсчитаем, сколько раз он учитывается в правой части формулы включений-исключений
Если элемент не обладает ни одним из свойств , то в правой части формулы он учитывается ровно 1 раз (в члене ).
Пусть элемент обладает в точности свойствами, скажем . Он дает по 1 в тех слагаемых суммы , для которых есть подмножество , и 0 для остальных. Число таких подмножеств по определению есть число сочетаний . Следовательно, вклад элемента в правую часть равен
При числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равна
Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств , то есть . Что и требовалось доказать.