Перегляд вихідного коду сторінки Математична індукція

{{Otheruses|Індукція}}

[[Файл:Dominoeffect.png|right|300px]]
'''Математи́чна інду́кція'''&nbsp;—  це застосування ''[[принцип]]у індукції'' для [[доведення]] [[Теорема|теорем]] у [[Математика|математиці]]. Зазвичай полягає в доведенні правильності твердження стосовно одного з [[натуральні числа|натуральних чисел]], а потім всіх наступних.

Принцип індукції полягає в тому, що нескінченна [[послідовність (математика)|послідовність]] тверджень <math>P_i</math>, <math>i = 1, \dots, \infty</math>, правильна якщо:
# <math>P_1</math>&nbsp;— правильне, та
# із правильності <math>P_k</math> випливає правильність (істинність) <math>P_{k+1}</math> для всіх ''k''.

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

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

== Формулювання ==
Припустимо, що потрібно встановити справедливість нескінченної послідовності тверджень, пронумерованих [[натуральне число|натуральними числами]]: <math>P_1, P_2, \ldots, P_n, P_{n+1}, \ldots</math>.

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

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

=== Принцип повної математичної індукції ===
Існує також варіація, так званий принцип повної математичної індукції. Ось його строге формулювання:
{{Рамка}}
Нехай є послідовність тверджень <math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>\ldots</math>. Якщо для будь-якого натурального <math> n </math> з того, що істинні всі <math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>\ldots</math>, <math>P_{n-1}</math>, випливає також істинність <math>P_n</math>, то всі твердження в цій послідовності істинні, тобто <math>(\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</math>.
{{/рамка}}

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

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

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

== Приклади ==
'''Задача.''' Довести, що, якими б не були натуральне ''n'' і дійсне ''q'' ≠ 1, справджується рівність
: <math>1 + q + q^2 +\cdots + q^n = \frac{1 - q^{n + 1}}{1  -q}.</math>

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

''База'', ''n'' = 1:
: <math>1 + q = \frac{(1 - q)(1 + q)}{1 - q}=\frac{1 - q^{1 + 1}}{1 - q}.</math>
''Перехід'': припустимо, що
: <math>1 + q + \cdots + q^n=\frac{1- q^{n + 1}}{1 - q},</math>
тоді
: <math>1+q+\cdots +q^n+q^{n+1}=\frac{1-q^{n+1}}{1-q}+q^{n+1}=</math>
: <math>=\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}</math>,
що й потрібно було довести.

'''Коментар:''' істинність твердження <math>P_n</math> в цьому доведенні — те саме, що й істинність рівності
: <math>1+q+\cdots +q^n=\frac{1-q^{n+1}}{1-q}.</math>

== Варіації та узагальнення ==
* [[Трансфінітна індукція]]
* [[Структурна індукція]]
* [[Аксіоми Пеано]]
* [[Зворотна індукція]] або [[Індукція Коші]]
* [[Коіндукція]]

== Джерела ==
{{refbegin}}
* {{Cite book|
author=Weisstein, Eric W. | authorlink= | coauthors= | 
title=CRC concise encyclopedia of mathematics | url=https://archive.org/details/crcconciseencycl0000weis |
date=1999 |
publisher=CRC Press |
location=Boca Raton, Fla.|
isbn=0-8493-9640-9 | pages=}}
{{refend}}

== Література ==

{{вікіпідручник|Знайомство з методом математичної індукції}}
* {{книга-ру |автор=[[Вілєнкін Наум Якович|Н. Я. Виленкин]] |заглавие=Индукция. Комбинаторика |издание=Пособие для учителей |место=М. |издательство=Просвещение |год=1976 |страниц=48}}
* {{книга-ру |автор=Л. И. Головина, [[Яглом Ісаак Мойсейович|И. М. Яглом]] |заглавие=Индукция в геометрии |серия=[[Популярные лекции по математике]] |том=21 |издательство=[[Физматгиз]] |год=1961 |страниц=100 |ссылка=http://plm.mccme.ru/ann/a21.htm}}
* {{книга-ру |автор=[[Ріхард Курант|Р. Курант]], Г. Роббинс |заглавие=Что такое математика? |nodot=1 |часть=Глава I, §&nbsp;2 |ссылка=http://www.mccme.ru/free-books/pdf/kurant.htm}}
* {{книга-ру |автор=И. С. Соминский |заглавие=Метод математической индукции |серия=[[Популярные лекции по математике]] |том=3 |издательство=Наука |год=1965 |страниц=58 |ссылка=http://plm.mccme.ru/ann/a03.htm}}

== Відеоматеріали ==
* [https://www.youtube.com/watch?v=ePmGdZd40-k Курс відеолекцій з математичної індукції українською мовою] {{Webarchive|url=https://web.archive.org/web/20160401025458/https://www.youtube.com/watch?v=ePmGdZd40-k |date=1 квітня 2016 }}
* [https://www.youtube.com/watch?v=_BytZXq2HCY Приклади розв'язування задач (відео українською мовою)]

== Див. також ==
{{Портал|Математика}}
* [[Доведення]]
* [[Дедукція]]
* [[Формальна логіка]]
* [[Проблема індукції]]

{{Math-stub}}

{{Математична логіка|state=collapsed}}

[[Категорія:Теореми]]
[[Категорія:1838 у науці]]
[[Категорія:Теорія доведення]]
[[Категорія:Математична індукція| ]]