Teljes indukció

A teljes indukció egy speciális bizonyítási módszer, mely a természetes számok mindegyikére vonatkozó állítások bizonyítására alkalmas.

A módszer tehát nem egy állítást igazol, hanem megszámlálhatóan végtelen sok állítást, kihasználva a természetes számok halmazának azt a tulajdonságát, hogy minden elemnek van rákövetkezője és ilyen módon a 0-ból kiindulva az összes természetes szám felsorolható. (Lásd: Peano-féle axiomarendszer, indukciós axióma)

A teljes indukció megszámlálhatóan végtelen számosságnál használható; kiterjesztése a transzfinit indukció.

A bizonyítás alapvetően két részből áll.

Az első lépésben bizonyítjuk az állítást n=0 értékre (konkrét feladatokban persze előfordul,hogy nem n=0 esetból indulunk ki, hanem más kezdőértéket választunk.)

A bizonyítás második részében megmutatjuk, hogy ha az állítás igaz valamely n=k értékre (indukciós feltevés), akkor igaz lesz n=k+1 esetén is (indukciós lépés).

A két lépés együtt bizonyítja, hogy az állítás tetszőleges természetes számra igaz, hiszen n=0-ra beláttuk az állítást, ha n=0 esetén igaz az állítás, akkor az indukciós lépés miatt n=1 esetet is igazoltuk, de ha n=1 igaz, akkor az indukciós lépés miatt a rákövetkező n=2 érték esetén is igaz lesz az állítás, és így tovább…

Egy-két példát jó lenne részletezni is… ha valaki érez magában erre indíttatást :)

• Az első n négyzetszám összege .
• Hány részre oszthatja maximum a síkot n egyenes?
• Gráfelmélet: n csúcsú fa éleinek száma n-1.
• Gráfelmélet: Euler tétel