Ну давайте еще одну задачку на тождество про треугольник Паскаля, чтобы оно как-то совсем было сочно, понятно. Давайте я ее словами сформулирую, а потом нарисую, собственно, треугольник Паскаля, так чтобы было понятно, о чем говорится словами. Значит, говорится так: давайте обозначим буквой C произвольный собственный элемент, произвольное число треугольника Паскаля. Произвольное число, стоящее в треугольнике Паскаля где-нибудь. ...произвольное число в треугольнике Паскаля. А дальше попробуем сделать следующее: сосчитаем сумму чисел, сосчитаем сумму чисел в треугольнике Паскаля, которые стоят на прямой, справа вверх идущей от вот этого числа C, включая число C. Так, посчитаем сумму чисел в треугольнике от вот этого числа C и дальше направо вверх, от C и дальше направо верх. Сейчас нарисую, будет совершенно понятно, о чем идет речь. ...и дальше направо вверх. [ШУМ] Утверждается, – это нам предстоит доказать, – что сумма, которая получится в итоге, равна числу, которое, наоборот, стоит снизу вправо от числа C. Она (это утверждение, это надо доказать) равна числу, стоящему под C справа, под C справа. Ну сейчас разберемся. Давайте, чтоб вообще понять, в чем состоит утверждение задачи, для начала просто нарисуем треугольник Паскаля. Как он рисуется? Ну можно вот так нарисовать. В числах просто: 1, потом (1, 1), потом (1, 2, 1), потом (1, 3, 3, 1), (1, 4, 6, 4, 1), у и так далее там, до бесконечности можно рисовать. Вот. Ну имеется в виду следующее: вот, например, если вот это число мы обозначили буквой C, если буква C обозначает вот это число, то сумма вот этих вот чисел от 3 доверху, видите, вот так вот она идет, диагональка эта прямая, вправо вверх, 3 + 2 + 1 = 6. О, чудо! равняется шести! Или если мы вот это, например, обозначили за C, пускай это C, тогда мы складываем 6, 3, 1. Хе, так здесь, действительно, стоит 10. Если вы посмотрите на построение треугольника Паскаля – здесь действительно стоит 10. Но давайте попробуем, все-таки, сформулировать это утверждение в терминах биномиальных коэффициентов, то есть в терминах чисел сочетаний. Что это за тождество для C из n по k или там для C из n по (k + 1), не знаю. Для этого перерисуем треугольник. Смотрите, вот что такое вот эта самая верхняя единица? Ну и на лекции это наверняка у нас было – это C из 0 по 0. Следующая строчка – это C из 1 по 0 и C из 1 по 1. Дальше идет C из 2 по 0, C из 2 по 1, C из 2 по 2. Дальше C из 3 по 0, C из 3 по 1, C из 3 по 2, C из 3 по 3, ну и так далее. То есть у нас очередная строчка треугольника Паскаля она состоит из цешек, у которых нижний коэффициент – это номер этой строчки. Ну нулевой номер – это C из 0 по 0. Первый номер – это C из 1 по 0 и C из 1 по 1. Ну то есть это коэффициенты в биноме Ньютона, когда (x + y) возводится в нулевую степень, здесь – когда (x + y) возводится в первую степень. Здесь, когда (x + y) возводится в квадрат, здесь – когда в куб, ну и так далее. То есть вот это число C – это, на самом деле, просто какое-то C из n по k. Это просто биномиальный коэффициент C из n по k. Ну вот давайте, например, вот здесь нарисуем C и скажем, что вот это есть C из n по k. Тогда в этом случае как выражается та сумма, которая идет вот по соответствующей диагональке, скажем, вот отсюда сюда? Что это за сумма такая? На следующей строчке, на следующем слое у нас находится, если здесь была n, у нас находится, конечно, (n – 1). Здесь n – тройка, значит двойка – это (n – 1). Или даже вот это еще более показательно: n = 3, следующая 2, а следующая единице. То есть мы прибавляем C из (n – 1), но сейчас важно понять по кому? А совершенно понятно по кому, – видите, они все время совпадают внутри соответствующей диагональки, – то есть тоже по k. И так вплоть до чего? Вот здесь вот все заканчивается просто на C из k по k, и здесь тоже все заканчивается на C из k по k. То есть последнее слагаемое – это C из k по k. Вот та самая странная сумма, которая здесь была не очень понятна, это сумма C из n по k, C из (n – 1) по k, C из (n – 2) по k и так далее, покуда имеет смысл суммировать, вплоть до C из k по k. Уже C из (k – 1) по k никакого смысла не имеет, да и в треугольнике Паскаля такого числа, естественно, тоже нет. Так вот утверждается, что вся эта сумма равна числу, которое стоит, наоборот, вот сюда вот, вправо вниз. И как оно выражается? Понятно, что если здесь была n-ная строчка треугольника Паскаля, то в следующей строке номер будет (n + 1). То есть это C из (n + 1), и осталось понять по кому? C из (n + 1) по кому же здесь у нас будет? Это вот очень интересный вопрос: что справа снизу? Ну вот можно здесь, например, увидеть, да? C из 2 по 1, а здесь (n + 1) – это 3, (2 + 1 это 3), если здесь было по k, то здесь будет по (k + 1). То есть это C из (n + 1) по (k + 1). Вот такое вот замечательное тождество, которого у нас в лекциях-то, в общем-то, не было. То есть утверждается, что выполнено вот это тождество, я его не доказал, я просто переформулировал пока что задачу. Если задача изначально была сформулирована вот в таких, ну как сказать, словесных терминах, то мы сообразили, что в общем случае она означает вот такое тождество: для любых n и k сумма таких вот цешек – это в точности C из (n + 1) по (k + 1). Ну, на самом деле, все очень просто и все вылезает из основного тождества, которое порождает треугольник Паскаля. Давайте, действительно, докажем, ну можно доказывать по индукции, а я буду действовать просто методом последовательных приближений. Значит C из (n + 1) по (k + 1). Если применить стандартное тождество, которое мы с вами знаем, оно, кажется, шло в лекции за номером 3, это тождество, которое касается, собственно, треугольника Паскаля. Это получится так: будет C из n по (k + 1) плюс C из n по k, не так ли? Это будет C из n по (k + 1) плюс C из n по k. Мы из (n + 1) объекта выбираем (k+ 1) объект – это тоже самое, что из n объектов выбрать (k + 1) объект плюс из n объектов выбрать k объект и присоединить первый объект. Так доказывалось это тождество, это в точности тождество из лекции. Я просто напоминаю его доказательство, ну совсем вкратце. Но мы можем дальше развернуть. Мы можем взять и вот это, вот к этой величине снова применить то же самое тождество. К C из n по (k + 1) то же самое тождество. Давайте посмотрим: вот эту цешку напишем вначале, C из n по k, ее напишем просто, а дальше вот к этой величине применим то же самое тождество. Что у нас получится? У нас получится C из (n – 1) по k плюс C из (n – 1) по (k + 1). Абсолютно то же самое тождество. Смотрите, уже отчленилось C из n по k, вот оно, и C из (n – 1) по k, вот оно. Ну вот дальше точно так же переписываем, сохраняя слагаемые C из n по k и C из (n – 1) по k. Разворачиваем вот эту штуку согласно тождеству. Получаем C из (n – 2) по k плюс C из (n – 2) по (k + 1), Ну и видно, что мы так каждый раз будем понижать n на очередную единичку, пока не докатимся до C из k по k. =... = (C из n по k) + (C из (n – 1) по k) +... + (C из k по k). Вот, собственно говоря, задачу мы и решили. Повторяю, строго это доказывается, наверное, с помощью индукции, но идея она совершенно понятна, что постепенно мы дойдем досюда. И дальше уже получим нулевые слагаемые, согласно обычному второму тождеству из нашей лекции.
