90
правок
Изменения
→Формула включения-исключения
Тогда
<tex> | A |=| A_n |+\Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j \in I_{n-1} } A_j \Big| \Bigg) + \Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+2} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| \Bigg) = \sum \limits_{I_n} (-1)^{|I_n|+1} \Big| \bigcap \limits_{ j \in I_n } A_j \Big| )</tex>.
Равенство справедливо, потому что все наборы <tex> I_n </tex> можно разбить на три группы :
1) <tex> (n) </tex>
2) <tex> (I_{n-1})</tex> Это означает, что в наборе точно '''не''' будет присутствовать индекс <tex> n </tex>, а будут все различные варианты индексов остальных множеств, т.е. <tex> I_{n-1} </tex>
3) <tex> (n; I_{n-1}) </tex> Аналогично предыдущему, только в наборе будет индекс <tex> n </tex>
Как видно из равенства, каждое слагаемое "отвечает" за соответствующие группы. Значит равенство истинно.
Значит для <tex>~l=n</tex> мы доказали, что равенство верно. Значит индукционный переход доказан, то теорема доказана.
}}
