доказивањем да је први у бесконачном низу исказа тачан, и затим
доказивањем да ако је неки исказ у бесконачном низу исказа тачан, онда је тачан и њему следећи исказ
Математичку индукцију не треба схватати као облик индуктивног резоновања, које се сматра не-ригорозним у математици (види проблем индукције). У ствари, математичка индукција је облик дедуктивног резоновања, и потпуно је ригорозна.
Метод се може проширити да докаже изјаве о општијим добро утемељеним структурама, као што су стабла; ова генерализација, позната као структурна индукција, користи се у математичкој логици и рачунарству. Математичка индукција у овом проширеном смислу је уско повезана са рекурзијом. Математичка индукција је правило закључивања које се користи у формалним доказима и представља основу већине доказа исправности за компјутерске програме.[3]
Иако њено име може сугерисати другачије, математичку индукцију не треба мешати са индуктивним резоновањем које се користи у филозофији (погледајте проблем индукције). Математички метод испитује бесконачно много случајева да би доказао општу тврдњу, али то чини помоћу коначног ланца дедуктивног закључивања који укључује променљиву, која може узети бесконачно много вредности.[4]
Најранији трагови математичке индукције се могу наћи у Еуклидовом доказу да постоји бесконачно пуно простих бројева, и Баскариномциклидном методу[5] Форма доказа математичком индукцијом се јавља у књизи коју је написао Ал-Караџи око 1000. године, који ју је између осталог користио да докаже биномну теорему и Паскалов троугао.[6][7]
Ниједан од ових старих математичара није експлицитно дао индуктивну хипотезу. Прво ригорозно излагање принципа индукције је дао Франческо Мауролико, у свом делу (1575), који је користио ову технику да докаже да је збир првих непарних целих бројева једнак 2. Индукцију су такође независно открили Швајцарац Јакоб Бернули и Французи Паскал и Ферма.[5]
Најједноставнији и најуобичајенији облик математичке индукције доказује да неки исказ важи за све природне бројеве . Овај доказ се састоји из два корака:
База индукције: показује се да исказ важи када је = 0.
Индуктивни корак: показује се да ако исказ важи за , онда исти исказ важи и за
Коришћење речи ако у индуктивном кораку се назива индуктивном хипотезом. Како би се спровео индуктивни корак, претпоставља се да индуктивна хипотеза важи (тачније да је исказ тачан за ) и онда се користи ова претпоставка да се докаже исказ за
Овај метод функционише на следећи начин. Прво се докаже да је исказ тачан за почетну вредност, а затим се докаже да је процес преласка са неке вредности на следећу исправан. Ако су оба доказана, онда се до тачности исказа за сваку вредност може доћи узастопним понављањем овог процеса. Ово се може посматрати као ефекат домина; Ако имамо дугачак низ домина, и ако смо сигурни да:
Прва домина може да падне
Која год домина да падне, обориће и следећу домину,
онда се може закључити да ће све домине пасти, уколико се обори прва домина.
Основна претпоставка или аксиома индукције (прихвата се, не доказује) је исписана логичким симболима,
где је дати исказ, а природан број.
Корак 1. доказати (0) - формула важи за цео број 0.
Корак 2. доказати да за сваки природан број , () имплицира . Да би се ово спровело, претпоставља се да важи и показује се да из ове претпоставке следи да важи . Ово не значи замену у - ово је врло честа грешка која се састоји у претпостављању онога шта тек треба да се докаже.
Заједно кораци 1. и 2. имплицирају да важи за свако веће или једнако 0. У општем случају, ако је доказано, где може бити негативан цео број (замислимо домине нумерисане од -20 па навише), онда важи за свако веће или једнако .
Претпоставимо да желимо да докажемо исказ:
За све природне бројеве ; обележимо овај исказ као . (Ово је специјални случај Фаулхаберове формуле.) Ово је једноставна формула за суму позитивних природних бројева мањих или једнаких броју . Доказ да је овај исказ тачан за све природне бројеве следи.
Проверимо да ли је исказ тачан за = 1. Сума самог броја 1 је просто 1. А 1(1 + 1) / 2 = 1. Значи, исказ је тачан за = 1. Доказали смо да важи.
Сада морамо да покажемо да ако исказ важи када је , онда он такође важи и када је . Ово се може извести на следећи начин.
Претпоставимо да је исказ тачан за , тј,
Додавањем са обе стране се не мења једнакост:
Алгебарском манипулацијом, са десне стране добијамо
Стога имамо
Приметимо да је ово еквивалентно тврђењу . Овај доказ је кондиционалан: начинили смо претпоставку да је тачно, и из тога смо извели . Стога, ако је тачно, онда и мора бити тачно. Симболички, показали смо да
Сада, како бисмо завршили, користимо процес математичке индукције:
Знамо да је тачно.
Како имплицира , тачно је и .
Слично, како имплицира , добијамо .
Са , добијамо .
Из , следи .
И тако даље. (овде наступа аксиома математичке индукције.)
Можемо да закључимо да важи за сваки природан број .
Cajori (1918), стр.197: Процес резоновања који се назива математичком индукцијом има неколико независних корена. Може се пратити до Швајцарца Јакоба (Џејмса) Бернулија, Француза Б. Паскала и П. Ферма, Италијана Ф. Мауролицуса. [...] Ако се мало чита између редова, могу се наћи трагови математичке индукције и раније, у списима Индуса и Грка, на пример у циклидном методу Баскаре и у Еуклидовом доказу да простих бројева има бесконачно много.
Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd изд.). Addison-Wesley. ISBN978-0-201-89683-1. (Section 1.2.1: Mathematical Induction, pp.11–21.)
Bussey, W. H. (1917). „The Origin of Mathematical Induction”. American Mathematical Monthly. 24 (5): 199—207. JSTOR2974308. doi:10.2307/2974308.
Cajori, Florian (1918). „Origin of the Name "Mathematical Induction"”. The American Mathematical Monthly. 25 (5): 197—201. JSTOR2972638. doi:10.2307/2972638.
Fowler, D. (1994). „Could the Greeks Have Used Mathematical Induction? Did They Use It?”. Physis. XXXI: 253—265.
Freudenthal, Hans (1953). „Zur Geschichte der vollständigen Induction”. Archives Internationales d'Histoire des Sciences. 6: 17—37.
Hyde, Dominic; Raffman, Diana (2018), Zalta, Edward N., ур., „Sorites Paradox”, The Stanford Encyclopedia of Philosophy (Summer 2018 изд.), Metaphysics Research Lab, Stanford University, Приступљено 23. 10. 2019
Katz, Victor J. (1998). History of Mathematics: An Introduction. Addison-Wesley. 0-321-01618-1.
Rabinovitch, Nachum L. (1970). „Rabbi Levi Ben Gershon and the origins of mathematical induction”. Archive for History of Exact Sciences. 6 (3): 237—248. doi:10.1007/BF00327237.
Rashed, Roshdi (1972). „L'induction mathématique: al-Karajī, as-Samaw'al”. Archive for History of Exact Sciences (на језику: French). 9 (1): 1—21. doi:10.1007/BF00348537.CS1 одржавање: Непрепознат језик (веза)
Unguru, S. (1991). „Greek Mathematics and Mathematical Induction”. Physis. XXVIII: 273—289.
Unguru, S. (1994). „Fowling after Induction”. Physis. XXXI: 267—272.
Vacca, G. (1909). „Maurolycus, the First Discoverer of the Principle of Mathematical Induction”. Bulletin of the American Mathematical Society. 16 (2): 70—73. doi:10.1090/S0002-9904-1909-01860-9.
Yadegari, Mohammad (1978). „The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)”. Isis. 69 (2): 259—262. JSTOR230435. doi:10.1086/352009.
Stuhlmüller, A.; Goodman, N.D. (јун 2014). „Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs”. Cognitive Systems Research. 28: 80—99. doi:10.1016/j.cogsys.2013.07.003.