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

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

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

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

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

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

Формулювання

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

Шаблон:Рамка Припустимо, що

1. Встановлено, що $P_1$ є істинним. (Це твердження називається базою індукції.)
2. Для будь-якого n доведено, що якщо є істинним $P_n$, то є істинним $P_{n+1}$. (Це твердження називається індукційним переходом.)

Тоді всі твердження нашої послідовності є істинними. Шаблон:/рамка

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

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

Існує також варіація, так званий принцип повної математичної індукції. Ось його строге формулювання: Шаблон:Рамка Нехай є послідовність тверджень $P_1$, $P_2$, $P_3$, $\dots$. Якщо для будь-якого натурального $n$ з того, що істинні всі $P_1$, $P_2$, $P_3$, $\dots$, $P_{n-1}$, випливає також істинність $P_n$, то всі твердження в цій послідовності істинні, тобто $(\mathrm{\forall }n\in \mathbb{N})((\mathrm{\forall }i\in \{1;\dots ;n-1\})P_i⟶P_n)⟶(\mathrm{\forall }n\in \mathbb{N})P_n$. Шаблон:/рамка

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

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

Історія

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

Приклади

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

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

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

База, n = 1:

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

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

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

тоді

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

$=\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}$,

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

Коментар: істинність твердження $P_n$ в цьому доведенні — те саме, що й істинність рівності

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

Варіації та узагальнення

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

Джерела

• Шаблон:Cite book

Література

• Шаблон:Книга-ру
• Шаблон:Книга-ру
• Шаблон:Книга-ру
• Шаблон:Книга-ру

Відеоматеріали

• Курс відеолекцій з математичної індукції українською мовою Шаблон:Webarchive
• Приклади розв'язування задач (відео українською мовою)

Див. також

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