Aksiom matematičke indukcije

Aksiom matematičke indukcije je aksiom o matematičkoj (potpunoj, totalnoj) indukciji. Omogućava da iz izvjesnih svojstava podskupa zaključimo odnos dvaju skupova. Ovim aksiomom se mogućava i sredstvo je za prouučavati beskonačne skupove, za dokazivati poučke i za definiciju funkcija.

Aksiom glasi:

Neka je skup [math]\displaystyle{ \mathrm{M} }[/math] podskup skupa prirodnih brojeva [math]\displaystyle{ \mathbb{N} }[/math].

Pretpostavimo dva svojstva skupa [math]\displaystyle{ \mathrm{M} }[/math]:

1. [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ \in\mathrm{M} }[/math]
2.   [math]\displaystyle{ \left(\forall n\in\mathbb{N} \right) \left (n \in \mathrm{M} \Rightarrow n + 1 \in \mathrm{M} \right ) }[/math]
   

Slijedi zaključak: [math]\displaystyle{ \mathrm{M}=\mathbb{N} }[/math]

Primjeri

Možda najosnovniji primjer za metodu matematičke indukcije je suma konačno mnogo uzastopnih prirodnih brojeva. Želimo li dokazati tvrdnju, odnosno formulu [math]\displaystyle{ 1 + 2 + 3 + \ ... \ + n = \frac{n(n + 1)}{2} }[/math] možemo postupiti ovako:

Dokazujemo da tvrdnja vrijedi za prvi broj u navedenom skupu, a to je "cijeli" skup [math]\displaystyle{ \mathbb{N} }[/math], dakle u ovom slučaju za broj 1: [math]\displaystyle{ 1 = \frac{1(1 + 1)}{2}. }[/math] Time smo dokazali bazu indukcije.

Sada pretpostavljamo da tvrdnja vrijedi barem za jedan broj različit od 1 iz našeg skupa, neka je to m-ti broj iz skupa [math]\displaystyle{ \mathbb{N}, n_m = m \ (\neq 1). }[/math] Prema tome, pretpostavljamo da vrijedi [math]\displaystyle{ 1 + 2 + \ ... \ + m = \frac{m(m + 1)}{2}. }[/math] (*) Ovo se zove pretpostavka indukcije.

Nadodajmo [math]\displaystyle{ m + 1 }[/math] na obje strane jednakosti. Vidimo da tada tvrdnja tada vrijedi i za sljedeći broj, [math]\displaystyle{ m + 1. }[/math] Dakle, pretpostavljamo da je [math]\displaystyle{ 1 + 2 + \ ... \ + m + (m + 1) = \frac{(m + 1)(m + 2)}{2}. }[/math] Sada slijedi ključan korak u ovoj metodi. Prema prvoj pretpostavi lijevu stranu jednakosti (*) možemo napisati kao: [math]\displaystyle{ \frac{m(m + 1)}{2} + (m + 1), }[/math] što daje [math]\displaystyle{ \frac{(m + 1)(m + 2)}{2}. }[/math] Time smo dokazali da ako tvrdnja vrijedi za [math]\displaystyle{ m, }[/math] onda nužno vrijedi i za [math]\displaystyle{ m + 1. }[/math] Ovaj se dio naziva korakom indukcije.

Pokazali smo da tvrdnja vrijedi za 1. No, onda vrijedi i za 2, onda i za 3, itd. Time smo dokazali da tvrdnja vrijedi [math]\displaystyle{ \forall n \in \mathbb{N}. }[/math]

Sada je jasan aksiom matematičke indukcije.

Izvori

1. Kurepa, Svetozar. Matematička analiza 1. Diferenciranje i integriranje. Zagreb: Školska knjiga, 1997.; str. 17-18