Математична індукція Зміст Формулювання | Історія |...


Теореми1838 у науціТеорія доведенняМатематична індукція


доведення теоремматематицінатуральних чиселпослідовністьнатуральними числамиаксіом Пеанонатуральні числаімплікаціятрансфінітної індукціїБлеза ПаскаляГерсонідаПлатонаДіалог ПарменідПроклаЕвклідаАуґустус де Морган1838





Dominoeffect.png

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


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




  1. P1{displaystyle P_{1}} — правильне, та

  2. із правильності Pk{displaystyle P_{k}} випливає правильність (істинність) Pk+1{displaystyle P_{k+1}} для всіх k.


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


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




Зміст






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


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




  • 2 Історія


  • 3 Приклади


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


  • 5 Джерела


  • 6 Література


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


  • 8 Див. також





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


Припустимо, що потрібно встановити справедливість безкінечною послідовності тверджень, занумерованих натуральними числами: P1,P2,…,Pn,Pn+1,…{displaystyle P_{1},P_{2},ldots ,P_{n},P_{n+1},ldots }.



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



  1. Встановлено, що P1{displaystyle P_{1}} правильне. (Це твердження називається базою індукції.)

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


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



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



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


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



Нехай є послідовність тверджень P1{displaystyle P_{1}}, P2{displaystyle P_{2}}, P3{displaystyle P_{3}}, {displaystyle ldots }. Якщо для будь-якого натурального n{displaystyle n} з того, що істинні всіP1{displaystyle P_{1}}, P2{displaystyle P_{2}}, P3{displaystyle P_{3}}, {displaystyle ldots }, Pn−1{displaystyle P_{n-1}}, слід також істинність Pn{displaystyle P_{n}}, то всі твердження в цій послідовності істинні, тобто (∀n∈N)((∀i∈{1;…;n−1})Pi⟶Pn)⟶(∀n∈N)Pn{displaystyle (forall nin {mathbb {N} }){Big (}(forall iin {1;dots ;n-1})P_{i}longrightarrow P_{n}{Big )}longrightarrow (forall nin {mathbb {N} })P_{n}}.



У цій варіації база індукції виявляється зайвою, оскільки є тривіальним окремим випадком індукційного переходу. Дійсно, при n=1{displaystyle n=1} імплікація (∀i∈{1;…;n−1})Pi⟶Pn{displaystyle (forall iin {1;dots ;n-1})P_{i}longrightarrow P_{n}} еквівалентна P1{displaystyle P_{1}}. Принцип повної математичної індукції є прямим застосуванням більш сильною трансфінітної індукції.


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



Історія |


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



Приклади |


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


1+q+q2+⋯+qn=1−qn+11−q.{displaystyle 1+q+q^{2}+cdots +q^{n}={frac {1-q^{n+1}}{1-q}}.}

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


База, n = 1:


1+q=(1−q)(1+q)1−q=1−q1+11−q.{displaystyle 1+q={frac {(1-q)(1+q)}{1-q}}={frac {1-q^{1+1}}{1-q}}.}

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


1+q+⋯+qn=1−qn+11−q,{displaystyle 1+q+cdots +q^{n}={frac {1-q^{n+1}}{1-q}},}

тоді



1+q+⋯+qn+qn+1=1−qn+11−q+qn+1={displaystyle 1+q+cdots +q^{n}+q^{n+1}={frac {1-q^{n+1}}{1-q}}+q^{n+1}=}


=1−qn+1+(1−q)qn+11−q=1−qn+1+qn+1−q(n+1)+11−q=1−q(n+1)+11−q{displaystyle ={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}}},


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


Коментар: істинність тверджения Pn{displaystyle P_{n}} в цьому доведенні — то саме, що й істинність рівності


1+q+⋯+qn=1−qn+11−q.{displaystyle 1+q+cdots +q^{n}={frac {1-q^{n+1}}{1-q}}.}


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



  • Трансфінітна індукція

  • Структурна індукція

  • Аксіоми Пеано


  • Зворотня індукція або Індукція Коші



Джерела |


.mw-parser-output .refbegin{font-size:90%;margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{list-style-type:none;margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li,.mw-parser-output .refbegin-hanging-indents>dl>dd{margin-left:0;padding-left:3.2em;text-indent:-3.2em;list-style:none}.mw-parser-output .refbegin-100{font-size:100%}


  • 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 с. — (Популярні лекції з математики)



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



  • Курс відеолекцій з математичної індукції українською мовою

  • Приклади розв'язування задач (відео українською мовою)



Див. також |




  • Доведення

  • Дедукція

  • Формальна логіка

  • Проблема індукції










Popular posts from this blog

Фонтен-ла-Гаярд Зміст Демографія | Економіка | Посилання |...

Список ссавців Італії Природоохоронні статуси | Список |...

Маріан Котлеба Зміст Життєпис | Політичні погляди |...