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

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

Принцип

Основний принцип такий: ми доводимо твердження для якогось першого елемента, у натуральних числах це найчастіше n = 1. Це доводимо простою підстановкою. На наступному етапі, у кроці індукції, ми доводимо імплікацію «якщо твердження виконується для n = a, то воно виконується й для n = a + 1».

З цих двох кроків можна зробити висновок, що твердження виконується для всіх n (з тієї множини, з якою ми зараз працюємо). Чому це так? На початку ми доводимо, що твердження виконується для n = 1. Водночас ми знаємо, що якщо твердження виконується для n = a, то воно виконується й для n = a + 1. Тож виберемо a = 1. Ми знаємо, що для a = 1 твердження виконується, а також що воно виконується для a + 1 = 2. Отже, тепер ми знаємо, що твердження виконується для a = 2. Але оскільки воно виконується й для a + 1, то має виконуватися й для 2 + 1 = 3. І так далі.

Перший приклад

Перший приклад буде тривіальним. Доведемо, що коли до будь-якого парного числа додати двійку, ми знову отримаємо парне число. Оскільки ми працюємо з натуральними числами, запишемо загальне парне число як 2n, де n — натуральне число. Якщо підставити замість n будь-яке натуральне число, у результаті ми отримаємо парне число, це видно з першого погляду. Подільність записують за допомогою вертикальної риски так:

$$2\mid2n$$

Цей запис означає, що двійка ділить вираз 2n націло. Тепер, коли ми вміємо записувати подільність, можемо записати й те, що маємо довести методом математичної індукції.

$$2\mid 2n+2; \quad n\in\mathbb{N}$$

Це ми й маємо довести в першому прикладі, тобто що двійка ділить вираз 2n + 2 — це точно відповідає початковій словесній умові «якщо до будь-якого парного числа додати двійку, ми знову отримаємо парне число».

У базі індукції доведемо це для першого елемента, для одиниці. Підставимо у вираз n = 1:

$$\begin{eqnarray} 2&\mid& 2\cdot1+2\\ 2&\mid& 4 \end{eqnarray}$$

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

$$2\mid2a+2$$

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

$$2\mid2(a+1)+2.$$

Що ми зробили? Замість a ми написали (a + 1). Важливі саме дужки: вираз 2a + 1 + 2 був би неправильним. Ми додаємо одиницю не до всього виразу, а справді робимо з a вираз на одиницю більший, тобто (a + 1). Перетворимо вираз, розкривши дужки.

$$\begin{eqnarray} 2&\mid&2(a+1)+2\\ 2&\mid&2a+2+2
\end{eqnarray}$$

Тепер невеликий відступ про подільність. Якщо маємо два числа, скажімо, p і q, які діляться на якесь число, наприклад r, то й їхня сума ділиться на число r. Отже, виконується:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Можна підставити, наприклад, числа p = 8, q = 20 і r = 4. Бачимо, що четвірка ділить і вісімку, і двадцятку. Так само вона ділить і їхню суму 8 + 20 = 28.

Як це використати в нашому прикладі? Розділимо праву частину на числа p і q так:

$$p=2a+2; \quad q=2$$

Число q, тобто двійка, тривіально ділиться на двійку. А вираз p теж ділиться на два, бо так говорить припущення. Вираз p точно відповідає нашому припущенню, про яке ми припускаємо, що воно істинне. А якщо p ділиться на два і водночас q ділиться на два, то й їхня сума ділиться на два.

Ще раз про це припущення. На початку ми сказали, що припускаємо виконання

$$2\mid2a+2.$$

Тому, коли під час побудови доведення нам трапився вираз 2a + 2, ми могли сказати, що він ділиться на два. Саме тому, що це наше припущення. Це зазвичай найважчий момент методу математичної індукції — зрозуміти, коли і чому можна використовувати припущення індукції.

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

Якщо хочеш, можна розкласти інакше й не використовувати припущення: p = 2n і q = 2 + 2. Число q = 4 тривіально ділиться на два, так само й p = 2n, адже після ділення на два лишається число n, яке натуральне, тобто ціле. Знову ми отримали два вирази, які обидва діляться на два, тож і їхня сума ділиться на два.

В обох випадках ми довели, що

1. твердження виконується для n = 1,
2. якщо твердження виконується для n, то воно виконується й для n + 1.

Звідси вже можна вивести:

• Ми знаємо, що твердження виконується для n = 1.
• Якщо воно виконується для n, то має виконуватися й для n + 1, тобто й для 1 + 1, тобто твердження виконується й для n = 2.
• Якщо воно виконується для n, то має виконуватися й для n + 1, тобто й для 2 + 1, тобто твердження виконується й для n = 3.
• Якщо воно виконується для n, то має виконуватися й для n + 1, тобто й для 3 + 1, тобто твердження виконується й для n = 4.
• Якщо воно виконується для n, то має виконуватися й для n + 1, тобто й для 4 + 1, тобто твердження виконується й для n = 5.
• …

Другий приклад

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

$$2^n\ge2n;\quad n\in\mathbb{N}.$$

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

$$\begin{eqnarray} 2^1&\ge&2\cdot1\\ 2&\ge&2 \end{eqnarray}$$

Це тривіально виконується. Тепер перейдемо до кроку індукції, у якому треба з'ясувати, чи з виконання для n = a випливає виконання для n = a + 1. Отже, наше припущення таке: виконується

$$2^a\ge2a$$

і ми хочемо довести:

$$2^{a+1}\ge2(a+1)$$

Ліву частину спершу розпишемо за правилами дій зі степенями, а в правій частині просто розкриємо дужки.

$$2\cdot2^a\ge2a+2$$

У лівій частині замість множення скористаємося додаванням, а праву залишимо без змін.

$$2^a+2^a\ge2a+2$$

Тепер скористаємося припущенням. Припущення — це висловлення, про яке ми припускаємо, що воно істинне. В обох частинах нерівності маємо по два доданки. Водночас ми знаємо, що

$$\begin{eqnarray} 2^a&\ge&2a\\ 2^a&\ge&2. \end{eqnarray}$$

Перший рядок нам дає припущення, а друге висловлення тривіальне (найменше значення 2^a — при a = 1, і воно дорівнює саме двом). Отже, ми знаємо, що в лівій частині кожен із двох доданків не менший за відповідний доданок у правій частині. Так ми методом індукції довели, що якщо твердження виконується для a, то воно виконується й для (a + 1), а оскільки воно виконується й для одиниці, то твердження істинне.

Третій приклад

Спробуймо довести таке твердження:

$$3\mid n\Rightarrow 3\mid n^2;\quad n\in\mathbb{N}$$

Словами: якщо n ділиться на три, то й n² ділиться на три. Якщо n не ділиться на три, то твердження виконується тривіально (за означенням імплікації), тож ми розглядатимемо лише випадки, коли n ділиться на три. Це дає нам послідовність натуральних чисел a_i = 3, 6, 9, 12, 15… Відтепер ми працюватимемо лише з цією послідовністю a_i.

Доведення індукцією почнемо з бази індукції, тобто з перевірки першого елемента. Нагадую, що ми працюємо з послідовністю a_i, тож беремо перший елемент цієї послідовності, тобто елемент a₁, який дорівнює трьом. Для трійки твердження виконується:

$$3\mid3\Rightarrow 3\mid3^2$$

Тепер перейдемо до кроку індукції. Бачимо, що послідовність a_i можна записати як 3n, де n — натуральне число. Отже, другий елемент на три більший за попередній і так далі. Припустімо, що твердження виконується для n, і треба показати, що воно виконується й для (n + 3), а це правило, яке породжує наступний елемент послідовності, з якою ми працюємо. Спершу запишемо припущення:

$$3\mid n\Rightarrow 3\mid n^2$$

а потім те, що хочемо довести:

$$3\mid (n+3)\Rightarrow 3\mid(n+3)^2.$$

Розкриємо дужки в правій частині за формулою:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

І ми вже майже біля мети. У лівій частині маємо вираз, який напевно ділиться на три, адже n за припущенням ділиться на три (ми беремо лише числа з послідовності a_i), і трійка теж ділиться на три. У правій частині маємо спершу n², яке за припущенням ділиться на три. Справді, ми знаємо, що n ділиться на три, а припущення говорить, що коли n ділиться на три, то й n² ділиться на три:

$$3\mid n\Rightarrow 3\mid n^2$$

Далі йде вираз 6n, який тривіально ділиться на три. Можна уявити це як скорочення дробу:

$$\frac{6n}{3}=2n$$

Змінна n — якесь натуральне число, тож і добуток 2n буде натуральним числом, тобто після ділення на три ми отримали натуральне число, а отже, вираз 6n ділиться на три. А дев'ятка в кінці знову ділиться на три. Твердження виконується для першого елемента і для кроку індукції, отже, воно істинне.

Кількість дужок у виразі

Останній приклад буде дещо незвичним. Спробуймо довести твердження, що кількість дужок у простому виразі завжди парна, щоб було видно, що метод математичної індукції можна застосовувати й у зовсім іншому контексті, а не лише для натуральних чисел. Спершу треба означити, що таке простий вираз. Простий вираз — це:

• натуральне число,
• якщо p — простий вираз, то й (p²) — простий вираз,
• якщо p і q — прості вирази, то й (p + q) — простий вираз.

Отже, простими виразами є: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). А ось ці вирази простими не є:

• 1 + 2 $\rightarrow$ бракує зовнішніх дужок,
• (1 + 2 $\rightarrow$ бракує правої дужки,
• 13² $\rightarrow$ бракує зовнішніх дужок,
• (1 + 2 + 3) $\rightarrow$ бракує дужок, правильно було б записати (1+(2 + 3))

Простий вираз може утворитися, наприклад, так. На початку виберемо простий вираз (a + b). Тепер замість a підставимо простий вираз a = (c + d), отримаємо ((c + d)+b), а замість b підставимо трійку: ((c + d)+3). Замість c підставимо десятку: ((10 + d)+3) і нарешті замість d підставимо (5²): ((10+(5²))+3). Важливо дотримуватися дужок, інакше нічого не вийде.

Тепер доведемо, що простий вираз містить парну кількість дужок (до парних чисел належить і нуль).

У базі індукції виберемо якийсь перший елемент. У цьому випадку першим елементом буде найтривіальніший простий вираз, тобто будь-яке натуральне число. Отже, покладемо

$$j=n;\quad n\in\mathbb{N}.$$

Для виразу j кількість дужок дорівнює нулю, тож перший елемент підходить. У кроці індукції припустимо, що маємо два прості вирази p і q і що обидва мають парну кількість дужок. Тоді треба довести, що й прості вирази (p + q) і (p²) мають парну кількість дужок.

Спершу додавання. Означимо ще функцію k(q), яка повертає кількість дужок виразу q. Тоді вираз (p + q) має k(p)+k(q)+2 дужок. Тобто має на дві дужки більше, ніж сума кількостей дужок виразів p і q. За припущенням і k(p), і k(q) парні, тож коли ми додамо три парні числа, знову отримаємо парне число. Для цього випадку твердження виконується.

Тепер степінь. Знову діє припущення, що простий вираз p містить парну кількість дужок. Тоді вираз (p²) містить k(p)+2 дужок, тобто знову на дві дужки більше, ніж вираз p. І в цьому випадку ми додаємо парні числа, тож результат парний.

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