Matematička indukcija - Uvod

itc »Strukture podataka i algoritmi » Matematička indukcija » Uvod

Matematička indukcija igra značajnu ulogu pri konstrukciji mnogih algoritama.
Zbog toga se u ovom uvodnom poglavlju analizira nekoliko karakterističnih primera primene indukcije.

Neka je $N=\{1,2,3,...\}$ skup prirodnih brojeva.
Princip matematičke indukcije može se formulisati na sledeći način.
Pretpostavimo da treba dokazati da je tvrđenje $T(n)$ tačno za svaki prirodan broj $n \in N$. Umesto da se ovo tvrdjenje "napada" direktno, dovoljno je dokazati sledeća dva tvrđenja:

  • $T(n)$ je tačno za $n=1$ ,
  • za svako $n > 1$ važi : ako je tačno $T(n-1)$, onda je tačno i $T(n)$.

Ova činjenica je takozvani princip indukcije, i predstavlja ustvari aksiomu, koja definiše skup prirodnih brojeva.
U praksi se obično prvo tvrđenje, koje se zove još i baza indukcije lako dokazuje.
Dokaz drugog tvrđenja olakšan je pretpostavkom da je tačno $T(n -1)$, takozvanom induktivnom hipotezom.
Drugim rečima, dovoljno je tvrđenje svesti na slučaj kad je n umanjeno za jedan.
Ilustrovaćemo to jednim jednostavnim primerom :

Teorema 1.1 Za svaka dva broja $x,n \in N$ vazi $x-1 | x^n-1$.
Dokaz :
Dokaz se izvodi indukcijom po $n$ .
Za $n=1$ tvrdjenje glasi $x-1 | x^1 - 1$, što je naravno tačno.
Svođenje slučaja $n$ na slučaj $n-1$ se zasniva na izrazu
$x^n-1 = (x^n^-^1-1)x + (x-1)$ , jer on pokazuje da iz induktivne hipoteze $x-1 | x^n^-^1-1$ sledi da je $x-1 | x^n-1$ tačno.

Princip matematičke indukcije često se koristi u nešto promenjenim oblicima, koji su neposredna posledica osnovnog.


Teorema 1.2 Ako je tačno tvrđenje $P(1)$ i za sveko $n>1$ iz pretpostavke da je $P(k)$ tačno za svako $k<n$ sledi tačnost $P(n)$, onda je $P(n)$ tačno za svako $n \in N$.

Ovo je takozvana potpuna indukcija, a dobija se od osnovne varijante primenom na tvrđenje $T(n)=\bigwedge_{k=1}^n P(K)$.


Teorema 1.3 (Regresivna indukcija). Neka ja $a1, a2, ...$ rastići niz prirodnih brojeva. Ako je tvrđenje $P(n)$ tačno za $n=a_{k}, k=1,2,...$ i za svako $n>=2$ iz pretpostavke da je tačno $P(n)$ sledi da je tačno $P(n-1)$ , tada je $P(n)$ tačno za svako $n \in N$.

Prvi deo pretpostavke, da je tačno $P(_{a_{k}})$ tačno za $k>=1$ dokazuje se indukcijom $( P(1)$, i ako $P(_a_{k})$ onda $P(_{a_{k+1}}), k>=1)$. Dakle, najpre se dokazuje da postoje proizvoljno veliki brojevi $n$ takvi da je $P(n)$ tačno, a onda da je $P(n)$ tačno za i za sve izostavljene brojeve. Ovo je takozvana regresivna indukcija

Unless otherwise stated, the content of this page is licensed under GNU Free Documentation License.