Popolna indukcija
Iz o KvarkaWiki
Popolna (matematična) indukcija je metoda, s katero preverjamo veljavnost neke prepostavke za vsa naravna števila. Kot taka je zelo uporabna na mnogih področjih matematike.
Splošen opis
Popolno indukcijo uporabimo za dokazovanje neke trditve v neskončno mnogih primerih. To naredimo na sledeč način:
- prvo dokažemo da za prvi primer trditve, od neskončno mnogih, trditev drži (s tem se morebitno izognemo brezpomenskemu dokazovanju za vsa število, saj če ne drži za prvi primer, sigurno ne drži za vse)
- nato dokažemo da velja za vse mogoče primere
Praktičnejši opis
Najbolj običajno dokazujemo da neka trditev velja za vsa naravna števila n. Kot zgoraj omenjeno gre postopek na sledeč način:
- dokažemo za prvi primer, torej recimo n = 1
- nato pa induktivni korak: pokažemo da če trditev velja za n = m, potem ista trditev velja za n = m + 1.
Predpostavko, ki sledi besedi "če" v induktivnem koraku imenujemo tudi indukcijska predpostavka. Torej, da naredimo indukcijski korak najprej prepostavimo da trditev velja za n = m, nato uporabimo indukcijsko prepostavko v n = m + 1.
Na ta način dokažemo da trditev velja za vse n. To si lahko predstavljamo kot domine; najprej poderemo eno, naslednje pa padejo samodejno.
Primer
Recimo da želimo dokazati naslednjo trditev:
za vsa naravna števila n.
- Pogledamo za n = 1. Očitno za n= 1 tole velja, saj je na levi in desni strani enačaja ista številka (1 = 1).
- Nato predpostavimo da trditev velja za vse n = m (indukcijska predpostavka), potem mora veljati tudi za n = m + 1. To naredimo na sledeč način:
Privzamemo indukcijsko predpostavko: n = m,
Naredimo indukcijski korak m -> m + 1 (očitno, na obeh straneh dodamo (m+1))
Nato desno stran enačbe preuredimo tako, da v njej opazimo podobnost z enačbo za m + 1 (torej, če bi na začetku namesto m vstavili m + 1):
Tako dobimo:
To pa je enačba za n = m + 1.
S tem smo dokazali da trditev velja za vsa naravna števila.
