- •Мирон Маланюк, Василь Кравчук Метод математичної індукції та елементи комбінаторики
- •Передмова редактора
- •§1. Метод математичної індукції
- •§2. Прості задачі комбінаторного типу
- •§3. Загальні правила комбінаторики
- •§4. Основні поняття комбінаторики
- •4.1. Перестановки
- •4.2. Розміщення
- •4.3. Комбінації
- •4.4. Деякі комбінаторні тотожності
- •§5. Сполуки з повторенням елементів
- •5.1. Перестановки з повтореннями
- •5.2. Комбінації з повтореннями
- •5.3. Розміщення з повтореннями
- •§6. Приклади розв’язування комбінаторних задач
- •§7. Формула бінома Ньютона
- •Заключне зауваження
- •Задачі для самостійного розв’язування Завдання і
- •Обов’язкові задачі
- •Додаткові задачі
- •Завдання 2 Обов’язкові задачі
- •Додаткові задачі
- •Задачі для підготовки до математичних олімпіад
- •Відповіді та вказівки до задач математичних олімпіад
- •Список рекомендованої літератури
- •§1. Метод математичної індукції 8
§7. Формула бінома Ньютона
При розв’язуванні багатьох задач виникає потреба записати n-й степінь двочлена (бінома) a + b в розгорнутому вигляді. Ви вже знаєте, що (а + b)0 1, (а + b)1 а + b, (а + b)2 а2 + 2ab + b2, (а + b)3 а3 + 3а2b + 3аb2 + b3. Перемноживши а + b на (а + b)3, дістанемо:
Аналогічно можна знайти (а + b)5, (а + b)6 тощо. Якщо коефіцієнти розкладу (а + b)п при n 0, 1, 2, … виписувати у порядку зростання показника степеня числа b, то вони утворять нескінченну трикутну таблицю:
Ця таблиця була відома ще арабським математикам у XIII ст. Вперше її властивості детально вивчив французький математик, фізик і філософ Блез Паскаль (1623 –1662). На його честь цю таблицю називаютьтрикутником Паскаля. Умовимося рядок трикутника Паскаля, який відповідаєп 0, називати нульовим, рядок, який відповідаєп 1, — першим і т. д.
З наведеного фрагмента трикутника Паскаля можна побачити такі закономірності:
1. «Бічні сторони» трикутника Паскаля утворені одиницями.
2. Рядки симетричні відносно «висоти», тобто числа, рівновіддалені від початку і від кінця рядка, — однакові.
3. Сума двох сусідніх чисел одного рядка дорівнює числу, яке стоїть під ними в наступному рядку. Наприклад, додавши 1 і 4 з четвертого рядка, дістанемо число 5, яке стоїть під цими числами у п’ятому рядку.
Розглянемо числа:
1,3, 3, 1.
Звернемо увагу на те, що саме такі числа стоять у третьому рядку трикутника Паскаля. Провівши обчислення, можна переконатися, що четвертий рядок трикутника Паскаля утворюють числа Виникає припущення про те, щоn-й рядок трикутника Паскаля утворюють числа
(1)
Зважимо й на те, що з тотожностей 1–3 для кількості комбінацій (див. §4) випливає, що числа мають відзначені вище властивості трикутника Паскаля. Істинність висловленого припущення випливаєз наступної теореми.
Теорема. Які б не були виразиаіbта яке б не було натуральне числоп, справджується така формула (формула бінома Ньютона):
. (2)
■ Доведення проведемо методом математичної індукції.
1. При n 1 формула (2) істинна, оскільки (а + b)1 a + b a + b.
2. Нехай формула (2) є істинною при nm, тобто
Враховуючи це припущення, при n m + 1 матимемо:
Враховуючи, крім того, що і, дістанемо:
Отже, на основі принципу математичної індукції, формула (2) істинна для будь-якого натуральногоn.■
Многочлен, який стоїть у правій частині формули бінома Ньютона, називається розкладом бінома. Згідно з доведеним, коефіцієнтами цього розкладу є числа Через те ці числа називаютьбіно-міальними коефіцієнтами.
Використовуючи формулу бінома Ньютона, можна заповнити 6-й, 7-й і т. д. рядки наведеного вище фрагмента трикутника Паскаля. Зокрема, у шостому рядку стоятимуть числа отже, (a + b)6 a6+ 6a5b+ 15a4b2+ 20a3b3+ 15a2b4+ 6ab5+b6. Однак простіше виписати 6-й рядок трикутника Паскаля, використавши 5-ий його рядок та властивості 1–3 цього трикутника. Подумайте, як це зробити.
З доведеної теореми, як наслідки, випливають такі дві властивості біноміальних коефіцієнтів, про першу з яких уже було згадано у §4.
1.Сума всіх біноміальних коефіцієнтів для бінома степеняnдорівнює 2n.
■ Візьмемо у формулі (2)ab1. Матимемо:
Тому ■
2.Сума біноміальних коефіцієнтів, які стоять на парних місцях, дорівнює сумі біноміальних коефіцієнтів, що стоять на непарних місцях.
■Візьмемо у формулі (2)a1,b–1. Матимемо:
тобто
(3)
Якщо n— парне, то
Якщо ж n— непарне, то ■
Той доданок у розкладі бінома (а+b)n, який містить множникbk, називатимемоk-м членомцього розкладу і позначатимемо символомТk. Наприклад,є нульовим членом,— першим членом, і т. д. Тодізагальний член:
Приклад 1.Знайти член розкладу (x2+x–3)25, який не міститьх.
■Запишемо загальний член розкладу:За умовою задачі має бути: 50 – 5k0, звідкиk10. Отже, десятий член розкладу не міститьx. ■
Приклад 2.Сума біноміальних коефіцієнтів другого і передостаннього членів розкладудорівнює 78. Знайти раціональні члени цього розкладу.
■ За умовою, Розв’яжемо це рівняння (з невідомимn):
Загальний член розкладу має такий вигляд:
де
Для того, аби член Tkбув раціональним, необхідно і достатньо, щоб числобуло цілим. Це може бути лише при тихk, які діляться на 8.Оскільки тоk 0 або k 8. Отже, раціональними членами розкладу є ■
Приклад 3.Довести тотожність
■
За рівністю (3) (див, стор. 36), вираз в останніх дужках дорівнює 0. Тотожність доведено. ■