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

Індуктивна множина

Математична індукція — це фундаментальний принцип, що використовується для строгого доведення тверджень щодо натуральних чисел. Підмножина \( A \subseteq \mathbb{R} \) називається індуктивною, якщо вона задовольняє наступні дві умови:

  • \( 0 \in A \).
  • \( \forall \, x \in A\) випливає, що \(x + 1 \in A \).

Іншими словами, індуктивна множина містить елемент \( 0 \) і замкнена відносно операції додавання \( 1 \).

Нехай \( A, B \subseteq \mathbb{R} \) — дві індуктивні множини. Тоді їх перетин \( A \cap B \) також є індуктивною множиною. Оскільки \( A \) та \( B \) є індуктивними, маємо:

  • \( 0 \in A \) та \( 0 \in B \), отже \( 0 \in A \cap B \).
  • Якщо \( x \in A \cap B \), то \( x \in A \) та \( x \in B \). За індуктивною властивістю, \( x + 1 \in A \) та \( x + 1 \in B \), звідси \( x + 1 \in A \cap B \).

Отже, \( A \cap B \) задовольняє умови індуктивної множини. Зокрема, множина натуральних чисел \( \mathbb{N} \subseteq \mathbb{R} \) сама є індуктивною множиною, і більш точно, вона є найменшою індуктивною множиною, будучи перетином усіх індуктивних підмножин \( \mathbb{R} \).

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

Виходячи з формального означення індуктивної множини, розглянемо множину \( A \subseteq \mathbb{N} \), визначену властивістю \( p(n) \), таку що \(A = \lbrace n \in \mathbb{N} \mid p(n) \rbrace\). Припустимо, що виконуються наступні умови:

  • \( p(0) \) є істинним, тобто \( 0 \in A. \)
  • \( p(n) \rightarrow p(n+1) \, \forall \ n \in \mathbb{N}, \) тобто, якщо \( n \in A \), то \( n+1 \in A.\)

Таким чином, \( p(n) \) є істинним для кожного \( n \in \mathbb{N}.\)

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

  • Базовий крок полягає у перевірці того, що \( p(0) \) виконується, тобто що \( 0 \) належить \( A \).
  • Індуктивний крок полягає у доведенні того, що щоразу, коли \( p(n) \) є істинним для деякого \( n \in \mathbb{N} \), випливає, що \( p(n+1) \) також є істинним, забезпечуючи тим самим, що \( n+1 \in A \).

Приклад 1

Розглянемо практичне застосування принципу математичної індукції, довівши наступне твердження (сума перших \( n \) натуральних чисел):

\[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \quad \forall \, n \in \mathbb{N} \]

Спочатку розглянемо базовий крок. Для \( n = 0 \) ліва частина є порожньою сумою, яка за домовленістю дорівнює \( 0 \). Права частина дає:

\[ \frac{0(0+1)}{2} = 0 \]

Таким чином, формула виконується при \( n = 0 \).

Тепер перейдемо до індуктивного кроку. Припустимо, що формула є істинною для деякого довільного \( k \in \mathbb{N} \); тобто припустимо:

\[ \sum_{i=1}^{k} i = \frac{k(k+1)}{2}. \]

За цього припущення ми повинні довести, що формула також виконується для \( k+1 \). Починаючи з лівої частини:

\[ \sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1). \]

Спрощуючи, отримуємо:

\[ \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}. \]

Це точно права частина формули при \( n = k+1 \). Оскільки твердження виконується для \( n = 0 \) і його справедливість для \( n = k \) тягне за собою його справедливість для \( n = k+1 \), за принципом математичної індукції формула є істинною для кожного натурального числа \( n \).

Звідси випливає, що формула виконується для кожного \( n \in \mathbb{N} \).

Застосування: подільність

Покажемо, що вираз \( n^3 - n \) ділиться на \( 3 \) для кожного \( n \in \mathbb{N} \). Почнемо з базового кроку. Для \( n = 0 \) маємо \( 0^3 - 0 = 0 \), і \( 3 \mid 0 \) виконується тривіально, оскільки \( 0 = 3 \cdot 0. \)

Тепер перейдемо до індуктивного кроку. Припустимо, що \( 3 \mid k^3 – k \) для деякого \( k \in \mathbb{N} \), тобто \( k^3 – k = 3m \) для деякого цілого числа \( m \). За цієї гіпотези ми хочемо показати, що подільність на \( 3 \) переноситься на наступний член, тобто що \( 3 \mid (k+1)^3 - (k+1) \). Розкриваючи вираз, отримуємо:

\[ \begin{align} (k+1)^3 – (k+1) &= k^3 + 3k^2 + 3k + 1 – k – 1 \\[6pt] &= (k^3 – k) + 3k^2 + 3k \end{align} \]

За індуктивною гіпотезою, \( k^3 - k = 3m \), тому вираз стає:

\[ \begin{align} (k+1)^3 – (k+1) &= 3m + 3k^2 + 3k \\[6pt] &= 3(m + k^2 + k) \end{align} \]

Оскільки \( m + k^2 + k \in \mathbb{Z} \), випливає, що \( 3 \mid (k+1)^3 – (k+1) \). За принципом індукції твердження виконується для кожного \( n \in \mathbb{N} \).

Застосування: нерівність

Покажемо, що \( 2^n > n \) для кожного \( n \in \mathbb{N} \). Ця нерівність виражає той факт, що експоненціальне зростання врешті-решт і назавжди домінує над лінійним зростанням — закономірність, яку індукція точно фіксує: щойно нерівність виконується на даному кроці, мультиплікативна природа лівої частини гарантує її виконання на наступному.

Почнемо з базового кроку. Для \( n = 0 \) маємо \( 2^0 = 1 > 0 \), отже нерівність виконується.

Індуктивний крок здійснюється наступним чином. Припустимо, що \( 2^k > k \) для деякого \( k \in \mathbb{N} \). Мета — показати, що \( 2^{k+1} > k+1 \). Розглянемо ліву частину:

\[ \begin{align} 2^{k+1} &= 2 \cdot 2^k \\ &> 2k \\ &= k + k \end{align} \]

Оскільки \( k \geq 0 \), маємо \( k + k \geq k + 1 \) для кожного \( k \geq 1 \), а випадок \( k = 0 \) вже покрито базовим кроком. Отже, \( 2^{k+1} > k + 1 \), і за принципом індукції нерівність виконується для кожного \( n \in \mathbb{N} \).

Застосування: геометричний ряд

Покажемо, що для будь-якого дійсного числа \( r \neq 1 \) і кожного \( n \in \mathbb{N} \):

\[ \sum_{i=0}^{n} r^i = \frac{r^{n+1} - 1}{r - 1} \]

Ця тотожність є замкненою формою часткової суми геометричної послідовності, і індукція забезпечує чіткий шлях до її перевірки. Почнемо з базового кроку. Для \( n = 0 \) ліва частина дає \( r^0 = 1 \), а права частина дає:

\[ \frac{r^1 – 1}{r – 1} = 1 \]

Формула виконується для \( n = 0 \).

Індуктивний крок здійснюється наступним чином. Припустимо, що формула виконується для деякого \( k \in \mathbb{N} \), тобто:

\[ \sum_{i=0}^{k} r^i = \frac{r^{k+1} – 1}{r – 1} \]

Ми хочемо показати, що вона виконується для \( k + 1 \). Починаючи з лівої частини:

\[ \begin{align} \sum_{i=0}^{k+1} r^i &= \sum_{i=0}^{k} r^i + r^{k+1} \\[6pt] &= \frac{r^{k+1} – 1}{r – 1} + r^{k+1} \end{align} \]

Зводячи два доданки до спільного знаменника:

\[ \begin{align} \frac{r^{k+1} - 1}{r - 1} + r^{k+1} &= \frac{r^{k+1} – 1 + r^{k+1}(r-1)}{r – 1} \\[6pt] &= \frac{r^{k+2} - 1}{r - 1} \end{align} \]

Це точно права частина формули при \( n = k+1 \). За принципом індукції тотожність виконується для кожного \( n \in \mathbb{N} \).

Вибрані джерела