Чуть более продвинутая задача на применение и доказательство тождеств. Давайте сосчитаем такую сумму чисел сочетания, или биномиальных коэффициентов. C из n по 1 (почему-то у меня С не прорисовывается, не знаю, ну, я надеюсь, что видно), C из n по 1 + 2 × C из n по 2, + 3 × C из n по 3 +... + n × C из n по n. Вот такая вот сумма. На первый взгляд... Посмотришь, и кажется страшно, потому что непонятно, тут даже бином никакой не просматривается. Не угадаешь. Но, с другой стороны, можно... Да, вопрос в том, чему она равна. С другой стороны, можно заметить сразу, что имеется, конечно, вот такое тождество (это самое первое, самое простое тождество, которое мы с вами получали): C из n по k – это в точности C из n по n − k. То есть биномиальные коэффициенты симметричны, так сказать, относительно серединки – они сначала растут, потом убывают. Ну неважно, в общем. C из n по k = C из n по n − k. Что бы нам из этого такое заключить? А давайте обозначим интересующую нас величину x и каждую C-шку, которая присутствует в этом x, заменим согласно указанному тождеству. То есть C из n по 1 запишем как C из n по n−1, C из n по 2 запишем как C из n по n − 2 и, наконец, C из n по n запишем как C из n по 0. И посмотрим, чего у нас получится. Разумеется, получится тот же самый x. Ну, вот, давайте его напишем в новом виде: C из n по 0 + … почему C из n по 0? Извините, вот отсюда начинаем. C из n по n- 1 + 2 C из n по n − 2 + 3 C из n по n − 3 +... + n × C из n по 0. Ну вот переписали просто согласно указанному тождеству. Вполне понятная, вроде как, вещь, да? А теперь давайте возьмем и прибавим к вот этой записи x... Прибавим к вот этой записи x вот эту запись x. То есть сложим вот это равенство и вот это равенство. Ну ясно дело, что с одной стороны получится 2 × x. Если мы сложили два равенства, каждое из которых совпадает с x, то с одной стороны мы, естественно, получаем 2x. А ну, давайте подумаем, что мы получаем с другой стороны. Так, внимание: в верхней строчке есть ли где-нибудь C-шка, которая бралась бы по 0? Ну нет, конечно, 1, 2, 3, n – ни одной C, которая бы бралась по 0. Ну значит, единственная C, которая берется по 0, коль скоро мы складываем вот эту сумму с вот этой суммой, это вот это. Ну, давайте ее напишем: n × C из n по 0. Теперь давайте посмотрим: хорошо, а C из n по 1? Оно где присутствует? Тут есть оно? Есть. Тут есть C из n по 1. Смотрите внимательно: нумерация идет сверху от 0 до n − 1. То есть, вот в этом многоточии слагаемое, которое предшествует нашему последнему слагаемому n × C из n по 0, – это и есть слагаемое, у которого сверху стоит единичка. Так, давайте посмотрим, что это за слагаемое. Очевидно, это n − 1 × C из n по 1 (это просто предыдущее слагаемое вот в этой длинной сумме, n- 1 × C из n по 1). Но и в этой сумме тоже присутствует C из n по 1, причем с коэффициентом 1. Поэтому, когда мы сложим вот эту единственную C по 1 и вот эти n- 1 C по 1, мы получим в сумме n × C из n по 1. Ну, давайте еще, до кучи, посмотрим на ситуацию, которая возникает с C по 2: смотрите, вот здесь она идет с коэффициентом 2 (C из n по 2 идет со множителем с коэффициентом 2). А здесь? Здесь это, очевидно, предшествующее вот этому слагаемое вот в этом многоточии. То есть это n − 2 × C из n по 2. n − 2 × C из n по 2 + 2 × C из n по 2 – это n × C из n по 2 (и вырисовывается некоторая понятная картина), +.... Посмотрите внимательно: здесь стоит n × C из n по n, в этой сумме нету ни одного слагаемого, которое сверху имело бы n, поэтому прибавляем n × C из n по n и получаем n за скобкой, а в скобках C из n по 0 +... + C из n по n. Ну мы ж с вами знаем, чему равна эта сумма. Это в аккурат 2 в степени n, правильно? Сумма всех элементов строчки треугольника Паскаля. Это 2 в степени n. Это n × 2 в степени n получается. И это 2x, где x – это та величина, которая нас в итоге интересует. Ну значит, получается, что x – это есть n × 2 в n- 1 степени. И задача полностью решена. Такой вот хитрый ход: воспользоваться простейшим тождеством, переписать интересующую сумму в немножко другом виде, одно с другим сложить, привести подобный, вынести за скобки и получить итоговый ответ. Это часто работает.
