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

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

Принцип індукції полягає в тому, що нескінченна послідовність тверджень ${\displaystyle P_{i}}$, ${\displaystyle i=1,\dots ,\infty }$, правильна якщо:

1. ${\displaystyle P_{1}}$ — правильне, та
2. із правильності ${\displaystyle P_{k}}$ випливає правильність (істинність) ${\displaystyle P_{k+1}}$ для всіх k.

Індуктивне доведення наочно може бути представлене у вигляді т.зв. принципу доміно. Нехай довільне число кісточок доміно виставлено в ряд таким чином, що кожна кісточка, падаючи, обов'язково перекине наступну за нею кісточку (це індукційний перехід). Тоді, якщо ми штовхнемо першу кісточку (це база індукції), то всі кісточки в ряду впадуть.

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

Припустимо, що потрібно встановити справедливість нескінченної послідовності тверджень, пронумерованих натуральними числами: ${\displaystyle P_{1},P_{2},\ldots ,P_{n},P_{n+1},\ldots }$.

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

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

У цій варіації база індукції виявляється зайвою, оскільки є тривіальним окремим випадком індукційного переходу. Дійсно, при ${\displaystyle n=1}$ імплікація ${\displaystyle (\forall i\in \{1;\dots ;n-1\})P_{i}\longrightarrow P_{n}}$ еквівалентна ${\displaystyle P_{1}}$. Принцип повної математичної індукції є прямим застосуванням сильнішої трансфінітної індукції.

Принцип повної математичної індукції також еквівалентний аксіомі індукції в аксіомах Пеано.

Усвідомлення методу математичної індукції окремим методом походить від Блеза Паскаля і Герсоніда, хоча окремі випадки використання цього методу відомі ще в Платона (Діалог Парменід — можливо, міститься на початку приклад неявного індуктивного доведення), Прокла і Евкліда. Сучасну назву методу запровадив британський математик Ауґустус де Морган у 1838 році.

Задача. Довести, що, якими б не були натуральне n і дійсне q ≠ 1, справджується рівність

${\displaystyle 1+q+q^{2}+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}}.}$

Доведення. Індукція по n.

База, n = 1:

${\displaystyle 1+q={\frac {(1-q)(1+q)}{1-q}}={\frac {1-q^{1+1}}{1-q}}.}$

Перехід: припустимо, що

${\displaystyle 1+q+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}},}$

тоді

${\displaystyle 1+q+\cdots +q^{n}+q^{n+1}={\frac {1-q^{n+1}}{1-q}}+q^{n+1}=}$

${\displaystyle ={\frac {1-q^{n+1}+(1-q)q^{n+1}}{1-q}}={\frac {1-q^{n+1}+q^{n+1}-q^{(n+1)+1}}{1-q}}={\frac {1-q^{(n+1)+1}}{1-q}}}$,

що й потрібно було довести.

Коментар: істинність твердження ${\displaystyle P_{n}}$ в цьому доведенні — те саме, що й істинність рівності

${\displaystyle 1+q+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}}.}$

• Трансфінітна індукція
• Структурна індукція
• Аксіоми Пеано
• Зворотна індукція або Індукція Коші
• Коіндукція

• Доведення
• Дедукція
• Формальна логіка
• Проблема індукції

• Ляшко І. І., Боярчук О. К., Гай Я. Г., Головач Г. П. Математичний аналіз в прикладах і задачах. — 2026. — 2538 с.(укр.)
• Н. Я. Виленкин. Индукция. Комбинаторика. — Пособие для учителей. — М. : Просвещение, 1976. — 48 с.
• Л. И. Головина, И. М. Яглом. Индукция в геометрии. — Физматгиз, 1961. — Т. 21. — 100 с. — (Популярные лекции по математике).
• Р. Курант, Г. Роббинс. Глава I, § 2 // Что такое математика?
• И. С. Соминский. Метод математической индукции. — Наука, 1965. — Т. 3. — 58 с. — (Популярные лекции по математике).

• Курс відеолекцій з математичної індукції українською мовою [Архівовано 1 квітня 2016 у Wayback Machine.]
• Приклади розв'язування задач (відео українською мовою)

Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її.