logowanie

matematyka » forum » studia » zadanie

Analiza matematyczna, zadanie nr 584

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

student1
postów: 2
2012-11-02 13:50:24

witam potrzebuje pomocy przy 2 zadaniach:
1 wykaż:
$2^{n}$> $n^{16}$
n!>$N^{n}$
2 sprawdź czy są prawdziwe:
log n = O (lg n) ,to te tzw wielkie o
lg n = O (log n)
Błagam o pomoc.
Zdesperowany student.
PS. chyba dobry dział.


tumor
postów: 8085
2012-11-02 14:38:33

2. $log n = \frac{lg n }{lg 10}$

$3 <lg 10<4$

Zatem istnieją stałe dodatnie $c_1$, $c_2$, że dla $n>1$ mamy
$log n < c_1 lg n$
$lg n < c_2 log n$

Zatem $log n = O(lg n)$ oraz $lg n = O(log n)$.
Zdesperowany student mógłby zauważyć, że poza nowością w notacji ta rzecz jest bardziej niż prosta. Jaka to uczelnia? :)


student1
postów: 2
2012-11-02 14:50:31

PWSiP, muszę to przetrawić:D Zaraz może o coś zapytam.


tumor
postów: 8085
2012-11-02 15:31:52

1.
$2^n>n^{16}$ począwszy od pewnego $n_0$

na przykład dla $n=200$ nierówność jest prawdziwa. Dla wielu mniejszych $n$ też, ale to nieistotne.

Potem można indukcją, albo zauważyć, że $2^x$ ma dla $x>200$ większą pochodną niż $x^{16}$.

Indukcją można tak:
zał. $2^n>n^{16}$

$2^{n+1}=2*2^n$
$(n+1)^{16}<(1,01*n)^{16}=(1,01)^{16}n^{16}<2*n^{16}$

-----

$n!>N^n$

N jest pewną liczbą naturalną. Oczywiście możemy znaleźć takie $p$ naturalne, że $N<p!$
Niech teraz $n_0=(p+1)N-1$.

Wtedy $n_0!=1*2*3*...*N*...*2N*...*pN*...*(p+1)N-1>
N*(N+1)*...*2N*...*pN*...*(p+1)N-1>N^{n_0-N}(p!)^N>N^{n_0-N}N^N=N^{n_0}$

Tu indukcja jest oczywista, lewą stronę mnożymy przez $n+1$, prawą jedynie przez $N$. :)



strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2017 Mariusz Śliwiński      o serwisie | kontakt online: 11 drukuj