Teljes indukció

A Programozás Wiki wikiből

Egy bizonyítási eljárás, ami a következő tételen alapul:

Tegyük fel, hogy A(n) egy állítás (minden n eleme N-re) és:

  • 1. A(0) igaz
  • 2. Ha A(n) igaz, akkor A(n+1) is igaz

Ekkor A(n) minden n-re igaz.

Bizonyítása[szerkesztés]

Tegyük fel, hogy S halmaz kizárólag azokat az n-eket tartalmazza, melyekre igaz A(n) állítás. (Ilyenkor S része N-nek)

Tudjuk, hogy 0 eleme S-nek, és azt is, hogy ha n eleme, akkor n+1 is eleme. Ebből következik, hogy S egy induktív halmaz.

Mivel tudjuk, hogy N a legszűkebb induktív halmaz, ezért N része S-nek.

Mivel: S része N-nek, és N része S-nek, ezért S = N

Egyszerűbben: Indirekten tegyük fel, hogy van legalább egy olyan nemnegatív egész, amelyre az A állítás nem igaz. Legyen ezek közül m a legkisebb; m=0 esetén ellentmondásba kerültünk azzal a kezdőfeltétellel, hogy A(0) igaz, m>0 esetén viszont abból, hogy A(m-1) igaz (hiszen m a legkisebb olyan érték, amelyre A hamis) és az indukciós feltételből következik az ellentmondás. Tehát az indirekt feltevés hamis, nincs olyan nemnegatív egész, amelyre az A nem teljesül.