*POJAM
MATEMATICKE INDUKCIJE I PEANOVI AKSIOMI
Indukcije
pretstavlja zakljucvanje od posebmnog ka opstem. Postoji obicna (empirijska) indukcija kod
koje se iz jednog ili vise posebnih stavova (tzv. premisa) izvode opsti zakljucci tj. novi
stavovi. Empirijska indukcija se upotrebljava u prirodnim naukama, a u matematici u
posljednje vrijeme je smatrana nepouzdanom, nedovoljno valjanom, iako je ranije bila u
upotrebi. Veliki broj naucnika je dokazao netacnost empirijske indukcije.
Npr.:
Formula 1+2+3+...+n=1/2(2*n3-11*n2+23*n-12) tacna je za n=1, n=2 i
n=3, sto se neposredno provjerava direktnom zamjenom. Koristeci se empirijskom indukcijom,
mogli bismo zakljuciti da je ta formula tacna za svaki n pripada N, sto je pogresno.
Zaista, za n=4, data formula je jednaka.
1+2+3+4=1/2(2*43-11*42+23*4-12)
10=1/2(2*64-11*16+92-12)
10=1/2(128-176+80)
10=1/2*32
10=16 =>
nije tacna jednakost, dakle data jednakost ne vrijedi za n=4 tj. nije tacna za
svako n pripada N.
2.)
Brojevi oblika an=n2+n+41, n=1, 2, 3, ... su prosti za n=1, 2, 3,
...39. Medjutim za n=40 dobijamo da je a40=4o2+40+41=402+2*40+1=(40+1)2=412,
a broj 412je slozen broj.
3.)
Fermaovi brojevi su brojevi oblika Fn=22n+1, n=0, 1, ...S obzirom da
su brojevi F0=3, F1=5, F2=17, F3=257, F4=65537
prosti, Ferma je iznio hipotezu da su svi
brojevi Fn takodje prosti. Ovu hipotezu je 1732. god. oborio Ojler
dokazavsi da
je za
*Zato se uvodi tzv.
matematicka indukcija.
NJom se mnogi stavovi strogo dokazuju.
Princip
matematicke indukcije se zasniva na postulatu Peanovih aksioma, o skupu prirodnih brojeva
i glasi:
Odredjena
tvrdnja P(n) je tacna za sve prirodne brojeve n=1, 2, 3, ... ako je:
1) P(1)
tacno
2) ako je za svaki prirodan broj n
tacna implikacija
P(n) => P(n+1)
Prva
od gornjih tacaka se zove POCETNI KORAK
INDUKCIJE. ( To, u stvari, ne mora biti broj 1, vec bilo koji prirodan broj, ali
tada tvrdnja vazi za sve brojeve pocev od tog pocetnog broja.). Pretpostavka da je iskaz
P(n) tacan u dokazu implikacija u 2.) naziva se INDUKCIONA PRETPOSTAVKA (PRETPOSTAVKA INDUKCIJE).
PRIMJEDBA
1: Da bi se dokazala tacnost implikacije P(n) => P(n+1), u skladu sa njenom
definicijom, dovoljno je dokazati da je iskaz P(n+1) tacan ako je tacan iskaz P(n).
Zbog
toga pretpostavljamo da relacija P(n) vrijedi za neko k=n (da je relacija istinita). Zatim
dokazujemo da vrijedi za njegovog sljedbenika n=k+1 tj. uvijek treba dokazati implikaciju
P(k) => P(k+1). Iz dokazane implikacije slijedi da je stav P(n) istinit za
PRIMJEDBA
2: U nekim slucajevima u indukcionoj pretpostavci se, umjesto pretpostavke da tvrdnja
vrijedi za neki broj n, uzima pretpostavka da ona vrijedi za sve brojeve manje ili jednake
n. Neki matematicari zahtjev 2.) nazivaju djavoljom lemom (lema (lat. )-pomocna teorema,
pomocni stav). Moze se, naime, desiti da su sve implikacije u 2.) tacne, a da tvrdnja
jos
uvijek nije tacna ni za jedan prirodan broj. Za to treba biti ispunjen i uslov 1.). To
znaci da, kada tvrdnja vrijedi za jedan prirodan broj, ona tada vrijedi za sve prirpodne
brojevre pocev od tog broja, kao kad djavolu damo jedan prst, a on uzme cijelu ruku.
PRIMJER
1: Dokazati da vrijedi tvrdnja
1+2+3+...+n=n(n+1)/2
Dokaz
tvrdnje pod 1.)
Ispitujemo
da li tvrdnja vrijedi za prvi broj
za
n=1 => 1=1(1+1)/2
1=1*2/2
1=1 => 1 pripada N
2.)
pretpostavimo da data relacija
P(k):
1+2+3+...+k=k(k+1)/2
vrijedi
za neko k pripada N.
DOKAZ:
Dodajemo i lijevoj i desnoj strani sljedeci, u obliku kako je definisan, posljednji
element
=>
1+2+3+...+k+(k+1)=(k(k+1))/2+(k+1)
1+2+3+...+k+(k+1)=(k(k+1)
+ 2(k+1))/2
=(k+1)(k+2)/2
=(k+1)((k+1)+1)/2 =>
k+1 pripada N
ZAKLJUCAK: Dokazali smo da
je tvrdnja P(n) tacna pod 1.) i pod 2.), to znaci da data tvrdnja vrijedi za sve prirodne
brojeve.
Kao
sto postoje i razlicite vrste
indukcije (spomenuli smo empiijsku i matematicku) tako postoje razlicite vrste
matematicke
indukcije.
1.) Princip totalne indukcije
je vec spomenuti oblik matematicke indukcije koji slijedi iz postulata Peanovih aksioma i
ciji je metod dokazivanja vec objasnjen na primjeru 1. Princip totalne indukcije daje
pregled o skupu prirodnih brojeva. Princip totalne indukcije mozemo i ovako formulisati:
1) Ako
precrtamo broj 1
2) Ako nadalje
precrtavsi neki prirodan broj n, precrtamo i broj n+1, onda cemo precrtati svaki prirodan
broj.
Primjene principa totalne indukcij
primjer 1.1 -
uredjenje skupa N
TEOREMA: "Skup prirodnih brojeva je uredjen po velicini tj. za svaka dva prirodna broja k, m ili je k=m ili je k<m li je k>m."
*Treoremu
cemo dokazati totalnom
indukcijom s obzirom na k.
DOKAZ:
za k=1
=> 1<m za svako m pripada
N
pretpostavimo da je teorema dokazana za
neko k=n pripada N i dokazujemo za k=n+1, gdje za
m<k
=> m<k+1 (zbog k<k+1)
m=k
=> m<k+1 (zbog k<k+1)
m>k
=> m>=k+1 (prema relaciji da za ma koja prirodna dva broja m
i n vazi da iz m>n =>
m>=n+1)
Dakle, uistinu je ili m<k+1 ili m=k+1
ili m>k+1 => k+1 pripada N
Dokazana je trorema pod 1.) i pod 2.),
dakle teorema vazi za svako k,m pripada N.
2.)
Cest je slucaj da neko tvrdjenje ne vazi za sve prirodne brojeve, samo za one koji su
veci
ili jednaki od nekog k. U tom slucaju dokazivanje metodom
matematicke
indukcije sprovodi se na sljedeci nacin:
1) Provjeri se
tacnost tvrdjenje P(k)
2) Dokaze se da za bilo koje n>k iz
tacnosti tvrdjenja P(n) slijedi i tacnost tvrdjenje P(n+1)
U
obliku formule:
P(k)
i ("n) (n>k => (P(n)=>P(n+1)) => ("n)(n>k => P(n))
primjer 2.1:
Nejednakost
2n>n2 ...(1) je za
n=1 => 21>12 => 2>1
=> nejednakost je tacna
n=2 =>
22>22 =>
4>4 => nejednakost nije
tacna
n=3 => 23>32 => 8>9
=> nejednakost nije tacna
n=4 => 24>42 => 16>16 => nejednakost nije
tacna
Matematickom
indukcijom dokaujemo da je ona tacna za svaki prirodan broj n>5
za
n=5 => 25>52 => 32>25 => nejednakost je tacna
Pretpostavimo
da je jednakost tacna za neko fiksirano n (n>5)
Ako
je n>5, tada je
1/n<1/5
i 1/n2<1/25
Onda
je
(n+1)2/n2=(1+1/n)2=1+2/n+1/n2
1+2/n+1/n2<1+2/n+1/25
i 1+2/5+1/25<2
=> 2>(n+1)2/n2 ...(2)
Mnozeci
zadanu jednakost (1) sa (2) dobijamo
2n*2>n2*(n+1)2/n2
2
n+1>(n+1)2 => nejednakost je tacna za n+1, n>=5,
indukcioni dokaz je zavrsen.
3.) Dokaz matematickom indukcijom da je
tvrdjenje P(n) tacno za svaki
prirodan broj n moze se dokazati na sljedeci nacin:
1) Dokaze se
tacnost tvrdjenja P(0), P(1), P(2),
...P(m), gdje je m neki odredjeni prirodan broj
2) Dokaze se da iz
tacnosti tvrdjenja P(n), P(n+1),
...P(n+m) uvijek izlazi i tacnost tvrdjenja P(n+m+1)
U
obliku formule:
P(0)
i P(1) i ...i P(m) i ("n) (P(n) i P(n+1) i ... i P(n+m) => P(n+m+1))
=>
primjer
3.1:
Dokazati
matematickom indukcijom da je
an=51/2/5((1+51/2)/2)n-51/2/5((1-51/2)/2)n
prirodan
broj za svako n pripada N
DOKAZ:
1.) za n=1 => a1=51/2/5*(1+51/2)/2-51/2/5*(1-51/2)/2=51/2/5((1+51/2)/2-(1-51/2)/2)=51/2/5*(1+51/2-1+51/2)/2=
=51/2/5*2*251/2/2=51/2/5*51/2=5/5=1 =>
a1 pripada N
za n=2 => a2=51/2/5((1+51/2)/2)2-/5((1-51/2)/2)2=
=51/2/5((1+2*51/2+5)/4)-51/2/5((1-2*51/2+5)/4)=51/2/5*(1+2*51/2+5-(1-2*51/2+5))/4=
=51/2/5(1+2*51/2+5-1+2*51/2-5)/4=51/2/5*4*51/2/4=51/2/5*51/2=5/5=1 =>
a2 pripada N
S
druge strane je
an+a n+1=51/2/5((1+51/2/2)n+(1+51/2/2)n+1)- 51/2/5((1-51/2/2)n+(1-51/2/2)n+1)=51/2/5(1+51/2/2)n(1+(1+51/2)/2)-51/2/5(1-51/2/2)n(1+(1-51/2)/2)=
=51/2/5(1+51/2/2)n*(2+1+51/2)/2-51/2/5(1-51/2/2)n((2+1-51/2)/2)=
=51/2/5(1+51/2/2)n*(3+51/2)/2-51/2/5(1-51/2/2)n*(3-51/2)/2=
=51/2/5(1+51/2/2)n+2-51/2/5(1-51/2/2)n+2,
jer je
(1+51/2/2)2=(1+2*51/2+5)/4=(6+2*51/2)/4=2(3+51/2)/4=(3+51/2)/2
(1-51/2)/2=(1-2*51/2+5)/4=(6-2*51/2)/4=2(3-51/2)/4=(3-51/2)/2
Prema
tome, dokazano je da je an+an+1=an+2, n=1, 2. 3,
...Pretpostavimo da su an i an+1 prirodni brojevi. Na osnovu
prethodne jednakosti slijedi da je i an+2 prirodan broj. Dakle, a1 i a2
su prirodni brojevi i an+an+1=a n+2, onda na osnovu
principa matem. indukcije zakljucujemo da je i broj an prirodan za svako n
pripada N.
Transfinitna
indukcija je jedan
vazn oblik indukcije. Dokazivanje transfinitnom indukcijom vrsi se na sljedeci
nacin:
1) Dokaze se
tacnost tvrdjenje P(0)
2) Dokaze se da iz
tacnost tvrdjenja P(0), P(1),
P(2), ... P(n) uvijek slijedi tacnost tvrdjenja P(n+1)
U
obliku formule
P(0)
i ("n)(P(0) i P(1) i ... i P(n) => P(n+1) ) => ("n) P(n)
primjer 4.1:
Osnovna teorema aritmetike:"Svaki prirodan broj (>1) je ili prost ili proizvod prostih brojeva."
DOKAZ:
P(n):
n je prost broj ili je proizvod prostih brojeva
1) za n=2
=> P(2) je tacno
tvrdjenje,
jer je 2 prost broj
2) Neka je n bilo koji prirodan broj. Pretpostavimo
da tvrdjenje vazi za svako k, k<n
Broj
n+1 je prost ili slozen. Ako je prost tada je P(n+1) tacno.
Pretpostavimo
da je broj n+1 slozen. Ako je slozen, onda ga mozemo napisati u obliku n+1=m*k, za neke
prirodne brojeve k, m razlicite od 1
Otuda
k, m <n+1 tj. k.,m <=n
Prema
indukcionoj hipotezi je P(k) i P(m) tj. k, m su proizvodi prostih brojeva ili su sami
prosti brojevi. Otuda slijedi da je n+1 proizvodih prostih brojeva => P(n+1), dakle
teorema je tacna za svaki n pripada N.
12+22+32+...+n2=(n(n+1)(2n+1))/6
Dokaz:
1.) za n=1 =>
12=1(1+1)(2*1+1)/6
1=1*2*3/6
1=6/6
1=1 => 1 pripada N
za n=2
=> 12+22=2(2+1)(2*2+1)/6
1+4 =2*3*5/6
5=6*5/6
5=5 => 2 pripada N
2.) pretpostavimo da izraz
vrijedi za neko k pripada N i dokazujemo
za sljedeci k+1
=>
12+22+32+...+k2+(k+1)2=(k(k+1)(2k+1))/6+(k+1)2
=k(k+1)((2k+1)+6(k+1)(k+1))/6=
=(k+1)(k(2k+1)+6(k+1))/6=
=(k+1)(2k2+k+6k+6)/6=
=(k+1)(2k2+7k+6)/6=
=(k+1)(2k2+4k+3k+6)/6=
=(k+1)(k+2)(2k+3)/6=
=(k+1)(2k(k+2) + 3(k+2)=
=(k+1)((k+1)+1)(2(k+1)+1)/6 =>
Data jednakost vrijedi pod 1.) i pod
2.), sto znaci da data jednakost vrijedi za svako n pripada N, sto je i trebalo dokazati.
PRIMJER
3: Matematickom indukcijom dokazati da za sve prirodne brojeve
vazi da je
f(n)=22n+1-9n2+3n-2
djeljivo sa 54.
DOKAZ:
za
n=1 => f(1)=22*1+1-9*12+3*1-2=8-9+3-2=0=0*54 =>
54djf(1) => 1 pripada N
za n=2 => f(2)=22*2+1-9*22+3*2-2=25-36+6-2=32-36+4=-4+4=0=0*54 => 54dj f(2) =>
=>
2 preipada N
Pretpostavimo
da je f(k)=22k+1-9*k2+3*k-2 za neko k N djeljivo sa 54 i dokazujemo
da je djeljiv za njegov sljedbenik k+1
f(k+1)=22(k+1)
+1-9(k+1)2+3(k+1)-2=22k+2+1-9*k2-18*k-9+3*k+3-2=
=22*22k+1-9*k2-15*k-8=4*22k+1-4*9*k2+4*3k-4*2+27*k2-27*k=
=4(22k+1-9*k2+3*k-2)
+27*k(k-1)=4*f(k)+27*k(k-1)
Prvi
sabirak 4*f(k) je, po pretpostavci, djeljiv sa 54. Drugi sabirak 27*k(k-1) je djeljiv sa
27 i ostaje da dokazemo da je k(k-1) djeljivo sa 2. Brojevi k-1 i k su dva uzastopna
prirodna broja ( od kojih je bar jedan paran broj), onda je njihov proizvod k(k-1) djeljiv
sa 2. Onda je i 27*k(k-1) djeljivo sa 54 tj. 54dj4*f(k)+27*k(k-1) =>
54djf(n) za svako n pripada N.
Dokazali
smo da tvrdnja vrijedi pod 1.) i pod 2.), sto znaci da 54djf(n) za
svako n pripada N.
Matematicka
indukcija je primjer najsigurnijeg zakljucivanja. Jos od pojave induktivnog
zakljucivanja,
pa preko empirijske indukcije sve do matematicke indukcije razvija se proces
logickog zakljucivanja, gdje se tezi pronalasku sigurnog puta za otkrivanje istinitih teorema i
stavova u oblasti matematike.
Matematickom
indukcijom se mnogi stavovi strgo dokazuju. Princip matematicke indukcije je princip koji
se koristi za dokazivanje teorema iz skoro svih oblasti matematike.
Postoji
nekoliko tipova matematicke indukcije:
1) totalna indukcija
2) indukcija u kojoj se posmatra skup brojeva
veci
ili jednakih od nekog k (>k)
3) indukcija sa
vise hipoteza
4) transfinitna indukcija
Sve
se one zasnivaju na postulatu Peanovih aksioma:
Odredjena
tvrdnja P(n) je tacna za sve prirodne brojeve n=1, 2, 3, ... ako je:
1) P(1)
tacno
2) ako je za svaki prirodan broj n
tacna implikacija
P(n) => P(n+1)
Prethodno
su pokazane brojne primjene ovog principa zakljucivanja na brojne teoreme iz svih oblasti
matematike, npr. o uredjenju skupa prirodnih brojeva, princip minimuma za prirodne brojeve,
osnovna teorema aritmetike, itd. Pomocu ovog principa otkrivene su mnoge neistinite
tvrdnje u oblasti matematike npr. Fermaovi brojevi22n+1, za koje se smatralo da su prosti
za svako n pripada N, a dokazalo se da to nije istina tj. da je ovaj broj slozen
cak za "n>=5. Matematicka indukcija ima primjenu u svim naukama,
a posebno u matematici.
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |