Таблицы Брадиса

Пусть при утверждение верно.

Пусть при утверждение верно.

Элементы математики в задачах - Г. А. Мерзон

Решение. б) Раскроем скобки в произведении (a + b)... (a + b). Каждо­му слагаемому соответствует подмножество скобок, в которых была выбрана буква b. Следовательно, слагаемых вида an-kbk будет ровно Ck = ^ k). Значит, после приведения подобных слагаемых мы полу­чим в точности правую часть доказываемого равенства.

Решение 2. б) Докажем это утверждение индукцией по n.

База индукции n = 1 очевидна.

Шаг индукции. Пусть при n = N утверждение верно. Докажем его при n = N + 1.

(a + b)N+1 = (a + b)(a + b)N = (a + b)(([j)an + ... + ( nJb^ =

= ( 0 K1 + (( 0 ) + ( n ))"+•+(( ) 1 ) + ( n )H + ( n >n+1-

Осталось воспользоваться тем, что ^ n +1 ) = ^ k) + ( ^ 1 ).

Задача 11. Докажите, что:

а) (0) + (n) + -ЧD =2n;

б) a-( о+-+(-1)4^=».

Решение. Подставив в бином Ньютона a = 1, b = 1, получим утвер­ждение пункта а), а подставив a = 1, b = -1, получим утверждение пункта б).

126                     Комбинаторика 2. Бином Ньютона

Решение 2. а) По определению треугольника Паскаля, каждое число следующей строки есть сумма двух чисел предыдущей строки. При этом каждое число предыдущей строки вносит свой «вклад» ровно в два числа следующей строки. Поэтому сумма чисел следующей стро­ки в два раза больше суммы чисел предыдущей строки. Дальнейшее рассуждение оставляем читателю в качестве упражнения.

б)  Подставим в левую часть всюду             + (п 1) вместо .

Осталось заметить, что при этом каждое из чисел предыдущей строки встретится один раз со знаком «+» и один раз со знаком «-».

Решение 3. а) Найдем двумя способами количество подмножеств п- элементного множества. С одной стороны, оно равно сумме коли­честв к-элементных подмножеств по 0 ^ к ^ п, то есть левой части доказываемого тождества. С другой стороны, таких подмножеств 2п.