A teljes indukció lépései

Teljes indukcióval olyan állítást (sejtést) bizonyíthatunk, amely az n pozitív egész számoktól függ.

A bizonyítás lépései:

1. Előzetes ellenőrzéssel (megfigyeléssel) belátjuk, hogy az állítás igaz -re. (Lehet, hogy van olyan állítás, amelynél azt találjuk, hogy az a legkisebb n, amelyre az állítás igaz, nem , hanem például .)

2. a) Feltesszük, hogy az állítás (sejtés) valamely n pozitív egész számra igaz.

b) Megnézzük, hogy ha az állítás n-re igaz, akkor -re igaz-e. Ha igaznak találjuk, akkor az állítás n-ről -re öröklődik, azaz -től (vagy -tól) kezdve minden pozitív egész számra igaz.

Feladat: Sík tartományokra bontása egyenesekkel

Bizonyítsuk be, hogy a síkot n számú egyenes legfeljebb számú tartományra bontja!

Megoldás: Sík tartományokra bontása egyenesekkel

A bizonyítást teljes indukcióval végezzük.
1. Nyilvánvaló, hogy -re igaz az állítás. Ekkor Egy egyenes valóban két tartományra bontja a síkot.
2. a) Feltesszük, hogy n-re igaz az állítás, azaz n darab egyenes a síkot legfeljebb tartományra bontja.
2. b) Megnézzük, hogy ez az állítás öröklődik-e n-ről -re. A kifejezésbe -et helyettesítünk, és átalakításokat végzünk. Célunk az, hogy felhasználhassuk az indukciós feltételt.

Az első tag azt mutatja, hogy n egyenes esetén mennyi a tartományok maximális száma. (Ez volt az indukciós feltevés.) Most azonban már egyenes van a síkon. Az -edik egyenes meghúzásakor úgy lesz maximális számú új tartomány, ha az -edik egyenes minden már meglévő egyenest, azaz n darabot, metsz. Az -edik egyenes egy-egy meglévő egyeneshez érve egy-egy eddigi tartományt két részre vág. Az n-edikhez érve már n darab új tartomány keletkezett. Az n-edik egyenest elhagyva még egy új tartomány jön létre, így új tartomány keletkezett. Tehát egyenessel létrejött tartományok maximális száma az n egyenessel létrejöttek számánál -gyel több.
Ezzel beláttuk, hogy az állítás igaz.