|
[[Fájl:Dominoeffect.png|bélyegkép|jobbra|200px|A teljes indukció módszere a [[dominóeffektus]]ra hasonlít.]]
A '''teljes indukció''' a [[matematika]] egyik gyakran használt, fontos [[matematikai bizonyítás|bizonyítási]] módszere. A matematika minden ágában használatos.
A módszer segítségével tulajdonképpen egyszerre [[megszámlálhatóan végtelen]] sok állítást lehet bizonyítani. A végtelen sok állítást sorba kell rendeznünk (vagyis csak megszámlálhatóan végtelen sok állítás bizonyítható ily módon)rendezzük, majd az így kapott sorozat első állítását igazoljuk. Ezután következik a lelketeljes a teljesindukció indukciónak„lelke”, az '''indukciós lépés'''. Ez annak az állításnak a bizonyítását jelenti, hogy ha feltesszük, hogy az ''n''-edik állítás igaz, akkor abból következik az ''n+1''-edik állítás igazsága is. Az első állítás igazsága és az indukciós lépés együtt már az összes állítás igazságát is bizonyítja.
A teljes indukció nagyobb számosságokra[[számosság]]okra való általánosítása a [[transzfinit indukció]].
A teljes indukció első írásos emléke [[1575]]-ből származik. Ekkor bizonyította [[Francesco Maurolico]] ''Arithmeticorum libri fuo'' című művében, hogy az első ''n'' páratlan szám összege ''n<sup>2</sup>''.
A módszer neve félrevezető;, valójában nem általánosításról, hanem a matematika szabályai szerinti bizonyításról van szó, azaz a teljes indukció – mint minden más matematikailag helyes módszer – tulajdonképpen [[dedukció]].
==Példa==
Egy példa alapján könnyebben megérthető a módszer. Legyen ez aA Maurolico által bizonyított állítás, vagyis hogy az első ''n'' páratlan szám összege éppen ''n<sup>2</sup>'' teljes indukciós bizonyítása következik. Képlet formájában:
<center>:<math>1+3+ \ldots + (2n-1) = n^2</math>.</center>
Ez tehátEzt az állításállítást minden pozitív egész ''n''-re, amit be kell látnunk.
Az '''első lépés''', hogy ellenőrizzük az állítást <math>n=1</math>-re. Ekkor a baloldalon mindössze egy tagja van az összeadásnak, az 1. A jobboldalon pedig 1<sup>2</sup> áll, vagyis igaz az állítás, hiszen <math>1=1^2</math>.
A második lépés az ''indukciós lépés''. Tegyük fel tehát, hogy az állítás igaz <math>n=k</math>-ra. Ez azt jelenti, hogy <math>1+3+\ldots + (2k-1)=k^2</math>.
Ekkor a baloldalon mindössze egy tagja van az összeadásnak, az 1. A jobboldalon pedig 1<sup>2</sup> áll, vagyis igaz az állítás, hiszen <math>1=1^2</math>.
ABe második lépés pedig az '''indukcióskellene lépés'''. Tegyük fel tehátlátni, hogy ekkor az állítás igazteljesül <math>n = k+1</math>-rare is. EzA aztbal jelenti,oldal hogy<math>n = k+1</math> esetén: <math>1+3+\ldots + (2k-1)=k^2+ (2k+1)</math>. Azért írjuk ilyen alakban, hogy jól látható legyen, hogy hol lehet felhasználni az indukciós feltevést. Ekkor ugyanis
:<math>1+3+\ldots +(2k-1)+(2k+1) = k^2 + (2k+1) = k^2 +2k+1 = (k+1)^2</math>:
Be kellene látni, hogy ekkor az állítás teljesül <math>n = k+1</math>-re is. A baloldal <math>n = k+1</math> esetén: <math>1+3+\ldots + (2k-1)+ (2k+1)</math>. Azért írjuk ilyen alakban, hogy jól látható legyen, hogy hol lehet felhasználni az indukciós feltevést. Ekkor ugyanis <center><math>1+3+\ldots +(2k-1)+(2k+1) = k^2 + (2k+1) = k^2 +2k+1 = (k+1)^2</math>.</center>
Vagyis az állítás teljesül <math>n = k+1</math>-re is. Ezzel a bizonyítást befejeztük.
| 