bulgakov

24. Следствия бинома: подстановки

Формула бинома верна при любых значениях xx и yy, поэтому в неё можно подставлять числа. Подстановка x=y=1x=y=1 даёт сумму всех биномиальных коэффициентов 2n2^n, подстановка x=−1, y=1x=-1,\ y=1 даёт знакопеременную сумму 00, а вместе они показывают, что суммы коэффициентов на чётных и на нечётных местах одинаковы и равны 2n−12^{n-1}.

Что пригодится из прошлого: бином Ньютона — формула (x+y)n=∑(nk)xkyn−k(x+y)^n=\sum\dbinom nk x^ky^{n-k}; свойства сочетаний — там мы уже доказывали ∑(nk)=2n\sum\dbinom nk=2^n другим способом. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Идея: подставить числа

Равенство (x+y)n=∑k=0n(nk)xkyn−k(x+y)^n=\sum_{k=0}^{n}\dbinom nk x^ky^{n-k} верно для любых xx и yy. Значит, мы вправе вместо букв подставлять конкретные числа, и обе части останутся равными. Подберём числа так, чтобы получилась красивая формула.

Следствие 1: подстановка y=1y=1

(1+x)n=∑k=0n(nk)xk.\boxed{(1+x)^n=\sum_{k=0}^{n}\binom nk x^k}.

Достаточно положить y=1y=1 в формулу бинома: yn−k=1y^{n-k}=1 для всех kk. Это запись «коэффициент при xkx^k в (1+x)n(1+x)^n равен (nk)\dbinom nk». Именно её мы используем в главах про тождество Вандермонда и про «клюшку».

Следствие 2: подстановка x=y=1x=y=1

∑k=0n(nk)=2n.\boxed{\sum_{k=0}^{n}\binom nk=2^n}.

Слева в формуле бинома получается (1+1)n=2n(1+1)^n=2^n, справа все степени единицы равны 11, остаются только биномиальные коэффициенты. Это уже знакомая сумма по размерам подмножеств: теперь она доказана ещё и алгебраически.

Следствие 3: подстановка x=−1x=-1, y=1y=1

∑k=0n(−1)k(nk)=0(n≥1).\boxed{\sum_{k=0}^{n}(-1)^k\binom nk=0\qquad(n\ge1)}.

Слева (−1+1)n=0n=0(-1+1)^n=0^n=0 (при n≥1n\ge1). Справа получаем (nk)(−1)k⋅1\dbinom nk(-1)^k\cdot1. Знаки чередуются: числа строки треугольника Паскаля берутся по очереди со знаками +,−,+,−,…+,-,+,-,\dots. Для строки 55:

1−5+10−10+5−1=0.1-5+10-10+5-1=0.

Исключение: n=0n=0. Тогда сумма состоит из одного слагаемого (00)=1\dbinom00=1, и равенство 00 неверно. Поэтому в условии стоит n≥1n\ge1 (то есть n∈Nn\in\mathbb N).

Следствие 4: чётные и нечётные места

(n0)+(n2)+(n4)+⋯=(n1)+(n3)+(n5)+⋯=2n−1(n≥1).\boxed{\binom n0+\binom n2+\binom n4+\cdots=\binom n1+\binom n3+\binom n5+\cdots=2^{n-1}\qquad(n\ge1)}.

В левой части суммируются коэффициенты с чётными нижними числами k=0,2,4,…k=0,2,4,\dots (последнее слагаемое — (n2⌊n/2⌋)\dbinom n{2\lfloor n/2\rfloor}), в средней — с нечётными (последнее — (n2⌊(n−1)/2⌋+1)\dbinom n{2\lfloor (n-1)/2\rfloor+1}).

Доказательство. Обозначим сумму коэффициентов на чётных местах через SчS_{\text{ч}}, на нечётных — через SнS_{\text{н}}. Следствие 2 говорит: Sч+Sн=2nS_{\text{ч}}+S_{\text{н}}=2^n. Следствие 3 говорит, что чётные слагаемые входят со знаком ++, а нечётные со знаком −-, и

Sч−Sн=0.S_{\text{ч}}-S_{\text{н}}=0.

Из Sч−Sн=0S_{\text{ч}}-S_{\text{н}}=0 следует Sч=SнS_{\text{ч}}=S_{\text{н}}. Подставим в первое равенство: Sч+Sч=2nS_{\text{ч}}+S_{\text{ч}}=2^n, то есть Sч=Sн=2n−1S_{\text{ч}}=S_{\text{н}}=2^{n-1}. □\square

Проверка на малых nn

  • n=1n=1: чётные kk — 1=11 = 1; нечётные kk — 1=11 = 1; 2n−1=12^{n-1}=1
  • n=2n=2: чётные kk — 1+1=21 + 1 = 2; нечётные kk — 2=22 = 2; 2n−1=22^{n-1}=2
  • n=3n=3: чётные kk — 1+3=41 + 3 = 4; нечётные kk — 3+1=43 + 1 = 4; 2n−1=42^{n-1}=4
  • n=4n=4: чётные kk — 1+6+1=81 + 6 + 1 = 8; нечётные kk — 4+4=84 + 4 = 8; 2n−1=82^{n-1}=8
  • n=5n=5: чётные kk — 1+10+5=161 + 10 + 5 = 16; нечётные kk — 5+10+1=165 + 10 + 1 = 16; 2n−1=162^{n-1}=16
  • n=6n=6: чётные kk — 1+15+15+1=321 + 15 + 15 + 1 = 32; нечётные kk — 6+20+6=326 + 20 + 6 = 32; 2n−1=322^{n-1}=32

Видно, как суммы совпадают при каждом nn и равны 2n−12^{n-1}.

Что это значит для подмножеств

Число подмножеств nn-элементного множества с чётным числом элементов равно числу подмножеств с нечётным числом элементов, и каждое равно 2n−12^{n-1} (при n≥1n\ge1).

Есть и прямое объяснение. Выберем один элемент aa. Любое подмножество либо содержит aa, либо нет. Если в подмножестве есть aa — уберите его; если нет — добавьте. Так чётные подмножества превращаются в нечётные и обратно, и это взаимно однозначное соответствие.

Примеры

1. ∑k=08(8k)=28=256\sum_{k=0}^{8}\dbinom8k=2^8=256.

2. (60)+(62)+(64)+(66)=1+15+15+1=32=25\dbinom60+\dbinom62+\dbinom64+\dbinom66=1+15+15+1=32=2^5.

3. Подстановка другого числа. Сумма ∑k=0n2k(nk)\sum_{k=0}^{n}2^k\dbinom nk: в формуле бинома положим x=2x=2, y=1y=1:

∑k=0n(nk)2k=(2+1)n=3n.\sum_{k=0}^{n}\binom nk2^k=(2+1)^n=3^n.

Для n=4n=4: 1+8+24+32+16=81=341+8+24+32+16=81=3^4.

Частые ошибки

  • Подставлять x=−1x=-1 и забывать, что n=0n=0 — исключение. Равенство ∑(−1)k(nk)=0\sum(-1)^k\dbinom nk=0 верно только при n≥1n\ge1.
  • Путать чётность nn и чётность kk. В следствии 4 чётность относится к нижнему числу kk.
  • Считать, что суммы на чётных и нечётных местах равны 2n2^n. Они равны 2n−12^{n-1}: вместе дают 2n2^n.
  • Подставлять в формулу только «удобные» числа. Можно любые: x=2x=2, y=1y=1 дают 3n3^n; x=y=2x=y=2 дают 4n4^n.

Проверь себя

1. Найдите ∑k=010(10k)\sum_{k=0}^{10}\dbinom{10}k.

Решение

210=10242^{10}=1024.

2. Найдите (70)+(72)+(74)+(76)\dbinom70+\dbinom72+\dbinom74+\dbinom76.

Решение

Сумма на чётных местах равна 27−1=642^{7-1}=64. Проверка: 1+21+35+7=641+21+35+7=64.

3. Найдите ∑k=0n(nk)3k\sum_{k=0}^{n}\dbinom nk3^k.

Решение

Подставляем x=3x=3, y=1y=1 в формулу бинома: (3+1)n=4n(3+1)^n=4^n.

4. Сколько подмножеств шестиэлементного множества содержат нечётное число элементов?

Решение

(61)+(63)+(65)=6+20+6=32=25\dbinom61+\dbinom63+\dbinom65=6+20+6=32=2^5.

Итог

  • Формула бинома верна при любых x,yx,y: в неё можно подставлять числа.
  • y=1y=1: (1+x)n=∑(nk)xk(1+x)^n=\sum\dbinom nkx^k. x=y=1x=y=1: сумма коэффициентов 2n2^n.
  • x=−1, y=1x=-1,\ y=1: знакопеременная сумма равна 00 (при n≥1n\ge1).
  • Суммы коэффициентов на чётных и нечётных местах одинаковы и равны 2n−12^{n-1}.
ПрактикаЗагружаем тест…