Давайте теперь, как водится в методе математической индукции, предположим,

предположим, что абсолютно такая же штуковина доказана

для некоторого числа k, где k — это количество свойств.

Давайте предположим (сейчас я напишу аккуратно и все будет понятно).

Предположим, что

для некоторого

k больше либо равного единице.

Предположим, что для некоторого числа k больше либо равного единице и для

всех натуральных чисел n маленькое,

не превосходящих вот этого k, верно

и дальше я переписываю буквально то, что вот здесь вот написано,

но только уже вот с этим вот числом n маленькое, не превосходящим k.

Значит, что верно: для любого количества объектов,

которые мы можем в принципе рассмотреть, для любого множества этих объектов,

состоящего из N большое элементов, и для абсолютно

любых свойств альфа один и так далее альфа

n справедлива формула включений и исключений в том смысле,

в котором она заявлена в формулировке теоремы.

Я не буду ее сейчас переписывать здесь.

Справедлива формула

включений и исключений.

Вот давайте предположим, что для какого-то k не знаю, для какого угодно,

больше либо равного единице, и для всех n, не превосходящих k, мы доказали вот это

вот утверждение, что сколько бы объектов мы ни взяли, какие бы объекты мы ни взяли,

какие бы свойства в количестве n маленькое штук (вот это n маленькое,

не превосходящее k, да?) какие бы свойства в количестве n маленькое штук мы ни взяли,

формула включений и исключений, как она заявлена в теореме, справедлива.

Вот давайте это предположим.

Докажем, что из

этого предположения следует справедливость формулы включений-исключений

не только при всех n не превосходящих k, но еще и при n равном k+1.

Что то же самое

верно и при n равном k+1.

Вот это называется принцип математической индукции.

Если вы его не знали, то вообще говоря интуитивно-то все понятно, что происходит.

Вот давайте посмотрим сюда.

Мы точно знаем, что в качестве такого числа k (вот смотрите на первый пункт

нашего доказательства), мы точно знаем, что для k равного единице,

для k равного единице то, что здесь написано, верно.

Смотрите, действительно, если взять k равное единице,

то что такое произвольное n, не превосходящее k?

n — это натуральное число.

Произвольная n,

которая не превосходит единицы k равно единице — это просто единица.

И для единицы вот оно написано.

Верно, что для любого N большого, для любых а один,

a эн и для любого альфа один справедлива формула включений-исключений.

Ровно это написано и здесь, коль скоро вот это k равняется одному.

То есть для k равного одному мы действительно имеем это утверждение.

Вот оно доказано в пункте один.

Так?

Представим себе, что вот это вот ‹‹докажем,

что то же самое верно и при n равном k+1›› реализовано,

мы доказали, что то же самое верно и при n равном k+1.

Вот смотрите, при n равном, ой извините, при k равном единице это было верно,

то есть при n равном единице это было верно.

А мы умеем доказать для следующего значения n, для n равного двойке.

Ну значит и для n равного двойке это тоже верно.

Итак, мы уже перешли к случаю, когда k равняется двойке.

Это верно сначала для k равного единице, а затем, за счет вот этого перехода,

который здесь осуществлен, мы можем это доказать и для k равного двойке тоже.

Потом предполагаем, что для k равного двойке это доказано.

Имеем право предположить, потому что шаг индукции, как говорят, завершен.

Ну, значит, переходим к k равному тройке, и так далее,

и так для всех натуральных значений k.

В итоге доказываем наше утверждение.

То есть в итоге мы можем вот здесь добавить вот этот квантор для любого еще и

по количеству свойств.

Сначала доказали для одного, потом из одного вывели для двух.

Раз доказали для двух, то опять запустили вот эту процедуру доказали для трех,

раз доказали для трех — запустили снова, доказали для четырех,

и так далее, но вот это такое занудное объяснение того, что такое индукция.

Смысл совершенно понятен.

Это можно формализовывать как угодно, но идея вроде бы очень простая.

Мы просто рекуррентно запускаем одну и ту же процедуру.

Прибегаем к помощи одной и той же процедуры,

которую один раз произвели полностью.

Если у нас есть с чего стартовать, то дальше мы ее каждый раз запускаем и

передоказываем наше утверждение для все большего и большего количества свойств.

Итак, наша цель, наша цель теперь — это действительно доказать,

что то же самое верно и при n равном k+1.

Формулировка и обсуждение индукционного перехода(*)

Комбинаторика для начинающих

Meet the Instructors