27. Хоккейная клюшка: суммы вдоль диагонали
Если сложить числа, стоящие подряд вдоль одной диагонали треугольника Паскаля, начиная с края, то сумма окажется следующим числом — на шаг вниз и вбок: . Картинка похожа на клюшку для хоккея: длинная ручка из слагаемых и «крюк» с суммой.
Что пригодится из прошлого: бином и — для доказательства через коэффициенты; правило Паскаля — для второго доказательства; сочетания. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Клюшка в треугольнике Паскаля
Возьмём диагональ треугольника Паскаля: числа , то есть . Сложим: . И число стоит на шаг вниз и вправо от последнего слагаемого. Слагаемые и сумма отмечены скобками (показана левая часть треугольника: справа числа повторяются зеркально):
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]
Теорема. Для любых
Слева слагаемые идут по диагонали: верхний индекс растёт на единицу, нижний не меняется. Сумма справа получается из последнего слагаемого переходом : оба индекса растут на единицу.
Почему это верно: три доказательства
1. Выбор по наибольшему элементу
Рассмотрим множество из элементов и выберем в нём числа. Всего способов. А теперь разобьём все такие подмножества по наибольшему элементу .
Если наибольший элемент равен , остальные элементов выбираются из чисел , а их штук: способов. Наибольший элемент не может быть меньше (иначе не хватит чисел), поэтому . Для это двухэлементные подмножества множества :
- наибольший элемент : {0, 1} — всего 1
- наибольший элемент : {0, 2}, {1, 2} — всего 2
- наибольший элемент : {0, 3}, {1, 3}, {2, 3} — всего 3
- наибольший элемент : {0, 4}, {1, 4}, {2, 4}, {3, 4} — всего 4
Всего подмножеств: 10.
Группы не пересекаются, и вместе они содержат все подмножества. Значит,
2. Цепочка по правилу Паскаля
По правилу Паскаля . Перепишем: . Каждое слагаемое — разность двух чисел «следующей» диагонали , стоящих подряд, и при сложении всё, кроме краёв, сокращается:
| Сумма | |||
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | 3 | 4 | 4 |
| 2 | 6 | 10 | 10 |
| 3 | 10 | 20 | 20 |
| 4 | 15 | 35 | 35 |
Каждая частичная сумма в точности равна числу следующей диагонали. Это свойство видно прямо в таблице: третий столбец совпадает с четвёртым.
3. Через многочлены
Рассмотрим сумму геометрической прогрессии со знаменателем :
(Сумма прогрессии равна ; знаменатель , поэтому внизу .) Чтобы не делить на , умножим обе части на :
Теперь сравним коэффициенты при .
- Слева умножение на сдвигает все степени на единицу: коэффициент при равен коэффициенту при в скобке. А в скобке слагаемое даёт при число . Поэтому слева получаем .
- Справа у коэффициент при равен , а у такой степени нет (наивысшая степень ), поэтому вычитается .
Значит, .
Примеры
1. .
2. Сумма первых натуральных чисел. Возьмём и заменим на : . Например, .
3. : это сумма .
Частые ошибки
- Идти по строке, а не по диагонали. В сумме слагаемые стоят вдоль диагонали (нижнее число постоянно); сумма строки — это .
- Ошибиться в нижнем индексе ответа. Ответ , а не : нижнее число увеличивается на единицу.
- Не начать с края. Диагональ суммируется от ; если начать позже, нужно вычесть недостающую часть.
- Потерять слагаемое. Слагаемых : .
Проверь себя
1. Вычислите .
Решение
, : . Проверка: .
2. Вычислите , опираясь на формулу.
Решение
.
3. Найдите .
Решение
Диагональ , последнее слагаемое с верхним числом : , значит . По формуле .
4. Сколько существует двухэлементных подмножеств множества , у которых наибольший элемент равен ? Сколько всего подмножеств при ?
Решение
Если наибольший элемент , второй элемент — любое из чисел : подмножеств. Всего при : .
Итог
- Сумма чисел вдоль диагонали треугольника Паскаля равна числу, стоящему на шаг ниже и правее: .
- Объяснение 1: подмножества из числа делятся по наибольшему элементу.
- Объяснение 2: правило Паскаля превращает сумму в «цепочку».
- Объяснение 3: сумма прогрессии и коэффициент при .
