Давайте сделаем следующую вещь.
Давайте, во-первых, заметим, заметим,
что достаточно доказать стремление к 0,
стремление к 0 вот такой
суммы по i от 1 до n/2 C из n по
i * (1 − p) в степени i * (n − i).
С чем это связано?
Ну это связано, конечно, с тем, что C из n по i — это симметричная функция.
То есть при i и при (n − i) получается одно и то же значение.
И точно так же имеет место симметрия во втором сомножителе.
То есть, та сумма, которая лежит за пределами нарисованной,
она такая же точно.
Таким образом, если мы докажем, что вот эта сумма стремится к 0, то, естественно,
мы докажем, что стремится к 0 вся сумма.
Ну тут мне могут сказать: «Ой,
а вдруг n пополам не делится?» Ну до целой части от пополам, хорошо.
До целой части.
Вот, это все ерунда, это все мелочи.
Нам бы суть понять.
И вот давайте введем такое обозначение.
Давайте через a с индексом i от n обозначим каждое
очередное слагаемое в этой сумме.
Так, это просто есть C из n по i * (1 − p) в степени i * (n − i).
Так обозначили.
И вот самый загадочный, возможно,
для многих будет момент в происходящем.
Давайте эту сумму разобъем на два куска, на две подсуммы.
То есть представим сумму по i от
1 до n/2 ai-тых от n (сейчас будет ужас,
держитесь, товарищи!) как сумму по i от
1 до n поделить на повторный логарифм
n (вот это должно вызывать трепет и страх у слушателя.
А? Вызывает?
Нет?
Вызывает!) так, ну, понятное дело, ai-тых от n и...
Ой, да-да-да-да!
Это тоже нацело может не делиться, естественно, до целой части.
Я ее не рисую, я надеюсь, что это как раз понятно.
А здесь у меня будет сумма, наоборот,
по i от n на повторный логарифм n (снова, конечно,
со взятием всех необходимых целых частей, это неважно) до n/2.
И здесь то же самое слагаемое ai-тое от n.
Ну, конечно, глядя на всю эту красоту и торжество науки,
человек должен не то что в катарсис попадать, а просто выпадать в осадок, да?
Но ничего, я постараюсь объяснить, откуда эти странные разграничения.
Как, вообще, до них можно было додуматься, я тоже попробую потом объяснить.
Да даже сейчас немножко объясню.
Смотрите: самое первое слагаемое a1 от n, мы знаем,
оно стремится к 0 при n стремящимся к бесконечности.
Это мы знаем.
Это мы давно доказали.
Сейчас мы убедимся в том, что,
конечно, каждое последующее слагаемое только меньше предыдущего.
Иначе нам точно несдобровать и не доказать, что вся сумма стремится к 0.
Это-то понятно.
Ясно, что каждое из следующих слагаемых должно быть меньше предыдущего.
Это ясно.
Но более того, друзья, вот мы сейчас докажем,
что в рамках вот этого суммирования, то есть в условиях,
когда i находится в пределах от 1 до n поделить на повторный логарифм n,
вот в этих условиях отношения двух соседних слагаемых
не просто меньше 1 (то есть последующего, предыдущего),
не просто меньше 1, но в растущее число раз меньше 1.
И это нам поможет все оценить.
Но за то время, покуда эти самые слагаемые будут так значимо уменьшаться,
уменьшаться, уменьшаться и уменьшаться, они доуменьшаются настолько,
что в этой сумме будут только пренебрежимо крошечные слагаемые,
и она уже тупо оценится просто максимальным из них, вернее...
да, максимальным из них, помноженным на количество всех слагаемых в этой сумме.
Это вот идея, как можно было придумать такое разграничение.
Ну а техническую реализацию мы сейчас, конечно, будем осуществлять.
Но знаете, я думаю, что техническую реализацию
мы будем осуществлять не здесь.
Что-то мне места мало, а?
Давайте побольше места возьмем и будем осуществлять техническую реализацию.