bulgakov

27. Хоккейная клюшка: суммы вдоль диагонали

Если сложить числа, стоящие подряд вдоль одной диагонали треугольника Паскаля, начиная с края, то сумма окажется следующим числом — на шаг вниз и вбок: (kk)+(k+1k)+⋯+(k+nk)=(n+k+1k+1)\dbinom kk+\dbinom{k+1}k+\dots+\dbinom{k+n}k=\dbinom{n+k+1}{k+1}. Картинка похожа на клюшку для хоккея: длинная ручка из слагаемых и «крюк» с суммой.

Что пригодится из прошлого: бином и (1+x)n=∑(nk)xk(1+x)^n=\sum\dbinom nkx^k — для доказательства через коэффициенты; правило Паскаля — для второго доказательства; сочетания. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Клюшка в треугольнике Паскаля

Возьмём диагональ треугольника Паскаля: числа (22),(32),(42),(52),(62)\dbinom22,\dbinom32,\dbinom42,\dbinom52,\dbinom62, то есть 1,3,6,10,151,3,6,10,15. Сложим: 1+3+6+10+15=351+3+6+10+15=35. И число 35=(73)35=\dbinom73 стоит на шаг вниз и вправо от последнего слагаемого. Слагаемые и сумма отмечены скобками (показана левая часть треугольника: справа числа повторяются зеркально):

                       1
                    1     1
                 1     2    [1]
              1     3    [3]    1
           1     4    [6]    4
        1     5    [10]   10
     1     6    [15]   20
  1     7     21   [35]

Теорема. Для любых n,k∈Nn,k\in\mathbb N

∑i=0n(k+ik)=(n+k+1k+1).\boxed{\sum_{i=0}^{n}\binom{k+i}{k}=\binom{n+k+1}{k+1}}.

Слева слагаемые идут по диагонали: верхний индекс растёт на единицу, нижний kk не меняется. Сумма справа получается из последнего слагаемого переходом (n+kk)↦(n+k+1k+1)\dbinom{n+k}{k}\mapsto\dbinom{n+k+1}{k+1}: оба индекса растут на единицу.

Почему это верно: три доказательства

1. Выбор по наибольшему элементу

Рассмотрим множество M={0,1,2,…,n+k}M=\{0,1,2,\dots,n+k\} из n+k+1n+k+1 элементов и выберем в нём k+1k+1 числа. Всего (n+k+1k+1)\dbinom{n+k+1}{k+1} способов. А теперь разобьём все такие подмножества по наибольшему элементу mm.

Если наибольший элемент равен mm, остальные kk элементов выбираются из чисел 0,1,…,m−10,1,\dots,m-1, а их mm штук: (mk)\dbinom mk способов. Наибольший элемент не может быть меньше kk (иначе не хватит чисел), поэтому m=k,k+1,…,n+km=k,k+1,\dots,n+k. Для k=1k=1 это двухэлементные подмножества множества {0,…,4}\{0,\dots,4\}:

  • наибольший элемент 11: {0, 1} — всего 1
  • наибольший элемент 22: {0, 2}, {1, 2} — всего 2
  • наибольший элемент 33: {0, 3}, {1, 3}, {2, 3} — всего 3
  • наибольший элемент 44: {0, 4}, {1, 4}, {2, 4}, {3, 4} — всего 4

Всего подмножеств: 10.

Группы не пересекаются, и вместе они содержат все подмножества. Значит,

(kk)+(k+1k)+⋯+(n+kk)=(n+k+1k+1).\binom{k}{k}+\binom{k+1}{k}+\dots+\binom{n+k}{k}=\binom{n+k+1}{k+1}.

2. Цепочка по правилу Паскаля

По правилу Паскаля (k+i+1k+1)=(k+ik+1)+(k+ik)\dbinom{k+i+1}{k+1}=\dbinom{k+i}{k+1}+\dbinom{k+i}{k}. Перепишем: (k+ik)=(k+i+1k+1)−(k+ik+1)\dbinom{k+i}{k}=\dbinom{k+i+1}{k+1}-\dbinom{k+i}{k+1}. Каждое слагаемое — разность двух чисел «следующей» диагонали (⋅k+1)\dbinom{\cdot}{k+1}, стоящих подряд, и при сложении всё, кроме краёв, сокращается:

ii (2+i2)\dbinom{2+i}{2} Сумма (3+i3)\dbinom{3+i}{3}
0 1 1 1
1 3 4 4
2 6 10 10
3 10 20 20
4 15 35 35

Каждая частичная сумма в точности равна числу следующей диагонали. Это свойство видно прямо в таблице: третий столбец совпадает с четвёртым.

3. Через многочлены

Рассмотрим сумму геометрической прогрессии со знаменателем (1+x)(1+x):

(1+x)k+(1+x)k+1+(1+x)k+2+⋯+(1+x)n+k=(1+x)n+k+1−(1+x)kx.(1+x)^k+(1+x)^{k+1}+(1+x)^{k+2}+\dots+(1+x)^{n+k}=\frac{(1+x)^{n+k+1}-(1+x)^k}{x}.

(Сумма прогрессии равна последний член⋅знаменатель−первый члензнаменатель−1\dfrac{\text{последний член}\cdot\text{знаменатель}-\text{первый член}}{\text{знаменатель}-1}; знаменатель 1+x1+x, поэтому внизу (1+x)−1=x(1+x)-1=x.) Чтобы не делить на xx, умножим обе части на xx:

x⋅((1+x)k+⋯+(1+x)n+k)=(1+x)n+k+1−(1+x)k.x\cdot\Bigl((1+x)^k+\dots+(1+x)^{n+k}\Bigr)=(1+x)^{n+k+1}-(1+x)^k.

Теперь сравним коэффициенты при xk+1x^{k+1}.

  • Слева умножение на xx сдвигает все степени на единицу: коэффициент при xk+1x^{k+1} равен коэффициенту при xkx^k в скобке. А в скобке слагаемое (1+x)k+i(1+x)^{k+i} даёт при xkx^k число (k+ik)\dbinom{k+i}{k}. Поэтому слева получаем ∑i=0n(k+ik)\sum_{i=0}^{n}\dbinom{k+i}{k}.
  • Справа у (1+x)n+k+1(1+x)^{n+k+1} коэффициент при xk+1x^{k+1} равен (n+k+1k+1)\dbinom{n+k+1}{k+1}, а у (1+x)k(1+x)^k такой степени нет (наивысшая степень kk), поэтому вычитается 00.

Значит, ∑i=0n(k+ik)=(n+k+1k+1)\sum_{i=0}^{n}\dbinom{k+i}{k}=\dbinom{n+k+1}{k+1}. □\square

Примеры

1. ∑i=04(2+i2)=1+3+6+10+15=35=(73)\sum_{i=0}^{4}\dbinom{2+i}{2}=1+3+6+10+15=35=\dbinom73.

2. Сумма первых натуральных чисел. Возьмём k=1k=1 и заменим nn на n−1n-1: ∑i=0n−1(1+i1)=1+2+⋯+n=(n+12)=n(n+1)2\sum_{i=0}^{n-1}\dbinom{1+i}{1}=1+2+\dots+n=\dbinom{n+1}{2}=\dfrac{n(n+1)}2. Например, 1+2+⋯+100=(1012)=50501+2+\dots+100=\dbinom{101}2=5050.

3. 1+3+6+10+15+21=(83)=561+3+6+10+15+21=\dbinom83=56: это сумма (22)+(32)+⋯+(72)\dbinom22+\dbinom32+\dots+\dbinom72.

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

  • Идти по строке, а не по диагонали. В сумме слагаемые стоят вдоль диагонали (нижнее число kk постоянно); сумма строки — это 2n2^n.
  • Ошибиться в нижнем индексе ответа. Ответ (n+k+1k+1)\dbinom{n+k+1}{k+1}, а не (n+k+1k)\dbinom{n+k+1}{k}: нижнее число увеличивается на единицу.
  • Не начать с края. Диагональ суммируется от (kk)=1\dbinom kk=1; если начать позже, нужно вычесть недостающую часть.
  • Потерять слагаемое. Слагаемых n+1n+1: i=0,1,…,ni=0,1,\dots,n.

Проверь себя

1. Вычислите ∑i=05(3+i3)\sum_{i=0}^{5}\dbinom{3+i}{3}.

Решение

k=3k=3, n=5n=5: (5+3+13+1)=(94)=126\dbinom{5+3+1}{3+1}=\dbinom94=126. Проверка: 1+4+10+20+35+56=1261+4+10+20+35+56=126.

2. Вычислите 1+2+3+⋯+1001+2+3+\dots+100, опираясь на формулу.

Решение

1+2+⋯+100=(1012)=101⋅1002=50501+2+\dots+100=\dbinom{101}2=\dfrac{101\cdot100}{2}=5050.

3. Найдите (33)+(43)+(53)+⋯+(103)\dbinom33+\dbinom43+\dbinom53+\dots+\dbinom{10}3.

Решение

Диагональ k=3k=3, последнее слагаемое с верхним числом 1010: n+k=10n+k=10, значит n=7n=7. По формуле (n+k+1k+1)=(114)=330\dbinom{n+k+1}{k+1}=\dbinom{11}4=330.

4. Сколько существует двухэлементных подмножеств множества {0,1,…,n}\{0,1,\dots,n\}, у которых наибольший элемент равен mm? Сколько всего подмножеств при n=9n=9?

Решение

Если наибольший элемент mm, второй элемент — любое из mm чисел 0,…,m−10,\dots,m-1: mm подмножеств. Всего при n=9n=9: 1+2+⋯+9=(102)=451+2+\dots+9=\dbinom{10}{2}=45.

Итог

  • Сумма чисел вдоль диагонали треугольника Паскаля равна числу, стоящему на шаг ниже и правее: ∑i=0n(k+ik)=(n+k+1k+1)\sum_{i=0}^{n}\dbinom{k+i}{k}=\dbinom{n+k+1}{k+1}.
  • Объяснение 1: подмножества из k+1k+1 числа делятся по наибольшему элементу.
  • Объяснение 2: правило Паскаля превращает сумму в «цепочку».
  • Объяснение 3: сумма прогрессии (1+x)k+⋯+(1+x)n+k(1+x)^k+\dots+(1+x)^{n+k} и коэффициент при xkx^k.
ПрактикаЗагружаем тест…