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

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

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

Задача. Доведіть, що будь-яку суму в копійках, починаючи з 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.

Олімпіада магічних головоломок

Способи узагальнення послідовності Фібоначчі

Перший спосіб узагальнення послідовностей Фібоначчі

Означення. Узагальненою послідовністю Фібоначчі 
 A_р(х₁, х₂, …, х_q )   р- ціле число,  q- натуральне число
із  q змінними   називають таку закономірність утворення чисел, котра задається рекурентною формулою у вигляді суми двох членів послідовності, які знаходяться на певній відстані один від одного:

                        A_р= A_р-1 + A_р-q,

де одразу відомі q-перших членів послідовності, а саме 

A₁= х₁, 

A₂= х₂, 

…, 

A_q= х_{q ,} 

де  { х₁, х₂, …, х_q } - дійсні числа, q- ціле число.

Приклади узагальнених послідовностей Фібоначчі:

A_р= A_р-1 + A_р-q, 1)Якщо q=2,  тоді A_р= A_р-1 + A_р-2, де

A₁=1;  

A₂=1;  

A₃=2;  

A₄=3, …  - послідовність Фібоначчі;

2)Якщо q=3,  тоді A_р= A_р-1 + A_р-3, де змінні члени  узагальненої послідовності Фібонначчи:

A₁=k;  

A₂=m;  

A₃=n;  

 де {k, m, n} - дійсні числа, р -ціле число,  тоді  отримаємо наступні члени послідовності із  змінними в обидві сторони, з додатним індексом або від'ємним індексом:

……………………….

A_-11=-8k+4m+n;

A_-10=k-8m +5n

A_-9=5k+m-3n;

A_-8=-3k+5m-2n;

A_-7=-2k-3m+3n

A_-6=3k-2m;

A_-5=3m-2n;

A_-4=n-2k;

A_-3=n-2m+k;

A_-2=k-n+m;

A_-1=m-k;

A₀=n-m;

A₁=k;  

A₂=m;  

A₃=n;   

A₄=n+k;

A₅=n+k+m;   

A₆=2n+k+m;  

A₇=3n+2k+m;    

A₈=4n+3k+2m;

A₉=6n+4k+3m;

A₁₀=9n+6k+4m;

A₁₁=13n+9k+6m;

…………………………..

 {k, m, n} - дійсні числа.

Другий спосіб узагальнення послідовностей Фібоначчі

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

Послідовності Люка являють собою пари послідовностей ${\displaystyle \{U_{n}(P,Q)\}}$ и ${\displaystyle \{V_{n}(P,Q)\}}$, що задовольняють одному і тому ж рекурентному співвідношенню з коефіцієнтами P і Q:

${\displaystyle U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1,\quad U_{n+2}(P,Q)=P\cdot U_{n+1}(P,Q)-Q\cdot U_{n}(P,Q),\,n\geq 0}$

${\displaystyle V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P,\quad V_{n+2}(P,Q)=P\cdot V_{n+1}(P,Q)-Q\cdot V_{n}(P,Q),\,n\geq 0}$

Приклади

Деякі послідовності Люка носять власні імена:

• ${\displaystyle \{U_{n}(1,-1)\}}$ - числа Фібоначчі
• ${\displaystyle \{V_{n}(1,-1)\}}$ - числа Люка
• ${\displaystyle \{U_{n}(2,-1)\}}$ - числа Пелля
• ${\displaystyle \{V_{n}(2,-1)\}}$ - числа Пелля-Люка
• ${\displaystyle \{U_{n}(3,2)\}}$ - числа Мерсенна
• ${\displaystyle \{U_{n}(1,-2)\}}$ - числа Якобшталя

Характеристичним многочленом послідовностей Люка ${\displaystyle \{U_{n}(P,Q)\}}$ та ${\displaystyle \{V_{n}(P,Q)\}}$ є:

${\displaystyle x^{2}-P\cdot x+Q}$

Його дискримінант ${\displaystyle D=P^{2}-4Q}$ вважається не рівним нулю. Корені характеристичного многочлена

${\displaystyle \alpha ={\frac {P+{\sqrt {D}}}{2}}}$ и ${\displaystyle \beta ={\frac {P-{\sqrt {D}}}{2}}}$

можна використовувати для отримання явних формул:

${\displaystyle U_{n}(P,Q)={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }}={\frac {\alpha ^{n}-\beta ^{n}}{\sqrt {D}}}}$

та

${\displaystyle V_{n}(P,Q)=\alpha ^{n}+\beta ^{n}.~}$

Обчислення значення золотого перетину

Золотий перетин ${\displaystyle \varphi }$ можна обчислити безпосередньо з означення:

${\displaystyle {\frac {a+b}{a}}={\frac {a}{b}}=\varphi \,.}$

Праве рівняння дає ${\displaystyle a=b\varphi \,}$. Підставляючи цю рівність у ліву частину:

${\displaystyle {\frac {b\varphi +b}{b\varphi }}={\frac {b\varphi }{b}}\,.}$

Скоротивши ${\displaystyle b\,}$ отримаємо:

${\displaystyle {\frac {\varphi +1}{\varphi }}=\varphi .}$

Помноживши обидві частини на ${\displaystyle \varphi \,}$ після перестановки отримаємо:

${\displaystyle \varphi ^{2}-\varphi -1=0.}$

Це квадратне рівняння має два розв'язки, один з яких є додатнім

${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\dots \,}$

Зв'язок із числами Фібоначчі

Спіраль Фібоначчі

Золотий перетин є границею відношення двох сусідніх членів у послідовності Фібоначчі:

${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$

При цьому члени послідовності ${\displaystyle {\frac {F_{n+1}}{F_{n}}}}$ збігаються до ${\displaystyle \varphi \,}$ поперемінно: один елемент — знизу, наступний — зверху і т. д. Наприклад

${\displaystyle {\frac {F_{6}}{F_{5}}}={\frac {8}{5}}=1,6<\varphi <{\frac {F_{7}}{F_{6}}}={\frac {13}{8}}=1,625}$

Формула Біне виражає за допомогою ${\displaystyle \varphi \,}$ значення числа Фібоначчі ${\displaystyle F_{n}\,}$ в явному вигляді:

${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\varphi -(-\varphi )^{-1}}}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}}\approx {\frac {\varphi ^{n}}{\sqrt {5}}}\quad (n\geq 1).}$

Окрім цього, послідовні степені числа ${\displaystyle \varphi \,}$ задовільняють рекурентному співвідношенню ідентичному до чисел Фібоначчі:

${\displaystyle \varphi ^{n+2}=\varphi ^{n+1}+\varphi ^{n}.\,}$

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