MATEMANIJA

Imam problema sa razumevanjem indukcije kod nejednačina. Na primer, zadatak glasi:
matematičkom indukcijom dokazati da je [inlmath]n^2<2^n[/inlmath] ako je [inlmath]\forall n\in\mathbb{N}[/inlmath] i ako je [inlmath]n\geq5[/inlmath]
1) baza indukcije: za [inlmath]n=5[/inlmath], imamo da je [inlmath]5^2<2^5[/inlmath] pa sledi da je [inlmath]25<32[/inlmath] što je tačno.
2) induktivni korak: pretpostavljamo da je tačno i za [inlmath]n+1[/inlmath], pa onda imamo sledeće:
[dispmath](n+1)^2<2^{n+1}[/dispmath][dispmath]n^2+2n+1<2^n\cdot2[/dispmath][dispmath]n^2+2n+1<n^2\cdot2[/dispmath]
Ovo je slučaj "zamene" [inlmath]2^n[/inlmath] iz drugog reda sa [inlmath]n^2[/inlmath] iz hipoteze ( [inlmath]n^2<2^n[/inlmath]). Kada sredimo, dobijamo izraz [inlmath]2n+1<5[/inlmath], pa kada proverimo sa nekim [inlmath]n[/inlmath] koje je veće ili jednako od [inlmath]5[/inlmath], na primer, [inlmath]n=5[/inlmath] , onda dobijemo da je [inlmath]2\cdot5+1<5^2[/inlmath], tj. [inlmath]11<25[/inlmath] , što je tačno.
Meni nije jasna ta "smena" [inlmath]2^n[/inlmath] sa [inlmath]n^2[/inlmath], zašto je to moguće? Jasno je da je [inlmath]n^2[/inlmath] manje od [inlmath]2^n[/inlmath], tako da mi u suštini tvrdimo da nešto što je sa desne strane znaka [inlmath]<[/inlmath] i dalje veće od onoga sa leve strane tog znaka iako je jasno da je ta vrednost sa desne strane sada manja nego pre te "smene" jer [inlmath]n^2\cdot2[/inlmath] ima manju vrednost od [inlmath]2^n\cdot2[/inlmath]. Kako nešto tako i dalje možemo da tvrdimo, na osnovu čega?
Ako u drugom slučaju, umesto [inlmath]2^n[/inlmath] iz drugog reda zamenimo [inlmath]n^2[/inlmath], dobićemo [inlmath]2^n+2n+1<2^n\cdot2[/inlmath] , pa kada sredimo i proverimo sa [inlmath]5[/inlmath], dobijamo opet tačan iskaz: [inlmath]21,5<32[/inlmath]. Ovde smo ubacili sa leve strane veću vrednost ([inlmath]2^n[/inlmath] je veće od [inlmath]n^2[/inlmath] ) a i dalje tvrdimo da je iskaz sa leve strane manji od iskaza sa desne strane, iako je tačno, verujem da postoje neki primeri gde ta "smena" neće biti moguća ili grešim?

2. Induktivna hipoteza [inlmath]2^n>n^2[/inlmath]
3. Trebamo dokazati
[dispmath]2^{n+1}>(n+1)^2[/dispmath][dispmath]2\cdot2^n>n^2+2n+1[/dispmath]
Pomnožimo IH sa [inlmath]2[/inlmath]:
[dispmath]2\cdot2^n>2\cdot n^2=n^2+n^2>n^2+2n+1[/dispmath]
Samo još treba pokazati da je [inlmath]n^2>2n+1[/inlmath]
Kao što vidiš nisam koristio nikakvu smjenu, vjerovatno si se zbunio jer ti je falilo par koraka.

smarko1983 je napisao:Meni nije jasna ta "smena" [inlmath]2^n[/inlmath] sa [inlmath]n^2[/inlmath], zašto je to moguće? Jasno je da je [inlmath]n^2[/inlmath] manje od [inlmath]2^n[/inlmath], tako da mi u suštini tvrdimo da nešto što je sa desne strane znaka [inlmath]<[/inlmath] i dalje veće od onoga sa leve strane tog znaka iako je jasno da je ta vrednost sa desne strane sada manja nego pre te "smene" jer [inlmath]n^2\cdot2[/inlmath] ima manju vrednost od [inlmath]2^n\cdot2[/inlmath]. Kako nešto tako i dalje možemo da tvrdimo, na osnovu čega?

Upravo ovo je i mene zbunilo dok sam pratio priloženi postupak, zbog čega ne mislim da bi se takav dokaz mogao smatrati validnim.
Je l' to prepisan postupak iz neke zbirke, ili...?

Potvrđujem ispravnost xyz-ovog dokaza.

@xyz, kako si došao do toga je [inlmath]2\cdot n^2>n^2+2n+1[/inlmath] ? Imaš slučaj da je [inlmath]a>c[/inlmath] i da je [inlmath]a>b[/inlmath] , ne možeš da iskoristiš hipotetički silogizam da zaključiš da je [inlmath]b>c[/inlmath] ili [inlmath]c>b[/inlmath] .

Daniel je napisao:Upravo ovo je i mene zbunilo dok sam pratio priloženi postupak, zbog čega ne mislim da bi se takav dokaz mogao smatrati validnim.
Je l' to prepisan postupak iz neke zbirke, ili...?

Čak sam sad video da ima i grešku:
"...Kada sredimo, dobijamo izraz [inlmath]2n+1<5[/inlmath], pa kada..." Trebalo je da stoji [inlmath]2n+1<n^2[/inlmath].
Mislim da sam prepisao iz neke strane knjige o dokazima, ali se ne sećam koje. Možda je bila "First course in set theory" , mada nisam siguran.

Molim te da izbegavaš citiranje celih postova, time se narušava preglednost, a i protivno je tački 15. Pravilnika. Uklonio/skratio sam suvišne citate.

smarko1983 je napisao:@xyz, kako si došao do toga je [inlmath]2\cdot n^2>n^2+2n+1[/inlmath] ?

Kao što je xyz i napisao,

xyz je napisao:Samo još treba pokazati da je [inlmath]n^2>2n+1[/inlmath]

Dakle, to se naknadno dokazuje. Reši se kvadratna nejednačina i time se pokaže da za zadati interval vrednosti [inlmath]n[/inlmath] nema brige da će ta nejednakost biti zadovoljena.

smarko1983 je napisao:Čak sam sad video da ima i grešku:
"...Kada sredimo, dobijamo izraz [inlmath]2n+1<5[/inlmath], pa kada..." Trebalo je da stoji [inlmath]2n+1<n^2[/inlmath].

Da, to je i mene zbunilo, ali se nakon one prethodne suštinske greške sa [inlmath]a<b\;\land\;c<b\;\Rightarrow\;a<c[/inlmath] nisam dalje nešto ni udubljivao u postupak...