Esetleg tudja valki, ezt a feladatot hogyan kell megoldani?

Mint ahogyan írtad is, felső korlátot keresünk, pontosabban olyan függvényt, amely egy adott pont után biztosan nagyobb lesz; úgyis mondhatnám, hogy az egyik függvény futóversenyen valamikor "megelőzi" a másik függvényt úgy, hogy az már nem előzi vissza.

Elvileg tanultatok nagyságrendeket függvények esetén, valami ilyesmi volt;

konstans < polinom < exponenciális < faktoriális < ..., bár itt most azonos fajtájú függvénnyel kell becsülni.

Azt megtanultátok, hogy nagyobb fokszámú polinommal mindig lehet felülről becsülni (például a 1000000000000 x^2 < x^3 valamikor teljesülni fog biztosan), exponenciális függvények esetén pedig az alapot kell csak megváltoztatni, agyis nagyobb alappal lehet felülről becsülni.

Akkor most a feladatok;

A) Gyakorlatilag az a kérdés, hogy tetszőleges (pozitív) c számra lesz-e olyan x, hogy onnantól kezdve a

2^(2n+1) < c*2^n mindig teljesülni fog. Hamar rá lehet jönni, hogy ez nem lesz igaz; a bal oldal a tanultak szerint átírható így:

2*4^n < c*2^n, és ahogyan az előbb írtam, nagyobb alapú exponenciális függvénnyel lehet felülről becsülni, fordítva nem megy, tehát ez alapján bizotsan hamis lesz. Ha ezt esetleg nem tudnánk, akkor sincs nagy probléma. Térjünk vissza az eredeti alakra:

2^(2n+1) < c*2^n, osztunk 2^n-nel, ami értelemszerűen mindig pozitív

2^(n+1) < c, ami soha nem lesz igaz tetszőleges n-re. Tehát a 2^n alakú függvények nem lehetnek felső becslései a bal oldalnak.

B) Hasonlóan, mint az előbb;

(2n+5)^3 < c*n^3, itt nem nehéz belátni, hogy például c=27 jó lesz nekünk;

(2n+3)^3 < 27*n^3, köbgyököt vonunk

2n+3 < 3n, kivonunk 2n-t

3 < n, tehát ha c=27, akkor már a sorozat 4. tagjától kezdve nagyobb lesz a bal oldal. Tehát a jobb oldal felülről becsülhető O(n^3)-nal.

Ezek mintájára megpróbálod a C)-t megoldani?

De miért osztottad n^3-bel? Nem értem...

Azt kell csak belátni például, hogy van olyan n, melytől kezdve minden n-re

3n^2+2n+1 < n^3 (itt most c-t 1nek választottam). Ha ez teljesül, akkor örülünk, mint majom a farkának, ha nem, akkor keresni kell egy másik c-t. Ha olyan szerencsétlenek vagyunk, hogy egyik c sem jó, akkor azt kell sejtenünk, hogy egyik sem lesz jó, ekkor viszont be kell látni, hogy tetszőleges c-re a fordítottja lesz igaz, vagyis

3n^2+2n+1 > c*n^3

Valójában az összes c igaz lesz, tehát definíció szerint:

[link]

igaz lesz az állítás. A beugratás az ebben a feladatban egyébként, hogy ennek a sorozatnak a nagyságrendje valójában O(n^2) (4n^2-tel lehet felülről becsülni), ezért azt mondanánk, hogy ez az állítás hamis, viszont a való életben is van olyan, hogy egy folyamatot tudunk valamivel felülről becsülni, aztán jóval később derül ki, hogy jobban/kisebb függvénnyel is lehet felülről becsülni.

Szóval első körben annyi a dolgod, hogy a

3n^2+2n+1 < n^3

egyenlőtlenségnek megállapítod, hogy egy adott n-től (amit amúgy küszöbszámnak vagy -indexnek szoktunk hívni) kezdve a nála nagyobb n-ek is mind megoldásai-e vagy sem. Ha igen, akkor igaz az állítás, ha nem, akkor még számolgass egy kicsit.

Egyébként ha n^3-bel osztasz, akkor ezt kapod:

(3/n)+(2/n^2)+(1/n^3)<c

Itt azért rá lehet jönni, hogy a 3/n, a 2/n^2 és az 1/n^3 is mind 0-hoz tart, hogyha n->végtelen, szóval tetszőleges pozitív c-re igaz lesz valamikortól az egyenlőtlenség.