====== 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: [[matematika:halmazok:számhalmazok#természetes számok halmaza|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 menete =====

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




===== Példák =====

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 <m>{n(n+1)(2n+1)}/6</m>.
  * Hány részre oszthatja maximum a síkot //n// egyenes?
  * Gráfelmélet: //n// csúcsú [[oktatas:matematika:kombinatorika:fa]] éleinek száma //n-1//.
  * Gráfelmélet: [[oktatas:matematika:kombinatorika:grafelmelet#Euler tétel]]