From Wikipedia, the free encyclopedia
Matematinė indukcija (lot. inductio – paskatinimas, įvedimas) – matematinio įrodinėjimo metodas, dažniausiai naudojamas, kai reikia parodyti, kad koks nors teiginys yra teisingas visiems natūraliesiems skaičiams. Pirmas indukcijos etapas yra įrodyti, kad pirmasis teiginys iš begalinės teiginių sekos yra teisingas. Antrasis etapas yra įrodyti, kad jei vienas teiginys yra teisingas, tai ir kitas teiginys begalinėje sekoje yra teisingas. Taip yra parodoma, kad visi sekos teiginiai pradedant pirmu yra teisingi.
Matematinės indukcijos metodas gali būti ir praplėstas labiau apibendrintų sąvokų įrodymams. Tai vadinama struktūrine indukcija. Ji yra naudojama matematinėje logikoje bei kompiuterių moksle ir yra glaudžiai susijusi su rekursija.
Matematinė indukcija neturėtų būti painiojama su indukciniu samprotavimo metodu, kuris yra kritikuojamas, nes jo rezultatais niekada negalima tvirtai pasitikėti. Matematinė indukcija yra, priešingai, griežtas ir patikimas įrodinėjimo metodas ir iš tikrųjų yra dedukcinio mąstymo forma.
Manoma, kad 370 m. pr. m. e. Platono veikale „Parmenidas“ galima rasti ankstyvąjį matematinės indukcijos įrodymo pavyzdį.[1]
Paprasčiausia ir dažniausiai naudojama matematinės indukcijos forma įrodo, kad koks nors teiginys, kuriame yra natūralusis skaičius n yra teisingas visoms n reikšmėms. Tai yra padaroma dviem etapais:
Tarkime, kad aprašytu būdu įrodėme kokį nors teiginį, pirmame etape įrodę, kad jis yra teisingas su n = 1. Tai reikštų, kad antrame etape įrodėme, jog reiškinys galioja ir su n + 1. Laikykime, kad čia n = 1. Tada n + 1 reikšmė yra n + 1 = 1 + 1 = 2. Taigi teiginys galioja skaičiumi 2 arba, kitaip tariant, kai n = 2. Kadangi teiginys yra teisingas su n = 2, tai jis yra teisingas ir su n + 1, kurio reikšmė šiuo atveju jau yra n + 1 = 2 + 1 = 3 . O kadangi teiginys teisingas su n = 3, tai dėl tos pačios priežasties jis yra teisingas ir su n = 4 ir t. t. iki begalybės.
Analogiška situacija yra su krintančiai domino kauliukais. Tarkime, kad turime ilgą domino kauliukų eilę ir žinome kad:
Galime būti tikri, kad galiojant šioms taisyklėms būtinai nuvirs visi domino kauliukai.
Šiame pavyzdyje matematinės indukcijos metodu bus įrodyta, kad teiginys
galioja visiems natūraliesiems skaičiams n. Pavadinkime tai teiginiu P(n).
Reikia parodyti, kad teiginys yra teisingas, kai n = 0 (arba, kitaip tariant, įrodyti P(0)):
Kairiosios rankos lygybės pusė yra tiesiog lygi 0.
Dešiniosios rankos lygybės pusėje turime reiškinį 0·(0 + 1)/2. Išsprendžiame jį:
Kadangi abi lygybės pusės lygios nuliui, teiginys P(0) yra teisingas.
Reikia įrodyti, kad jeigu P(n) yra teisingas, tai ir P(n + 1) yra teisingas.
Visų pirma, reikia padaryti prielaidą, kad P(n) yra teisingas (kokiai nors neapibrėžtai reikšmei n). Po to reikia parodyti, kad tada ir teisingas yra ir P(n + 1), kurį galima išreikšti lygybe
Pasinaudojus indukcijos hipoteze P(n) (kurią ir bandome įrodyti), kairiosios rankos lygybės pusę galima perrašyti iš
į
Šią lygybę galima įrodyti tokiais algebriniais veiksmais:
Tai įrodo, kad teiginys P(n + 1) yra teisingas. Kadangi atlikti abu indukcijos etapai, įrodėme, kad teiginys P(n) yra teisingas visiems natūraliesiems skaičiams n, ką ir reikėjo padaryti.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.