Matematička indukcija i njena primena
Svaki neprazan podskup prirodnih brojeva ima minimalni elemenat u odnosu na relaciju <. Zahvaljujući ovoj osobini mažemo koristiti sledeći princip matematičke indukcije.
Teorema (Matematička indukcija na N) Tvrdđnje T(n); n ∈ N je tačno za svaki prirodan broj n ∈ N ako:
- Za n = 1, T(n) odnosno T(1) je tačno tvrđnje;
- Iz pretpostavke da je za proizvoljno n ∈ N tačno tvrđnje T(n) sledi da je T(n + 1) tačno tvrđenje , odnosno implikacijaT(n)⇒T(n + 1) je tačna za svaki prirodan broj n.
Matematička indukcija se koristi za dokazivanje tvrđnja koja zavisi od prirodnog broja n i važe na nekom podskupu prirodnih brojeva n0, n0+1, …
U dokazivanju tvrđenja koristićemo sledeće korake:
- Proverimo da li je tvrdjenje tačno za n = 1
- Predpostavimo da je tvrdjenje tačno za n = k
- Dokazujemo da je tvrdjenje tačno za n = k+1
Matematička indukcija je metod matematičkog dokazivanja koji se obično koristi da se utvrdi da je dati iskaz tačan za sve prirodne brojeve
Matematičku indukciju koristimo kao mtod kojim se dokazuje da je neko tvrđenje tačno za sve prirodne brojeve kao dokaz jednakosti, nejednakosti , kongruencije.
Dešava se da rešavanjem nekog zadatka koristimo matematičku indukciju više puta.
Zadatak 1.
Dokazati da je \( 1+2+3+…+n=\frac{n(n+1)}{2} \)
Prvi korak
\( n \) određuje broj članova sa leve strane a sa dense menjamo \( n \) sa 1. Za \( n=1 \) tvrđenje postaje \( 1=\frac{1 (1+1)}{2} \iff 1=\frac{2}{2}\iff 1=1 \) tvrđenje je tačno
Drugi korak
Uzimamo kao tačan bez dokaza za n=k \( 1+2+3+…+k=\frac{k(k+1)}{2} \) indukcijska pretpostavka.
Treći korak
Za \( n=k+1 \) sa leve strane dodajemo \( (k+1). \) član a sa desne menjamo \( n \) sa \( k+1 \), \( \frac{(k+1)(k+1+1)}{2} \)
\( 1+2+3+…+k+(k+1)=\frac{(k+1)(k+1+1)}{2} \)
u koraku 2. imamo da je \( 1+2+3+…+k=\frac{k(k+1)}{2} \) primenjujemo na prethodni red
\( \frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}⇒\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}⇒\frac{(k+1)(k+2)}{2}=\frac{(k+1)(k+2)}{2} \)
\( \frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}⇒\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}⇒\frac{(k+1)(k+2)}{2}=\frac{(k+1)(k+2)}{2} \)
Tvrđenje je dokazano.
Kongruencije -matematička indukcija
Zadatak 2:
Zadatak 3:
Zadatak 4:
