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

Нехай деяке твердження справедливе в кількох окремих випадках. Розгляд усіх інших випадків або взагалі неможливий, або потребує розгляду великої кількості випадків. Як же дізнатися, чи буде правильним твердження в усіх можливих випадках? Це питання іноді вдається розв’язати, використавши особливий метод міркувань, який називається методом математичної індукції.

Основна заслуга в розробці цього методу належить французьким математикам Блезу Паскалю (1623-1662) і Рене Декарту (1596-1650), а також швейцарському математику Якобу Бернуллі (1654-1705).

В основі методу математичної індукції лежить твердження, яке називається принципом математичної індукції:

Деяке твердження правильне при будь-якому натуральному n, якщо:

1) воно правильне при n = 1;

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

Позначимо Т(n) твердження, яке залежить від натурального числа n.

Доведення методом математичної індукції проводиться за таким алгоритмом:

1) перевірити правильність твердження Т(1);

2) припустити, що правильним є твердження Т(k), k 1;

3) довести, використовуючи це припущення, що правильним буде твердження Т(k+1);

4) зробити висновок, що за принципом математичної індукції твердження Т(n) правильне для будь-якого nN.

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

З’ясуємо основу цього методу.

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

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

2) одиниця є натуральним числом, причому вона не слідує ні за яким натуральним числом;

3) жодне натуральне число не слідує за двома різними натуральними числами;

4) якщо множина А містить одиницю і разом з кожним числом k містить наступне за ним число k′ (чи k+1), то А містить всі натуральні числа.

Четверту аксіому Пеано називають аксіомою математичної індукції – саме на ній оснований метод математичної індукції.

Нехай твердження Т(1) – правильне, а з правильності твердження T(k) слідує правильність твердження T(k+1). Нехай А - множина тих натуральних чисел, для яких правильне T(n). За припущенням 1∈А (твердження правильне при n=1), а з того, що k ∈ A слідує k+1 ∈ A (якщо T(n) правильне при n=k, то воно правильне і при n=k+1). Тоді в силу аксіоми (4) звідси слідує, що А співпадає з множиною всіх натуральних чисел. Значить, T(n) правильне для всіх натуральних чисел.

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

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

при розв’язуванні задач на подільність чисел

Приклад 3.1.

Довести, що значення виразу n3 + 5n ділиться на 6, ∀nN.

Доведення.

При n = 1 значення виразу 13 + 5⋅1 ділиться на 6.

Припустимо, що на 6 ділиться значення виразу k3 + 5k.

Доведемо, що значення виразу (k+1)3 + 5(k+1) також буде
ділитися на 6.

(k+1)3 + 5(k+1) = k3 + 3k2 + 3k + 1 + 5k + 5 = k3 + 5k + 3k2 + 3k + 6 =

= k3 + 5k + 3k (k + 1) + 6.

(k3 + 5k)6 (за припущенням), 3k (k + 1) ділиться на 3, а також на 2, оскільки добуток k (k + 1) двох послідовних натуральних чисел – парний, тобто 3k (k + 1) 6.

Отже, значення виразу (k+1)3 + 5(k+1) ділиться на 6.

Згідно принципу математичної індукції (n3 + 5n) 6 nN.

Приклад 3.2.

Довести, що значення виразу ділиться на 19 при будь-якому натуральному n.

Доведення.

Якщо n = 1, то .

Припустимо, що для деякого натурального k (k ≥ 1) значення виразу ділиться на 19.

Доведемо, що значення виразу також ділиться на 19.

Дійсно,

Зважаючи на те, що і , то і вся сума буде ділитися на 19, а отже, ділиться на 19, тому значення виразу ділиться на 19 при будь-якому натуральному n.Приклад 3.3.

Доведіть, що при будь-якому натуральному n значення виразу 7n⋅23n - 32n кратне 47.

Доведення.

Якщо n = 1, то 7⋅23 - 32 = 47 47.

Припустимо, що для деякого натурального значення k (k ≥ 1) значення виразу 7k⋅23k - 32k ділиться на 47.

Доведемо, що значення виразу 7k+1⋅23(k+1) - 32(k+1) ділиться на 47.

7k+1⋅23(k+1) - 32(k+1) = 7⋅7k⋅23k⋅23 – 32k⋅32 = 56⋅7k⋅23k - 9⋅32k =

Оскільки кожний доданок останньої суми ділиться на 47, то і сама сума, а отже, і значення виразу 7k+1⋅23(k+1) - 32(k+1) ділиться на 47.

Згідно принципу математичної індукції значення виразу 7n⋅23n - 32n ділиться на 47 при будь-якому натуральному значенні n.

Приклад 3.4.

Доведіть, що при будь-якому натуральному n значення виразу 22n-1 – 9n2 + 21n – 14 ділиться на 27.

Доведення.

Якщо n = 1, то 22⋅1-1 – 9⋅12 + 21⋅1 – 14 = 0 27.

Припустимо, що (22k-1 – 9k2 + 21k – 14) 27.

Доведемо, що на 27 буде ділитися значення виразу

22(k+1)-1 – 9(k+1)2 + 21(k+1) – 14.

22(k+1)-1 – 9(k+1)2 + 21(k+1) – 14 = 22k+1 – 9k2 – 18k – 9 + 21k + 21 – 14=

=22k-1+2 – 9k2 + 3k – 2 = 4⋅22k-1 – 9k2 + 3k – 2 =

= .

Таким чином, значення виразу 22(k+1)-1 – 9(k+1)2 + 21(k+1) – 14
ділиться на 27.

Згідно принципу математичної індукції значення виразу
22n-1 – 9n2 + 21n – 14 ділиться на 27 при n N.

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

при розв’язуванні задач на знаходження сум та добутків

Приклад 4.1.

Знайти суму перших n чисел натурального ряду.

Розв’язання.

Спочатку знайдемо суми двох, трьох, чотирьох, п’яти перших натуральних чисел, щоб виявити певну закономірність:

1 + 2 = 3, коли n = 2 ;

1 + 2 + 3 = 6, коли n = 3 ;

1 + 2 + 3 + 4 = 10, коли n = 4 ;

1 + 2 + 3 + 4 + 5 = 15, коли n = 5 .

Таким чином можна припустити, що

1 + 2 + 3 + ... + n = .

Доведемо цю рівність методом математичної індукції.

Якщо n = 1, то - правильне твердження.

Припустимо, що правильною є рівність:

Доведемо, що .

1 + 2 + 3 + ...+(k+1) = 1 + 2 + 3 + k + (k +1) =

Отже, згідно принципу математичної індукції рівність

1 + 2 + 3 + ... + n = правильна при n N.

Приклад 4.2.

Знайти суму перших n непарних чисел.

Розв’язання.

Розглянемо послідовні суми непарних чисел:

1, 1 + 3, 1 + 3 + 5, 1 + 3 + 5 + 7, …

Отримаємо числа 1, 4, 9, 16, … , які є квадратами натуральних чисел 1, 2, 3, 4.

Отже, можна припустити, що для будь-якого натурального числа n правильною буде рівність:

1 + 3 + 5 + … + (2n – 1) = n2.

Доведемо цю рівність методом математичної індукції.

Якщо n = 1, то 1 = 12 – твердження правильне.

Припустимо, що твердження правильне при будь-якому натуральному k , тобто 1 + 3 + 5 + … + (2(k –1) –1) + (2k – 1) = k2.

Доведемо правильність твердження для k + 1.

1 + 3 + 5 + … + (2(k –1) –1) + (2k –1) + (2(k +1) -1) = k2 + (2(k +1) –1) = k2 + 2k + 1 = (k +1)2.

Отже, згідно принципу математичної індукції

1 + 3 + 5 + … + (2n – 1) = n2 – правильна рівність при nN.

Приклад 4.3.

Знайти суму .

Розв’язання.

Спочатку знайдемо суми одного, двох, трьох і чотирьох доданків:

Можна припустити, що

Для доведення цієї гіпотези використаємо метод математичної індукції:

1) Якщо n = 1, то - твердження правильне.

2) Припустимо, що твердження правильне при n = k (k ≥1), тобто

Використовуючи припущення, доведемо, що твердження буде правильним і при n = k + 1, тобто:

Отже, рівність правильна при будь-якому натуральному n.

Деякі твердження справедливі не для всіх натуральних n, а лише для натуральних n, починаючи з деякого числа m. Такі твердження іноді вдається довести методом, який дещо відрізняється від самого методу математичної індукції, але дуже схожим з ним. Він базується на такому принципі:

Твердження правильне при всіх натуральних значеннях n ≥ m, якщо:

1) воно правильне при n = m;

2) із правильності цього твердження при n = k, де k ≥ m, слідує, що воно правильне і при n = k +1.

Це твердження називається узагальненим принципом математичної індукції.

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

Доведення узагальненим методом математичної індукції проводиться за таким алгоритмом:

1) перевірити правильність твердження Т(m);

2) припустити, що правильним є твердження T(k), де k ≥ m;

3) довести, що правильним є твердження Т(k+1);

4)зробити висновок, що згідно узагальненого принципу математичної індукції твердження Т(n) правильне при всіх натуральних значеннях n ≥ m.

Приклад 4.4.

Знайти добуток , n ≥ 2.

Розв’язання.

Розглянемо спочатку такі добутки:

Робимо індуктивне припущення, що .

Доведемо формулу узагальненим методом математичної індукції.

1) Якщо n = 2, то .

2) Нехай твердження правильне при n = k (k ≥2), тобто

Доведемо, виходячи з цього, що правильним буде твердження:

тобто

Отже, формула правильна при всіх натуральних n ≥ 2.

Методом математичної індукції доводяться також твердження, правильні при всіх цілих від’ємних числах, а також твердження, правильні на множині цілих чисел, починаючи з деякого цілого m (провівши заміну
n = - m ). В останньому випадку доведення будується на наступному узагальненні принципу математичної індукції.

Деяке твердження Т(n) правильне при всіх цілих n ≥ m, якщо воно:

1) правильне при n = m;

2) із правильності цього твердження при n = k, де k Z, k ≥ m, слідує, що воно правильне для n = k +1

Доведення проводиться за таким алгоритмом:

перевірити правильність твердження Т(m);
припустити, що правильним є твердження T(k), де k ≥ m;
довести, використовуючи припущення, що правильним є твердження T(k+1);
зробити висновок, що твердження T(n) правильне при всіх цілих
n ≥ m.

Приклад 4.5.

Довести, що при всіх цілих n-1.

Доведення.

Якщо n = -1, то .

Припустимо, що ,(k≥ -1).

Доведемо, що .

Кожний з доданків ділиться на 16, тому і вся сума ділиться на 16.

Отже, згідно узагальненого принципу математичної індукції

при всіх цілих n-1.

Доведення тотожностей і нерівностей методом математичної індукції

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

Приклад 5.1.

Довести тотожність при nN.

(2 )

Доведення.

При n =1 твердження (2) набуде вигляду:

Нехай твердження (2) є тотожністю при n = k, тобто правильною є рівність:

(3)

Доведемо, використовуючи це припущення, що тотожністю буде рівність:

(4)

Для цього розглянемо різницю лівої та правої частин рівності (4). Якщо різниця буде дорівнювати 0, тоді рівність (4) є правильною. Враховуючи те, що рівність (3) за припущенням – тотожність, різниця лівої та правої частин цієї рівності дорівнює 0. Отже,

Згідно принципу математичної індукції рівність (2) є тотожністю при nN.

Приклад 5.2.

Довести, що для будь-якого натурального числа n правильною є рівність:

Доведення.

Якщо n = 1, то - правильна числова рівність.

Припустимо, що правильною є рівність:

Звідси .

Доведемо, що правильною буде рівність:

Для цього розглянемо різницю лівої та правої частин останньої рівності. Якщо різниця дорівнює 0, то ця рівність правильна.

Згідно принципу математичної індукції рівність:

правильна при ∀ n N.

При доведенні нерівностей використовують властивості нерівностей.

Приклад 5.3.

Довести, що якщо 0 < a < b, то n N an < bn.

Доведення.

1) Якщо n =1, то а < b – нерівність, що доводимо, правильна (це випливає з умови).

2) Нехай правильною є нерівність ak < bk. Так як a > 0 i b > 0, то можна помножити нерівність ak < bk на нерівність а < b і отримаємо правильну нерівність ak+1 < bk+1.

Згідно принципу математичної індукції an < bn, n N.

Приклад 5.4.

Якщо х > -1, то n N

(1 + х)n ≥ 1 + nх (нерівність Бернуллі) (7) Доведення.

Для доведення цієї нерівності застосуємо метод математичної індукції.

Доведення.

1) Якщо n = 1, то маємо (1 + х)1 ≥ 1 + х. Ця нерівність правильна.

2) Нехай (1 + х)k ≥ 1 + kx – правильна нерівність.

Так як 1 + х > 0, то помноживши попередню нерівність на 1 + х, отримаємо правильну нерівність: (1 + х)k+1 ≥ (1 + kх)(1 + х);

(1 + х)k+1 ≥ 1 + (k +1)х + kх2.

Так як kх2 ≥ 0, то звідси слідує

(1 + х)k+1 ≥ 1 + (k +1)х.

Згідно принципу математичної індукції робимо висновок, що нерівність (7) правильна при n N.

Приклад 5.5.

Довести, що для всіх невід’ємних чисел а і b і натурального числа n:

. (8)

Доведення.

1) При n = 1 . Ця нерівність правильна.

2) Нехай нерівність (8) правильна при n = k, тобто

тоді для а ≥ 0 та b ≥ 0 буде правильною нерівність:

(9)

3) Доведемо, використовуючи це припущення, що правильною буде нерівність:

. (10)

Для цього доведемо нерівність .

для а ≥ 0 та b ≥ 0.

Враховуючи нерівності (9) та (10), робимо висновок, що правильною буде нерівність:

Згідно принципу математичної індукції нерівність (8) правильна при
n N.

Приклад 5.6.

Довести, що середнє арифметичне будь-яких n невід’ємних чисел а1, а2, а3, ..., аn не менше їх середнього геометричного, тобто:

(нерівність Коші).

Доведення.

Якщо n = 2, то - правильна нерівність, бо

Припустимо, що нерівність, яку доводимо, правильна для довільних k невід’ємних чисел, тобто:

Доведемо, що правильною буде нерівність:

Переставляючи числа а1, а2, а3, ..., аk , можна досягти того, що число
аk+1 буде найбільшим числом (або одним з найбільших), тобто:

аk+1 а1;

аk+1 а2;

...

аk+1 аk.

Додавши отримані нерівності, матимемо:

k·аk+1 а1+ а2+ а3+ ...+ аk .

Звідси .

Введемо позначення ,

Так як , то , .

Тому ,

Піднесемо до (k+1)-го степеня останню рівність:

Але за припущенням , тому

Звідси .

Згідно принципу математичної індукції:

- правильна нерівність для будь-яких невід’ємних чисел а1, а2, а3, ..., аn , n N, n 2.

Приклад 5.7.

Довести, що ∀ х > 0 і nN має місце нерівність:

Доведення.

а) Якщо n = 1, то початкова нерівність набуває вигляду .

Це правильна нерівність, оскільки .

б) Якщо n = 2, то початкова нерівність набуває вигляду:

Нерівність правильна при ∀ х > 0, значить, вона правильна і при заміні х на х2, тобто .

Додавши до кожної частини останньої нерівності 1, отримаємо:

в) Припустимо, що правильною є нерівність:

, (11)

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

Доведемо, що правильною буде нерівність:

Замінимо в нерівності вираз х на вираз хk+2 .

Тоді . (12)

Додамо почленно нерівності (11) та (12).

Отримаємо:

Отже, результати кроків а) та в) дають можливість зробити висновок про те, що початкова нерівність правильна для будь-якого непарного значення n, так само як і ця нерівність буде правильною і для будь-якого парного числа n згідно пунктів б) та в).

В цілому, згідно принципу математичної індукції можна зробити висновок про те, що нерівність:

правильна ∀ х > 0 і nN.