Метод математичної індукції

Множина натуральних чисел N строго визначається за допомогою аксіом Пеано.

Довідка: Джузеппе Пеано (1858-1932) — італійський математик, якому, крім фор­мулювання аксіом натуральних чисел, належать загальна теорема про існуван­ня розв'язку диференціального рівняння, результати з обґрунтування геометрії. Вперше побудував неперервну криву, що заповнює квадрат.

1. Існує натуральне число 1, яке не є наступним ні за яким натуральним числом (натуральний ряд починається з 1).

2. Кожне натуральне число следує тільки за одним і тілько одним натуральним числом (у натуральному ряді немає повторень).

3. За кожним натуральним числом слідує одне і тільки одне натуральне число (натуральный ряд нескінчений).

4. Аксіома індукції. Нехай М Ì N. Якщо:

1)  1 Î М; (початковий елемент належить підмножині натуральних чисел)

2) Для будь-якого елемента а Î М множині М належить і наступний за а элемент а¹, тоді множина М співпадає з множиною натуральних чисел.

Таким чином, множина  N = { 1, 2, 3, 4,...}.

На аксиомі 4 грунтується спосіб доведення тверджень, який називається метод математичної індукції. Доведення різних тверджень  цим методом проводиться від часткового до загального, а потім робиться висновок про істинність даного твердження.

Доведення методом математичної індукції.

Зауваження. 1.Звертаємо вашу увагу на те, що твердження, яке вдається обгрунтувати методом математичної індукції, як правило, містить в собі  кількісно-впорядковану величину, тобто, числа які належать якійсь відомій класичній числовій множині( це можуть бути різні множини: натуральні числа, цілі числа, раціональні числа, тощо). 

Ця кількісна і впорядкована величина даного твердження (а позначають її через n) називається індуктивною змінною. У доведенні методом математичної індукції міркування проводять саме в полі властивостей індуктивної змінної, використовуючи індуктивний крок: від припущення: правильності даної властивості при п  до чіткого виведення правильності даної властивості при п +1.

 2. Звертаємо вашу увагу на те, що індуктивні твердження, як правило, записують за допомогою  різноманітних математичних моделей: формул, тотожностей, рівностей, правил, в яких присутня індуктивна змінна n, тобто індуктивне твердження «сховане»  в математичній моделі або  конструкції, що відображають  кількісно-впорядковані властивості реальних явищ, кількісних процесів,  або властивості довільних числових систем.

Приклад. Довести, що на площині n прямих, серед яких жодні три не перетинаються в одній точці, а жодні дві не паралельні, поділяють площину на 1 + 0,5n(n + 1) частин.

Доведення (методом математичної індукції):

1)Пряма ділить площину на 2 = 1+0,5 ∙ 1 ∙(1 +1)  частини, тобто
твердження справджується для n = 1.

2)Припустимо, що n прямих ділять площину на 1 + 0,5n(n+1) час­тин.

3) Виконаємо індуктивний крок. Нова (n + 1)-а пряма перетне наявні n прямих у n точках, що поділять нову пряму на (n + 1) частин.

4) Чітко виведемо правильність даної властивості для п +1 прямої. Отже, з наявних 1 + 0,5n(n + 1) частин площини буде перетнуто і поділено новою прямою (n+1). Таким чином, при проведенні цієї прямої кількість частин, на які поділяється площина, зросте на (n + 1) і дорівнюватиме:

1 + 0,5n(n + 1) + (n + 1) = 1 + 0,5(n + 1)(n + 2).

Що і треба було довести.

При розв'язуванні математичних задач  іноді використовують метод математичної індукції.

 Принцип міркувань за індуктивним методом можна викласти в трьох пунктах.

Нехай існує послідовність тверджень Т₁, Т₂, Т₃ , Т₄, … причому:

1) Безпосередньою перевіркою впевнюються, що твердження Т₁, Т₂, Т₃, Т₄, …, Т_к істинні;

2) Припускається, що деяке твердження Т_к істинне, тоді на основі  цього припущення  доводиться, що наступне твердження Т_к+1 також істинне.

3) Тоді стверджується, що всі твердження цієї послідовності істинні.

Такий спосіб міркувань називають методом математичної індукції. При цьому, доведення істинності твердження Т₁, Т₂, Т₃, Т₄, …, Т_к, називають базою індукції, а доведення того, що з істинності твердження  Т_к випливає істинність твердження Г_к+1, називають індукційним кроком.

Метод математичної індукції можна застосовувати не тільки для доведення, але і для означення послідовностей. Якщо ми означимо перший член послідовності, і, припустивши; що к-ий член вже означений, за допомогою нього означимо (к+1)-ий, то згідно принципу математичної індукції, вся послідовність буде означеною. Такий спосіб утворення послідовності називають рекурентним.

Існують й інші форми принципу математичної індукції. Іноді зручно починати індукцію не з доведення істинності Т₁, а з доведення істинності деякого Т_к. Принцип індукції    еквівалентний    такій    аксіомі:    в    довільній непустій множині натуральних чисел є найменше.

Приклад 2. Доведіть, що довільну суму, більшу 7 коп., можна сплатити монетами вартістю в 3 коп. та 5 коп.

Доведення (методом математичної індукції):

Тут демонструється «нестандарте»  використання методу індукції.

Індукцію введіть по числу копійок.  Перевіримо базу індукції. Суму в 8 = 3+5 коп, 9 = 3+3+3 коп і 10 = 5+5 коп очевидно можна сплатити.  А тепер до кожного з трьох попередніх наборів монет додати по одній копійці номіналом в 3 коп. Так отримаємо наступні три числа 11, 12, 13, які можна сплатити двома номіналами, і продовжити так до наперед заданого числа. 

Іншим способом міркування можна дійти того самого висновку. А саме припустимо, що нам вдалося сплатити суму  С в п копійок вказаними монетами. Якщо серед них є монета в 5 коп., то замінимо її на дві монети по 3 коп. і одержимо суму в (N+1) коп. Якщо ж всі монети суми по 3 коп., то їх не менше трьох і, замінивши три монети по 3коп. на дві монети по 5 коп., ми також збільшимо суму на 1 .

Приклад 3. Карта на площині утворена  всілякими прямими. Довести, що для правильного(воно таке, що можна розрізнити кольори по різні сторони від будь-якого відрізка на карті) розфарбування такої карти треба два кольори.

Доведення. Розглянемо площину, яка розділена однією прямою на дві частини. Зрозуміло, що для правильного розфарбування цієї карти потрібно два кольори. Проведемо другу пряму та розфарбуємо нову карту, змінивши всі кольори по одну сторону від нової прямої на протилежні. Потім проведемо третю пряму і так далі. Зрозуміло, що запропонований спосіб можна застосувати для  довільної кількості прямих. Отже методом математичної індукції ми довели, що можна розфарбувати у два кольори всі карти, що утворені прямими.

Приклад 4. Карта на плоскому аркуші паперу утворена  всілякими замкненими кривими без самоперетинів та кривими, що  перетинають весь аркуш від одного краю до іншого. Довести, що для правильного розфарбування такої карти треба два кольори.

Доведення. Розглянемо папір, який розділений однією кривою на дві частини. Зрозуміло, що для правильного розфарбування цієї карти потрібно два кольори. Проведемо другу задану криву та розфарбуємо нову карту, змінивши всі кольори по одну сторону від нової прямої на протилежні. Якщо знову проведена пряма замкнена, то змінити треба кольори на протилежні у тих ділянок, що потрапили у внутрішню частину. Потім проведемо третю пряму і так далі. Зрозуміло, що запропонований спосіб можна застосувати для  довільної кількості прямих. Отже,  методом математичної індукції ми довели, що можна розфарбувати у два кольори всі карти, що утворені такими кривими.

Зауваження. 1.Звертаємо вашу увагу на те, що принцип математичної індукції використовує деяку властивість чисел. Тому дуже важливо спочатку ретельно перевірити цю властивість для усіх без виключення перших значень індуктивної змінної. А потім тільки переходити на доведення індуктивного кроку від п  до п +1. Досить часто виникають помилки саме тому, що не достатньо перевірена властивість для усіх без виключення перших значень індуктивної змінної. Тому будьте обережні. Багато стародавніх математиків припустилися саме цієї помилки.

Вироблення умінь та навичок

Задачі на подільність чисел

1. Довести, що при довільному натуральному  к  число  к³ + 3к² + 5к ділиться на 3.
2. Довести, що при довільному натуральному  к  число  к³ +5к ділиться на 6.
3. Довести, що при довільному натуральному  к  число  к² + к парне.
4. Довести, що при довільному натуральному  к  число  к³ - к ділиться на 6.
5. Довести, що при довільному натуральному  к  число  к⁵ - к ділиться на 30.
6. Довести, що при довільному натуральному  к  число  к⁷ - к ділиться на 7.
7. Довести, що при довільному натуральному  к  число  к³ +11к ділиться на 6.
8. Довести, що при довільному натуральному  к  число  4^к+15к-1 ділиться на 9
9. Довести, що при довільному натуральному  к  число  7^к - 1 ділиться на 6.
10. Довести, що при довільному натуральному  к  число  10^к- 4^к+3к ділиться на 9.
11. Довести, що при довільному натуральному  к  число  2^2к - 1 ділиться на 3.
12. Довести, що при довільному натуральному  к  число  2^2к+1+1 ділиться на 3.
13. Довести, що при довільному натуральному  к  число  5^к+3+11^3к+1 ділиться на 17.
14. Довести, що при довільному натуральному  к  число  2к³+3к²+7к ділиться на 6.
15. Довести, що при довільному натуральному  к  число  к⁶ – к² ділиться на 60.
16. Довести, що при довільному натуральному  к  число  11^6к+3+1 ділиться на 148.
17. Довести, що при довільному натуральному  к  число  10^к+18к -28 ділиться на 27.
18. Довести, що при довільному натуральному  к  число  10^к+18к -28 ділиться на 27.
19. Довести, що при довільному натуральному  к  число  11^к+2+12^2к+1 ділиться на 133.
20. Довести, що при довільному натуральному  к  число  7^2к- 4^2к ділиться на 33.
21. Довести, що при довільному натуральному  к  число  6^{2 к}+ 19^к - 2^к+1 ділиться на 17.
22. Довести, що при довільному натуральному  к  число 7∙ 5^2к+12∙6^к  ділиться на 19.
23. Довести, що при довільному натуральному  к  число 9^к+1-18к-9  ділиться на 18.
24. Довести, що при довільному натуральному  к  число 2^к∙ 5^к+3-125  ділиться на 45.
25. Довести, що при довільному натуральному  к  число 7^2к-1  ділиться на 48.
26. Довести, що при довільному натуральному  к  число 6^2к+3^к+2+3^к  ділиться на 11.
27. Довести, що при довільному натуральному  к  число 5^2к+1+3^к+2∙2^к-1  ділиться на 19.
28. Довести, що при довільному натуральному  к  число к³+(к+1)³+(к+2)³ ділиться на 9.
29. Довести, що довільне натуральне m>8 можна подати у вигляді m = 3к+5n , де к і n  - натуральні числа.