|
'''Matematika indukto''' estas matematika [[matematika pruvo|pruvmetodo]], per kiu oni pruvas [[aserto]]n por ĉiuj [[natura nombro|naturaj nombroj]]. Ĉar temas pri senfina kvanto deda nombroj, tia pruvo ne povas esti realigata por ĉiu unuopa kazo. Tial oni realigas la pruvon en du ŝtupoj: La ''bazo de la indukto'' por la plej malgranda nombro (plej ofte 0 aŭ 1) kaj la ''paŝo de la indukto'', kiu logike deduktas de aserto pri iu varianta nombro la koncernan aserton por la sekva nombro. Ĉi tiu pruvmetodo havas fundamentan rolon en la [[aritmetiko]] kaj [[aroteorio]], kaj tial gravas por ĉiuj branĉoj de la matematiko.
Matematika indukto ne estas speco de [[indukta logiko]], kiu ne estas sufiĉe rigora por matematiko. Matematika indukto uzas nur [[logiko|deduktan logikon]].
== Ilustrado ==
[[Dosiero:Ilustro de indukto.png|eta|190px|maldekstra|Konkretaj paŝoj de indukto]]
Per la varianta indukto-paŝo la matematika indukto kovras ajnan kvanton de paŝoj, kiujn oni povas konkrete realigi komencante ĉe 1. Tion ilustras la ilustraĵo maldekstre. Tiu metodo estas komparebla kun la [[domen-efiko|dfenomeno de domeno]]: Kiamkiam la unua domen-tabulo falas kaj ĉiu falanta tabulo faligas la sekvan tabulon, tiam fine ĉiu domen-tabulo falas. Kontraste al la kazo de domeno, ĉe kiu povas ekzisti nur finhavafinia kvanto da domen-tabuloj, ekzistas senfina kvanto da naturaj nombroj, tiel ke neniu ajne longa konkreta indukto atingas ĉiujn nombrojn. Nur per la varianta indukto-paŝo la indukto iĝas kompleta kaj vere atingas ĉiujn nombrojn.
[[Dosiero:Domen-indukto.png|eta|500px|Matematika indukto kiel [[domeno (ludo)|domen]]-efiko]]
La principo de indukto estas transigebla ankaŭ al tiel nomataj [[bone-fundamentita aro|bone-fundamentitaj aroj]], kiuj posedas ordostrukturon kompareblan al tiu de la naturaj nombroj; ĉi-okaze oni parolas ankaŭ pri [[struktura indukto]].
== RikuraRekura aŭ indukta difino ==
La [[rikuro|rikurarekura difino]] - ankaŭ nomata ''indukta difino''<ref name="Hausdorff">[http://books.google.de/books?id=3nth_p-6DpcC&pg=PA212&lpg=PA212&dq=Hausdorff+%22Transfinite+Induktion%22&source=bl&ots=oMCu_BTVps&sig=lWdderWH55VqGvyXgwnuqjgIYl8&hl=de&ei=v58tTIzGL4jLOKLLsccB&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBkQ6AEwAA#v=onepage&q=Hausdorff%20%22Transfinite%20Induktion%22&f=false Hausdorff: Grundzüge der Mengenlehre, 1914, paĝoj 112 kaj sekvaj]</ref><ref>Peano: ''Le Definitione in Matematica'', 1921, en: Opere scelte II S.431, §7 Definizioni per induzione</ref> - estas procedo analoga al la matematika indukto, ĉe kiu oni difinas matematikan esprimon per rikuro-bazo kaj rikuro-paŝo. Pruvo kun matematika indukto povas evitigi rikuran kalkulon. Ekzemple, la [[#La sumformulo de Gauss|sumformulo de Gauss]] evitigas rikuran kalkulon de la sumo <math>\sum^n_{k=1} k</math> per rikuro-bazo <math>\sum^1_{k=1} k=1</math> kaj rikuro-paŝo <math>\sum^{n+1}_{k=1} k=\sum^{n}_{k=1}k+n+1</math>.
Rikuro same kiel indukto havas diversajn variaĵojn.
| 