Математи́чна інду́кція — це застосування принципу індукції для доведення теорем у математиці. Зазвичай полягає в доведенні правильності твердження стосовно одного з натуральних чисел, а потім всіх наступних.
Принцип індукції полягає в тому, що нескінченна послідовність тверджень , , правильна якщо:
- — правильне, та
- із правильності випливає правильність (істинність) для всіх 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 .
Література
Вікіпідручник має книгу на тему Знайомство з методом математичної індукції |
- (Н. Я. Виленкин). Индукция. Комбинаторика. — Пособие для учителей. — М. : Просвещение, 1976. — 48 с.
- Л. И. Головина, И. М. Яглом. Индукция в геометрии. — , 1961. — Т. 21. — 100 с. — ().
- Р. Курант, Г. Роббинс. Глава I, § 2 // Что такое математика?
- И. С. Соминский. Метод математической индукции. — Наука, 1965. — Т. 3. — 58 с. — ().
Відеоматеріали
Див. також
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет