90
правок
Изменения
Нет описания правки
Равенство справедливо, потому что все наборы <tex> I \in 2^N </tex> можно разбить на три группы :
# <tex> I \in 2^{N'} </tex> Это означает, что в наборе точно '''не''' будет присутствовать индекс <tex> n </tex>, а будут все различные варианты индексов остальных множеств, т.е. <tex> I \in 2^{N'}</tex>
# <tex>\{n\} \cup I</tex>, где <tex>I \in N'</tex> Аналогично предыдущему, только в наборе будет индекс <tex> n </tex>
Как видно из равенства, каждое первое и третье слагаемое "отвечаетотвечают" за соответствующие группывторую группу, а второе слагаемое за первую группу. Значит, равенство истинно.
Таким образом, для <tex>~l=n</tex> мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.
}}
