Чуть более продвинутая задача на применение и доказательство тождеств.
Давайте сосчитаем такую сумму чисел сочетания,
или биномиальных коэффициентов.
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 степени.
И задача полностью решена.
Такой вот хитрый ход: воспользоваться простейшим тождеством,
переписать интересующую сумму в немножко другом виде, одно с другим сложить,
привести подобный, вынести за скобки и получить итоговый ответ.
Это часто работает.
