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

Принцип індукції полягає в тому, що нескінченна послідовність тверджень , , правильна якщо:
- — правильне, та
- із правильності випливає правильність (істинність) для всіх k.
Індуктивне доведення наочно може бути представлене у вигляді т.зв. принципу доміно. Нехай довільне число кісточок доміно виставлено в ряд таким чином, що кожна кісточка, падаючи, обов'язково перекине наступну за нею кісточку (це індукційний перехід). Тоді, якщо ми штовхнемо першу кісточку (це база індукції), то всі кісточки в ряду впадуть.
На практиці використовується, щоб довести істинність певного твердження для всіх натуральних чисел. Для цього спочатку перевіряється істинність твердження за номером 1 - база (базис) індукції, а потім доводиться, що, якщо правдиве твердження з номером n, то правдиве й наступне твердження за номером n + 1 - крок індукції, або індукційний перехід.
Формулювання
ред.Припустимо, що потрібно встановити справедливість нескінченної послідовності тверджень, пронумерованих натуральними числами: .
Припустимо, що
Тоді всі твердження нашої послідовності є істинними. |
Логічною підставою для цього методу докази слугує так звана аксіома індукції, п'ята з аксіом Пеано, що визначають натуральні числа. Правильність методу індукції еквівалентна тому, що в будь-якій непорожній підмножині натуральних чисел існує мінімальний елемент.
Принцип повної математичної індукції
ред.Існує також варіація, так званий принцип повної математичної індукції. Ось його строге формулювання:
Нехай є послідовність тверджень , , , . Якщо для будь-якого натурального з того, що істинні всі , , , , , випливає також істинність , то всі твердження в цій послідовності істинні, тобто . |
У цій варіації база індукції виявляється зайвою, оскільки є тривіальним окремим випадком індукційного переходу. Дійсно, при імплікація еквівалентна . Принцип повної математичної індукції є прямим застосуванням сильнішої трансфінітної індукції.
Принцип повної математичної індукції також еквівалентний аксіомі індукції в аксіомах Пеано.
Історія
ред.Усвідомлення методу математичної індукції окремим методом походить від Блеза Паскаля і Герсоніда, хоча окремі випадки використання цього методу відомі ще в Платона (Діалог Парменід — можливо, міститься на початку приклад неявного індуктивного доведення), Прокла і Евкліда. Сучасну назву методу запровадив британський математик Ауґустус де Морган у 1838 році.
Приклади
ред.Задача. Довести, що, якими б не були натуральне n і дійсне q ≠ 1, справджується рівність
Доведення. Індукція по n.
База, n = 1:
Перехід: припустимо, що
тоді
- ,
що й потрібно було довести.
Коментар: істинність твердження в цьому доведенні — те саме, що й істинність рівності
Варіації та узагальнення
ред.Джерела
ред.- 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 с. — (Популярные лекции по математике).
Відеоматеріали
ред.Див. також
ред.
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |