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

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

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

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

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

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

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

Историја

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

$={\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}}.$

Стога имамо

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

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

$P(m)\Rightarrow P(m+1).\,$

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

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

Види још

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

Литература

• Franklin, J.; Daoud, A. (2011). Proof in Mathematics: An Introduction. Sydney: Kew Books. ISBN 978-0-646-54509-7.  (Ch. 8.)
• Hazewinkel Michiel, ур. (2001). „Mathematical induction”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Hermes, Hans (1973). Introduction to Mathematical Logic. Hochschultext. London: Springer. ISBN 978-3540058199. ISSN 1431-4657. 
• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd изд.). Addison-Wesley. ISBN 978-0-201-89683-1.  (Section 1.2.1: Mathematical Induction, pp. 11–21.)
• Kolmogorov, Andrey N.; Fomin, Sergei V. (1975). Introductory Real Analysis. Silverman, R. A. (trans., ed.). New York: Dover. ISBN 978-0-486-61226-3.  (Section 3.8: Transfinite induction, pp. 28–29.)
• Acerbi, Fabio (август 2000). „Plato: Parmenides 149a7-c3. A Proof by Complete Induction?”. Archive for History of Exact Sciences. 55 (1): 57—76. JSTOR 41134098. doi:10.1007/s004070000020. 
• Bussey, W. H. (1917). „The Origin of Mathematical Induction”. American Mathematical Monthly. 24 (5): 199—207. JSTOR 2974308. doi:10.2307/2974308. 
• Cajori, Florian (1918). „Origin of the Name "Mathematical Induction"”. The American Mathematical Monthly. 25 (5): 197—201. JSTOR 2972638. 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. ISBN 0-321-01618-1.
• Peirce, Charles Sanders (1881). „On the Logic of Number”. American Journal of Mathematics. 4 (1–4): 85—95. JSTOR 2369151. MR 1507856. doi:10.2307/2369151.  Reprinted (CP 3.252-88), (W 4  299–309)
• 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 одржавање: Непрепознат језик (веза)
• Rashed, R. (1994), „Mathematical induction: al-Karajī and al-Samawʾal”, The Development of Arabic Mathematics: Between Arithmetic and Algebra, Boston Studies in the Philosophy of Science (на језику: енглески), 156, Springer Science & Business Media, ISBN 9780792325659 
• Shields, Paul (1997). „Peirce's Axiomatization of Arithmetic”. Ур.: Houser; et al. Studies in the Logic of Charles S. Peirce. 
• Simonson, Charles G. (зима 2000). „The Mathematics of Levi ben Gershon, the Ralbag” (PDF). Bekhol Derakhekha Daehu. Bar-Ilan University Press. 10: 5–21. Архивирано из оригинала (PDF) 11. 10. 2017. г. Приступљено 25. 07. 2020. 
• 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. JSTOR 230435. 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. 
• Lucci, Stephen; Kopec, Danny (2015). Artificial Intelligence in the 21st Century (на језику: енглески). Stylus Publishing, LLC. ISBN 978-1-944534-53-0. 
• Tagiew, Rustam (2008). „Simplest Scenario for Mutual Nested Modeling in Human-Machine-Interaction”. KI 2008: Advances in Artificial Intelligence (на језику: енглески). Springer: 364—371. doi:10.1007/978-3-540-85845-4_45. 
• Fagin, Ronald; Halpern, Joseph Y.; Moses, Yoram; Vardi, Moshe Y. (март 1999). „Common knowledge revisited”. Annals of Pure and Applied Logic. 96 (1–3): 89—105. arXiv:cs/9809003 . doi:10.1016/S0168-0072(98)00033-5. 
• van der Hoek, Wiebe; van Ditmarsch, Hans (2007). Dynamic epistemic logic. Springer. ISBN 978-1-4020-5838-7. 

Спољашње везе

• „Forward-Backward Induction | Brilliant Math & Science Wiki”. brilliant.org (на језику: енглески). Приступљено 23. 10. 2019. 
• Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, Cauchy, Augustin-Louis (1821).