M (αk − 1, αk) −...
+ (−1) в k-той степени, просто в точности такая же формула, с заменой N на M.
Я специально ввел это обозначение, чтоб просто легче воспринималось.
Вот. Ну, а здесь будет, соответственно,
M (α₁, ..., αk).
Ну, это просто в точности то, что мы предполагаем выполненным,
и мы имеем право это предполагать, потому, что у нас была база индукции.
Вот тот самый первый пункт, с которого мы начали доказательство теоремы.
А теперь давайте попробуем всё-таки вот эту замечательную формулу,
которая у нас получилась, переписать в изначальных терминах,
то есть в обозначениях, в которых не будет M, а будет только N.
Как бы её переписать в таких терминах?
Ну, очень просто, например, вот это M – это в точности N (αk + 1).
Давайте подумаем, а что такое M (α₁)?
По сути?
Ну, это количество объектов среди вот этих вот, которые обладают свойством α₁,
но сами эти объекты, внимание, это ведь объекты,
которые по определению обладают свойством αk + 1, выбранные вот из
этого множества и по определению обладают, как минимум, свойством αk + 1.
Если мы из них, в свою очередь, выбираем тех товарищей, которые обладают свойством
α1 — ведь мы в итоге получаем ровно те объекты из исходного множества,
которые обладают и свойством αk + 1, и свойством α1.
Мы отсюда извлекли сначала все объекты, которые заведомо обладают свойством αk +
1, а потом из них, в свою очередь, выбрали те, которые обладают еще и свойством α1.
Понятно, что в результате мы получили просто те объекты отсюда,
которые одновременно обладают как αk + 1, так и α1.
То есть, если вот это вот равняется N( αk + 1 ),
то вот это число — это N( α1, αk + 1).
Можно вот так написать.
Просто количество всех объектов из исходного множества,
которые одновременно обладают как вот этим, так и вот этим.
Совершенно так же здесь получаем N( αk,
αk + 1 ), здесь получаем N( α1,
α2, αk + 1), здесь получаем
N(αk − 1, αk, αk + 1 ).
Ну и так далее.
Вот здесь вот получаем M...
Нет, N, извините, конечно N.
Мы все приводим к виду N.
N(α1, ..., αk, αk + 1 ).
Вот такая вот замечательная формула.
Да, а что такое слева?
Что написано слева?
Ну слева тоже написано количество объектов среди вот этих вот.
То есть среди тех объектов отсюда, которые обладают свойством αk + 1,
и которые в то же время не обладают ни одним из оставшихся свойств.
То есть вот эта вот величина (давайте я здесь напишу),
M(α1′, ..., αk′) = N(α1′,
..., αk′, αk + 1 без штриха).
Мы смотрим те объекты, которые, с одной стороны,
обладают αk + 1 свойством, но при этом не обладают ни одним из первых k свойств.
α1′, ..., αk′ — вот ни одним из них не обладают.
В итоге получилась такая замечательная формула.
Давайте ее еще раз перепишем.
N(α1′, ..., αk′,
αk + 1) = N(αk + 1) (и
эта формула доказана строго, потому что она вытекает
из предположения индукции) − N(α1, αk + 1) −...
− N(αk, αk + 1) +...
+ N от...
сейчас, секунду...
плюс и так далее, давайте вот так плюс...
виноват, немножко запутался.
Значит, +...
+ просто вот это напишем.
( −1) в k-той степени N(α1,
..., αk, αk + 1).
Вот так, покороче записал уже.
Не стал лишнего выписывать.
Вот эти слагаемые писать не стал.
Вот. Это то, что у нас получилось на выходе в
результате рассмотрения второго пункта, да?
Теперь вспоминаем (сейчас мы вернемся немножко сюда), вспоминаем,
что у нас еще есть вот эта формула, которая доказана в первом пункте.
Нудная-пренудная.
Но куда же деваться?
Вот есть такая формула.
Мы ее доказали, а потом — ту.
Давайте знаете что сделаем?
Давайте из вот этой формулы...
из вот этой формулы, из этого равенства вычтем то новое равенство,
которое только что доказали.
Сейчас будем это аккуратно делать на оставшемся у нас месте.
Что значит «вычесть»?
Значит, надо из N(α1′,
..., αk′) вычесть (это вот то,
что находится слева в наших формулах) N(α1′,
..., αk′, αk + 1).
Это вот слева.
А дальше, после знака равенства,
мы тоже будем вычитать все, что написано вот здесь из того,
что было написано в рамках пункта один, который я только что показал и напомнил.
Значит, вот будем вычитать.
Ну давайте посмотрим, а что вот это такое?
Чему это на самом деле равняется?
Значит, здесь у нас написано количество тех объектов,
которые не обладают ни одним из первых k свойств.
А здесь у нас написано количество тех из них,
тех из них, то есть опять же тех, которые не обладают ни одним из первых k свойств,
но которые к тому же еще обладают k + 1 свойством.
То есть вот есть все, которые не обладают k свойствами, а есть среди них те,
которые обладают свойством k + 1.
Ну понятно, сколько их.
Их в точности N(α1′, ..., αk + 1′).
Из всех, которые этими не обладают,
мы вычитаем их же, но с добавлением свойства αk + 1.
Значит остаются те, которые, конечно, по-прежнему не обладают первыми k,
но еще и не обладают k + 1.
Видите, уже вырисовывается формула включений-исключений, по крайней
мере ее левая часть, для случая, когда свойств k + 1, как нам и хотелось.
Осталось разобраться с правой частью.
Ну давайте смотреть.
Вот в той формуле, которая есть в пункте один,
у нас присутствует число N, правильно?
Дальше из него вычитаются числа N(α1) −...
− N(αk) и это все, что вычиталось в рамках той формулы,
которая была доказана в пункте один текущего доказательства.
Но из этой части мы, в свою очередь, вычитаем все, что нарисовано вот тут.
Все, что нарисовано в доказанном в рамках пункта два утверждении.
В частности, мы вычитаем и вот это N тоже.
Мы вычитаем N(αk + 1).
Смотрите, как здорово.
Формула прорисовывается все дальше.
Видите, было общее количество объектов.
Выкинули те, которые знают α1, те, которые знают αk,
но у нас же их k + 1 штука, значит надо еще выкинуть k + 1.
Да, действительно, выкинули k + 1 за счет вот этого вот.
Мы же его вычитаем?
Теперь давайте прибавлять.
В формуле, которая доказана в рамках пункта один доказательства.
Мы прибавляли исключительно N(α1, α2) +...
+ N(α k − 1, αk), потому что на том этапе мы рассматривали только k свойств.
Но здесь явно чего-то не хватает,
чтобы была справедлива формула включений-исключений для k + 1 свойства.
А чего не хватает?
Так, друзья мои, ровно того не хватает, что вот здесь вычитается.
Но вы не забывайте, мы же вычитаем вот это выражение.
То есть вот эти все «минусы» заменяются на «плюсы» при вычитании.
Мы добавляем еще N(α1, αk + 1) +...
+ N(αk, αk + 1).
И таким образом, среди вот этих вот прибавляемых присутствуют уже все
возможные пары свойств, в том числе вот эти вот.
Ну и так далее.
Дальше, я думаю, совершенно понятен принцип.
Последнее вычитаемое будет вот эта вот штука.
Давайте ее напишем.
Будет «плюс», и она пойдет со знаком «минус», вот эта вот величина.
Ну что значит «она пойдет со знаком минус»?
Это значит (−1) в k-той степени умножится на (−1).
Получится (−1) в k + 1.
А в скобочках после N будет в аккурат (α1, ..., αk + 1).
Теперь смотрите на формулировку нашей теоремы,
формулы включений-исключений — и получайте катарсис, если это еще возможно.
Потому что все, мы доказали, действительно,
формулу включений-исключений ровно в том виде,
в котором она заявлена в нашей теореме, но теперь уже для случая k + 1 свойств.
Все, теорема доказана.
