Matematična indukcija

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Matematična indukcija je metoda dokazovanja oziroma kombinatorno pravilo, s katero dokazujemo pravilnost neke trditve P(n), ki je odvisna od naravnega števila n, za vsa naravna števila.

Splošen opis

Osnovna oblika indukcije:

Baza indukcije
Dokažemo P(0).
Indukcijski korak
Dokažemo P(n) → P(n+1).

Običajno dokazujemo, da neka trditev velja za vsa naravna števila n. Postopek gre na sledeč način:

  1. Dokažemo za prvi primer, torej recimo n = 1,
  2. nato pa napravimo indukcijski korak: pokažemo, da če trditev velja za n = m, potem ista trditev velja za n = m + 1.

Predpostavko, ki sledi besedi "če" v indukcijskem koraku imenujemo tudi indukcijska predpostavka. Torej, da naredimo indukcijski korak, najprej predpostavimo, 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.

Ob tej osnovni obliki obstajajo tudi različice indukcije. Na primer, v bazi indukcije lahko namesto P(0) dokažemo P(a), za kakšno majhno vrednost a. V tem primeru po končanem dokazu velja trditev za vsa naravna števila n ≥ a.

Primer

Recimo, da želimo dokazati naslednjo trditev:

1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}

za vsa naravna števila n.

Pogledamo za n = 1. Očitno 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,

1 + 2 + \cdots + m = \frac{m(m + 1)}{2}

Naredimo indukcijski korak m -> m + 1 (na obeh straneh dodamo v enačbo še (m+1))

1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (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):

= \frac{m(m + 1)}{2} + \frac{2(m + 1)}{2} = \frac{(m^2 + 3m + 2)}{2} = \frac{(m + 2)(m + 1)}{2} = \frac{(m + 1)((m + 1) + 1)}{2}.

Tako dobimo:

1 + 2 + \cdots + (m + 1) = \frac{(m + 1)((m + 1) + 1)}{2}

To pa je enačba za n = m + 1.

S tem smo dokazali, da trditev velja za vsa naravna števila.

Osebna orodja