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 $\mathrm{M}$ podskup skupa prirodnih brojeva $\mathbb{N}$.

Pretpostavimo dva svojstva skupa $\mathrm{M}$:

1. $1$ $\in \mathrm{M}$
2.   $(\mathrm{\forall }n\in \mathbb{N})(n\in \mathrm{M}\Rightarrow n+1\in \mathrm{M})$
   

Slijedi zaključak: $\mathrm{M}=\mathbb{N}$

Primjeri

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

Dokazujemo da tvrdnja vrijedi za prvi broj u navedenom skupu, a to je "cijeli" skup $\mathbb{N}$, dakle u ovom slučaju za broj 1: $1=\frac{1(1+1)}{2}.$ 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 $\mathbb{N},n_m=m(\ne 1).$ Prema tome, pretpostavljamo da vrijedi $1+2+...+m=\frac{m(m+1)}{2}.$ (*) Ovo se zove pretpostavka indukcije.

Nadodajmo $m+1$ na obje strane jednakosti. Vidimo da tada tvrdnja tada vrijedi i za sljedeći broj, $m+1.$ Dakle, pretpostavljamo da je $1+2+...+m+(m+1)=\frac{(m+1)(m+2)}{2}.$ Sada slijedi ključan korak u ovoj metodi. Prema prvoj pretpostavi lijevu stranu jednakosti (*) možemo napisati kao: $\frac{m(m+1)}{2}+(m+1),$ što daje $\frac{(m+1)(m+2)}{2}.$ Time smo dokazali da ako tvrdnja vrijedi za $m,$ onda nužno vrijedi i za $m+1.$ 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 $\mathrm{\forall }n\in \mathbb{N}.$

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