Teljes indukció

A teljes indukció (ritkábban: matematikai indukció) a matematika egyik legfontosabb és leggyakrabban használt bizonyítási módszere a természetes számok körében. A teljes indukció elve a következő: Ha egy tulajdonság igaz 1-re (n=1), továbbá ez a tulajdonság olyan természetű, hogy öröklődik a természetes számok rákövetkezése során (tehát n-ről n+1-re), akkor ezzel a tulajdonsággal az összes természetes szám rendelkezik.

A módszer segítségével egyszerre megszámlálhatóan végtelen sok állítást lehet bizonyítani. A végtelen sok állítást sorba rendezzük, majd az így kapott sorozat első állítását igazoljuk. Ezután következik a teljes indukció „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 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 pozitív páratlan szám összege n².

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

A Maurolico által bizonyított állítás, vagyis hogy az első n pozitív páratlan szám összege éppen n², teljes indukciós bizonyítása következik. Képlet formájában:

${\displaystyle \sum _{i=1}^{n}2\cdot n-1=n^{2}}$, vagy másképp ${\displaystyle 1+3+\ldots +(2n-1)=n^{2}}$

Ezt az állítást minden pozitív egész n-re be kell látnunk.

Az első lépés, hogy ellenőrizzük az állítást ${\displaystyle n=1}$-re. Ekkor a bal oldalon mindössze egy tagja van az összeadásnak, az 1. A jobb oldalon pedig 1² áll, vagyis igaz az állítás, hiszen ${\displaystyle 1=1^{2}}$.

A második lépés az indukciós lépés. Tegyük fel tehát, hogy az állítás igaz ${\displaystyle n=k}$-ra. Ez azt jelenti, hogy ${\displaystyle \sum _{i=1}^{k}2\cdot k-1=k^{2}}$

Be kellene látni, hogy ekkor az állítás teljesül ${\displaystyle n=k+1}$-re is. A bal oldal ${\displaystyle n=k+1}$ esetén: ${\displaystyle 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

${\displaystyle 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 ${\displaystyle n=k+1}$-re is. Ezzel a bizonyítást befejeztük.

Kapcsolódó szócikkek

• Transzfinit indukció

További információk

• Alice és Bob - 11. rész: Alice és Bob számelméletet épít
• Alice és Bob - 12. rész: Alice és Bob rendet tesz

Források

• Részletes meghatározás példákkal

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!