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

Математичка индукција је метод математичког доказивања који се обично користи да се утврди да је дати исказ тачан за све природне бројеве. Ово се врши

• доказивањем да је први у бесконачном низу исказа тачан, и затим
• доказивањем да ако је неки исказ у бесконачном низу исказа тачан, онда је тачан и њему следећи исказ

Математичка индукција се може неформално илустровати позивањем на секвенцијални ефекат падајућих домина.^[1][2]

Математичку индукцију не треба схватати као облик индуктивног резоновања, које се сматра не-ригорозним у математици (види проблем индукције). У ствари, математичка индукција је облик дедуктивног резоновања, и потпуно је ригорозна.

Метод се може проширити да докаже изјаве о општијим добро утемељеним структурама, као што су стабла; ова генерализација, позната као структурна индукција, користи се у математичкој логици и рачунарству. Математичка индукција у овом проширеном смислу је уско повезана са рекурзијом. Математичка индукција је правило закључивања које се користи у формалним доказима и представља основу већине доказа исправности за компјутерске програме.^[3]

Иако њено име може сугерисати другачије, математичку индукцију не треба мешати са индуктивним резоновањем које се користи у филозофији (погледајте проблем индукције). Математички метод испитује бесконачно много случајева да би доказао општу тврдњу, али то чини помоћу коначног ланца дедуктивног закључивања који укључује променљиву ${\displaystyle n}$, која може узети бесконачно много вредности.^[4]

Историја

Најранији трагови математичке индукције се могу наћи у Еуклидовом доказу да постоји бесконачно пуно простих бројева, и Баскарином циклидном методу^[5] Форма доказа математичком индукцијом се јавља у књизи коју је написао Ал-Караџи око 1000. године, који ју је између осталог користио да докаже биномну теорему и Паскалов троугао.^[6][7]

Ниједан од ових старих математичара није експлицитно дао индуктивну хипотезу. Прво ригорозно излагање принципа индукције је дао Франческо Мауролико, у свом делу (1575), који је користио ову технику да докаже да је збир првих непарних целих бројева једнак ². Индукцију су такође независно открили Швајцарац Јакоб Бернули и Французи Паскал и Ферма.^[5]

Формални опис

Најједноставнији и најуобичајенији облик математичке индукције доказује да неки исказ важи за све природне бројеве . Овај доказ се састоји из два корака:

1. База индукције: показује се да исказ важи када је = 0.
2. Индуктивни корак: показује се да ако исказ важи за , онда исти исказ важи и за

Коришћење речи ако у индуктивном кораку се назива индуктивном хипотезом. Како би се спровео индуктивни корак, претпоставља се да индуктивна хипотеза важи (тачније да је исказ тачан за ) и онда се користи ова претпоставка да се докаже исказ за

Формални опис математичке индукције се може илустровати ефектом домина.

Овај метод функционише на следећи начин. Прво се докаже да је исказ тачан за почетну вредност, а затим се докаже да је процес преласка са неке вредности на следећу исправан. Ако су оба доказана, онда се до тачности исказа за сваку вредност може доћи узастопним понављањем овог процеса. Ово се може посматрати као ефекат домина; Ако имамо дугачак низ домина, и ако смо сигурни да:

1. Прва домина може да падне
2. Која год домина да падне, обориће и следећу домину,

онда се може закључити да ће све домине пасти, уколико се обори прва домина.

Основна претпоставка или аксиома индукције (прихвата се, не доказује) је исписана логичким симболима,

${\displaystyle \forall {\mbox{ predicates }}P,(P(0)\land \forall k[P(k)\Rightarrow P(k+1)])\Rightarrow \forall nP(n)}$

где је дати исказ, а природан број.

Корак 1. доказати (0) - формула важи за цео број 0.

Корак 2. доказати да за сваки природан број , () имплицира . Да би се ово спровело, претпоставља се да важи и показује се да из ове претпоставке следи да важи . Ово не значи замену у - ово је врло честа грешка која се састоји у претпостављању онога шта тек треба да се докаже. Заједно кораци 1. и 2. имплицирају да важи за свако веће или једнако 0. У општем случају, ако је доказано, где може бити негативан цео број (замислимо домине нумерисане од -20 па навише), онда важи за свако веће или једнако .

Пример

Претпоставимо да желимо да докажемо исказ:

${\displaystyle 1+2+3+\cdots +n={\frac {n(n+1)}{2}}}$

За све природне бројеве ; обележимо овај исказ као . (Ово је специјални случај Фаулхаберове формуле.) Ово је једноставна формула за суму позитивних природних бројева мањих или једнаких броју . Доказ да је овај исказ тачан за све природне бројеве следи.

Проверимо да ли је исказ тачан за = 1. Сума самог броја 1 је просто 1. А 1(1 + 1) / 2 = 1. Значи, исказ је тачан за = 1. Доказали смо да важи.

Сада морамо да покажемо да ако исказ важи када је , онда он такође важи и када је . Ово се може извести на следећи начин.

Претпоставимо да је исказ тачан за , тј,

${\displaystyle 1+2+\cdots +m={\frac {m(m+1)}{2}}}$

Додавањем са обе стране се не мења једнакост:

${\displaystyle 1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)}$

Алгебарском манипулацијом, са десне стране добијамо

${\displaystyle ={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}={\frac {(m+1)(m+2)}{2}}={\frac {(m+1)((m+1)+1)}{2}}.}$

Стога имамо

${\displaystyle 1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}}$

Приметимо да је ово еквивалентно тврђењу . Овај доказ је кондиционалан: начинили смо претпоставку да је тачно, и из тога смо извели . Стога, ако је тачно, онда и мора бити тачно. Симболички, показали смо да

${\displaystyle P(m)\Rightarrow P(m+1).\,}$

Сада, како бисмо завршили, користимо процес математичке индукције:

1. Знамо да је тачно.
2. Како имплицира , тачно је и .
3. Слично, како имплицира , добијамо .
4. Са , добијамо .
5. Из , следи .
6. И тако даље. (овде наступа аксиома математичке индукције.)
7. Можемо да закључимо да важи за сваки природан број .

Види још

• Индукција (математика)