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

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

Метод математичної індукції    еквівалентний    такій    аксіомі:    в    довільній непорожній множині натуральних чисел є найменше.

Задача. Доведіть, що будь-яку суму в копійках, починаючи з 8 копійок можна розміняти за допомогою двох номіналів в 3 коп та 5 коп.

Доведення. Індукцію введемо по числу копійок. База індукції це сума в 8 коп. Очевидно її можна сплатити отак:

 3+5 = 8.

3+3+3 = 9.

5+5 = 10.

Тоді, якщо  натуральне число 3 додавати до усіх трьох виразів, можна отримати наступні  три послідовні натуральні числа, більше 8, тобто

(3+5) + 3 = 11.

(3+3+3) + 3  = 12.

(5+5) + 3   = 13.

І так далі …

Тому можна записати три послідовні натуральні числа таким чином:

(3+5) + 3n = 8 + 3n.

(3+3+3) + 3n = 9 + 3n.

(5+5) + 3n  = 10 + 3n.

Тут n – довільне натуральне число.

Можна застосувати такі індуктивні міркування. Припустимо, що нам вдалося сплатити суму в п копійок вказаними монетами. Отже серед монет вже є по 5 коп. або по 3 коп. Якщо серед них є монета в 5 коп., то замінимо її на дві монети по 3 коп. і одержимо суму, що виражена наступним числом  п + 1 = р + 5 +1 =  р +3+3).  Якщо ж всі монети суми по 3коп., то їх не менше трьох і  замінивши три монети по 3 коп. на дві монети по 5 коп., ми також  збільшимо суму на 1  тобто п + 1 = р + 3 +3 +3 +1 =  р +5+5.

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

Індукцією називається умовивід, у якому на основі знання частини предметів класу робиться висновок про всі предмети класу, про клас в цілому. Індукція – це умовивід від часткового до загального. Термін “індукція” походить від латинського слова inductio, що означає “наведення”.

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

Неповною індукцією називається умовивід, у якому загальний висновок виводиться із засновків, котрі не охоплюють усіх предметів класу.

Індукція через простий перелік – це такий умовивід, у якому загальний висновок про клас предметів робиться на тій підставі, щоб серед спостережуваних фактів не траплялося жодного, який би суперечив узагальненню.

Дедуктивним (від латинського слова deductio – виведення) називається умовивід, у якому висновок про окремий предмет класу робиться на підставі класу в цілому.

У дедуктивному умовиводі думка рухається від загального до окремого, одиничного, тому дедукцію звичайно визначають як умовивід від загального до часткового.

Щоб дійти дедуктивного висновку, необхідно мати подвійне знання, засновки:

1) засновок, що має загальне положення або правило, під яке підводиться частковий випадок; 2) засновок, у якому ідеться про той окремий предмет або частковий випадок, який підводиться під загальне положення.

Дуже важливу роль в комбінаторіці відіграє індуктивний метод обгрунтування правил-алгоритмів та формул.

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

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

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

Можна за допомогою малюнків впевнитися, що формула вірна і для двох або для трьох прямих.

2)Припустимо, що n прямих ділять площину на 1 + 0,5n(n+1) час­тин. Нова (n + 1)-а пряма перетне наявні n прямих у n точках,
що поділять нову пряму на (n + 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)-ий, то згідно принципу математичної індукції, вся послідовність буде означеною. Такий спосіб утворення послідовності називають рекурентним.

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

Отже, як у найпростішій формі формулюється метод математичної індукції?

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

Практична частина заняття.

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

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  - натуральні числа.

                                    Задачі на знаходження сум степенів натуральних чисел.

1. Довести, що при довільному натуральному  к  виконується :
1. 2+4+6+..+ 2к = к(к+1)   (сума перших парних натуральних чисел);
2. 1+3+5+..+ 2к -1 = к²   (сума перших непарних натуральних чисел);
3. 1+2+3+4+..+ к = ?  (сума перших парних натуральних чисел);

Завдання для вироблення умінь та навичок досліджувати та аналізувати.

1. Запишіть множину:

a)      спільних дільників чисел 72 та 96; назвіть цю множину А.

b)     спільних кратних  чисел 12 та 18; назвіть цю множину В.

c)      прямих паралельних прямій y=2x+3; назвіть цю множину C.

d)     прямих паралельних прямій y=2x – 3; назвіть цю множину D;

e)      коренів рівняння (х-1)²  + (х-3)²  + (х-2)²  + (х-4)²  + (х-5)²  = 0; назвіть цю множину Е;

f)       коренів рівняння  -(х-1)²  - (х-3)²  - (х-2)²  - (х-4)²  - (х-5)²  = 15; назвіть цю множину F.

2. Виконайте операції:  перерізу, об'єднання, віднімання, доповнення  над множинами, взятих із завдання 1.

Нерівності, що доводяться методом математичної індукції

1.    Довести, що при  a>=1 та при довільному натуральному k  виконується.  (1+a)^x>=1+ka

2.    Знайти всі такі натуральні к, для яких справедлива нерівність 3k2(k+1)².

3.    Довести, що при довільному натуральному к  виконується k^к+2>2k+5.

4.    Довести, що при довільному натуральному к  виконується 2^кk+1.

5.    Знайти всі такі натуральні к, для яких справедлива нерівність 5^к5k³+2.