Teljes indukció

A teljes indukció módszere a dominóeffektusra hasonlít.

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 egy n₀ kezdeti értékre (általában n=0-ra vagy n=1-re), 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 n₀-tól kezdődően ezzel a tulajdonsággal minden természetes szám rendelkezik.

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ó.

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 (kezdőlépés). 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 az n-edik állítás implikálja az n+1-edik állítást, azaz 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 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².

Példa

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

${\displaystyle \sum _{i=1}^{n}2i-1=n^{2}}$, vagy másképp ${\displaystyle 1+3+\dots +(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 az 1 áll, a jobb oldalon pedig 1², 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}2i-1=1+3+\dots +(2k-1)=k^{2}}$.

Be kellene látni, hogy ekkor az állítás teljesül ${\displaystyle n=k+1}$-re is, azaz ${\displaystyle \sum _{i=1}^{k+1}2i-1=1+3+\dots +(2k-1)+(2k+1)=(k+1)^{2}}$.

Az ${\displaystyle n=k+1}$ esetén bal oldalon álló összeg a feltevés alapján:

${\displaystyle \left[1+3+\dots +(2k-1)\right]+(2k+1)=k^{2}+(2k+1)=k^{2}+2k+1=(k+1)^{2}}$.

Vagyis az állítás valóban teljesül ${\displaystyle n=k+1}$-re.

Ezzel a bizonyítást befejeztük, ugyanis a kezdőlépés és az indukciós lépés alapján a ${\displaystyle \sum _{i=1}^{n}2i-1=n^{2}}$ állítás igaz minden pozitív egész n esetén.

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