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

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

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

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

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

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

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

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

Припустимо, що

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

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

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

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

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

Нехай є послідовність тверджень $P_{1}$ , $P_{2}$ , $P_{3}$ , $\ldots$ . Якщо для будь-якого натурального $n$ з того, що істинні всі $P_{1}$ , $P_{2}$ , $P_{3}$ , $\ldots$ , $P_{n-1}$ , випливає також істинність $P_{n}$ , то всі твердження в цій послідовності істинні, тобто $(\forall n\in {\mathbb {N} }){\Big (}(\forall i\in \{1;\dots ;n-1\})P_{i}\longrightarrow P_{n}{\Big )}\longrightarrow (\forall n\in {\mathbb {N} })P_{n}$ .

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

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

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

Джерела

Weisstein, Eric W. (1999). CRC concise encyclopedia of mathematics. Boca Raton, Fla.: CRC Press. ISBN 0-8493-9640-9.

Література

Н.Я. Виленкін. Індукція. Комбінаторика. — Посібник для вчителів. — Просвіта, 1976. — 48 с.
Л.І. Головина, І.М. Яглом. Індукція у геометрії. — Фізматгіз, 1961. — Т. 21. — 100 с. — (Популярні лекції з математики)
Р. Курант, Г. Роббінс. Глава I, § 2 // Що таке математика?.
І.С. Соминський. Метод математичної індукції. — Наука, 1965. — Т. 3. — 58 с. — (Популярні лекції з математики)

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

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.