Teljes indukció

A Wikipédiából, a szabad lexikonból.

Teljes indukciónak (vagy matematikai indukciónak) egy bizonyítási módszert nevezünk. A teljes indukció a matematika szinte minden ágában használható.

A módszer segítségével tulajdonképpen egyszerre 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), majd az így kapott sorozat első állítását igazoljuk. Ezután következik a lelke a teljes indukciónak, 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.

A teljes indukció nagyobb számosságokra 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 n2.

[szerkesztés] Példa

Egy példa alapján könnyebben megérthető a módszer. Legyen ez a Maurolico által bizonyított állítás, vagyis hogy az első n páratlan szám összege éppen n2. Képlet formájában:

1+3+ \ldots + (2n-1) = n^2.

Ez tehát az állítás 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 n = 1-re.

Ekkor a baloldalon mindössze egy tagja van az összeadásnak, az 1. A jobboldalon pedig 12 áll, vagyis igaz az állítás, hiszen 1 = 12.

A második lépés pedig az indukciós lépés. Tegyük fel tehát, hogy az állítás igaz n = k-ra. Ez azt jelenti, hogy 1+3+\ldots + (2k-1)=k^2.

Be kellene látni, hogy ekkor az állítás teljesül n = k + 1-re is. A baloldal n = k + 1 esetén: 1+3+\ldots + (2k-1)+ (2k+1). Azért írjuk ilyen alakban, hogy jól látható legyen, hogy hol lehet felhasználni az indukciós feltevést. Ekkor ugyanis

1+3+\ldots +(2k-1)+(2k+1) = k^2 + (2k+1) = k^2 +2k+1 = (k+1)^2.

Vagyis az állítás teljesül n = k + 1-re is. Ezzel a bizonyítást befejeztük.

[szerkesztés] Külső hivatkozások

Részletesebb meghatározása a teljes indukciónak ábrákkal és feladattal