szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 11 maja 2018, o 15:15 
Użytkownik

Posty: 8
Lokalizacja: Warszawa
Witam,
Mam problem z zadaniem:
Znajdź możliwe najlepsze oszacowanie:

{n ^{2}\choose n}  =O(?).

Wiem że można skorzystać ze wzoru Stirlinga ale nie wiem jak to zrobić i jak wyliczyć ile wyniesie notacja O.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Online
PostNapisane: 11 maja 2018, o 17:18 
Użytkownik
Avatar użytkownika

Posty: 2375
Lokalizacja: Katowice
Najlepsze oszacowanie to chyba

{n ^{2}\choose n}  =O\left({n ^{2}\choose n}\right)

:)

Pierwszy sposób, który przychodzi mi na myśl, być może nie najprostszy. Oszacujemy podaną funkcją za pomocą elementarnych. Rozpiszmy uprzednio, czym jest

{n ^{2}\choose n}=\frac{(n^2)!}{n!(n^2-n)!}=\frac{(n^2-n)!(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2}{n!(n^2-n)!}=\frac{(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2}{n!}=.

Szukamy takiej funkcji f(n), dla której

\lim_{n\to\infty}\frac{{n ^{2}\choose n}}{f(n)}=1

(to będzie oznaczać, że przybliżenie jest najlepsze w sensie asymptotycznym. I faktycznie, z pomocą przyjdzie nam oszacowanie Stirlinga:

n!\approx \bigg(\frac{n}{e}\bigg)^n\sqrt{2\pi n},

za pomocą którego otrzymamy:

\frac{1}{n!}\approx \bigg(\frac{e}{n}\bigg)^n\frac{1}{\sqrt{2\pi n}}.

Stąd:

{n ^{2}\choose n} \approx \frac{(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2}{\sqrt{2\pi n}}\left(\frac{e}{n}\right)^n.

Prawie gotowe, pozostaje zająć się wyrażeniem (n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2.

Wystarczy sprawdzić, że:

(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2\approx n^{2n}e^{-1/2}=\frac{n^{2n}}{\sqrt{e}},

co wówczas da nam:

\boxed{{n ^{2}\choose n} \approx \frac{n^{2n}}{\sqrt{2\pi e n}}\left(\frac{e}{n}\right)^n=\frac{(e n)^n}{\sqrt{2\pi e n}}}

a w rezultacie, pomijając stałe (które nie wpływają na notację dużego O:

{n ^{2}\choose n}  =O\left(e^n n^{n-\frac{1}{2}\right).

Pozostaje zatem sprawdzić, że:

\lim_{n\to\infty}\frac{(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2}{n^{2n}}=e^{-1/2}

Poradzisz sobie dalej?
Góra
Mężczyzna Offline
PostNapisane: 12 maja 2018, o 11:09 
Użytkownik

Posty: 8
Lokalizacja: Warszawa
Mógłbyś rozwiązać do końca? Jestem mega słaby w tym :(

I mam pytanie { n^{2}  \choose n} to nie jest \frac{n^{2}!}{n( n^2-n)!}?
Góra
Mężczyzna Online
PostNapisane: 12 maja 2018, o 12:29 
Użytkownik

Posty: 12059
Nie, { n^{2} \choose n}=\frac{(n^2)!}{n!(n^2-n)!}.

Mamy
\frac{(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2}{n^{2n}}= \frac{ \prod_{k=1}^{n-1}(n^2-k) }{n^{2n-2}}=\\= \prod_{k=1}^{n-1}\left( 1- \frac{k}{n^2} \right)

Jeśli więc
a_n=\frac{(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2}{n^{2n}},
to
\ln a_n= \sum_{k=1}^{n-1}\ln\left( 1-\frac{k}{n^2}\right)
i teraz korzystając z:
\ln(1+t)=t+o(t) (co wynika ze wzoru Maclaurina) mamy
\ln\left( 1- \frac{k}{n^2} \right) =-\frac{k}{n^2}+o\left( -\frac k{n^2}\right),
w szczególności
\ln\left( 1- \frac{k}{n^2} \right) =-\frac{k}{n^2}+o\left(-\frac 1 n\right)
gdy k=1\ldots n-1, czyli
\lim_{n \to  \infty }  \sum_{k=1}^{n-1}\ln\left( 1-\frac{k}{n^2}\right)  = \lim_{n \to  \infty } \frac{1}{n^2}\sum_{k=1}^{n-1} k=-\frac 1 2
Ostatecznie więc
\lim_{n \to  \infty }\ln a_n=-\frac 1 2 i \lim_{n \to  \infty }a_n=e^{-\frac 1 2}

-- 12 maja 2018, o 11:57 --

Można również postąpić tak:
\ln(1-t)=- \sum_{m=1}^{ \infty } \frac{t^m}{m},
dla |t|<1,
więc
\ln\left( 1-\frac{k}{n^2}\right) =- \sum_{m=1}^{ \infty }  \frac{k^m}{n^{2m}}
dla k=1\ldots n-1 (oczywiście n>1).
oraz
\sum_{k=1}^{n-1}\ln\left( 1-\frac{k}{n^2}\right) =- \sum_{k=1}^{n-1} \sum_{m=1}^{ \infty } \frac{k^m}{n^{2m}}
Teraz rozbijmy tę sumę:
\sum_{m=1}^{ \infty } \frac{k^m}{n^{2m}}=\frac{k}{n^2}+ \sum_{m\ge 2}^{}  \frac{k^m}{n^{2m}}
toteż
\sum_{k=1}^{n-1}\ln\left( 1-\frac{k}{n^2}\right) =- \sum_{k=1}^{n-1}\frac{k}{n^2}- \sum_{k=1}^{n-1} \sum_{m=2}^{+\infty} \frac{k^m}{n^{2m}}
Mamy \frac{k^m}{n^{2m}}\le \frac{1}{n^m} dla k=1\ldots n-1, więc
0<\sum_{k=1}^{n-1} \sum_{m=2}^{+\infty} \frac{k^m}{n^{2m}} \le \sum_{k=1}^{n-1} \sum_{m=2}^{+\infty}  \frac{1}{n^{m}}= \\=\frac{n-1}{n^2\left(1-\frac 1 {n^2}\right)}\stackrel{n\rightarrow \infty}\longrightarrow 0,
toteż z tw. o 3 ciągach otrzymujemy
\lim_{n \to  \infty } \sum_{k=1}^{n-1} \sum_{m=2}^{+\infty} \frac{k^m}{n^{2m}}=0
oraz
\lim_{n \to  \infty } \sum_{k=1}^{n-1}\ln\left( 1-\frac{k}{n^2}\right) =-\frac 1 2
gdyż
\lim_{n \to  \infty }- \sum_{k=1}^{n-1}\frac{k}{n^2}=-\frac 1 2
(zwykła suma ciągu arytmetycznego).

Ale pewnie JakimPL miał na myśli coś sprytniejszego.
Góra
Mężczyzna Online
PostNapisane: 12 maja 2018, o 20:06 
Użytkownik
Avatar użytkownika

Posty: 2375
Lokalizacja: Katowice
Ponieważ

\frac{\left(n^2-\tfrac{n-1}{2}\right)^n}{n^{2n}}=\left(1-\frac{\tfrac{n-1}{2}}{n^2}\right)^n\approx\left(1-\frac{\tfrac{1}{2}}{n}\right)^n\to e^{-1/2},

to wystarczy sprawdzić, że

\prod_{k=1}^{n-1}\left( 1- \frac{k}{n^2} \right)\approx \frac{(n^2-\tfrac{n-1}{2})^n}{n^{2n}}

Czyli, że

\frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}\to 1

Zauważmy, z nierówności a \cdot b\leqslant \left(\frac{a+b}{2}\right)^2 dostajemy

(n^2-n+k)(n^2-k+1)\leqslant \left(n^2-\frac{n-1}{2}\right)^2

dla każdego k\in\{1,\ldots,n\}. Stąd

\frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}\leqslant\frac{\left(n^2-\tfrac{n-1}{2}\right)^n}{\left(n^2-\tfrac{n-1}{2}\right)^n}=1\to 1.

Na podstawie tej samej nierówności (!) wnioskujemy też:

\frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}\geqslant\frac{(n^2-n+1)\cdot\ldots\cdot n^2}{(n^2-n+1)\cdot\ldots\cdot n^2}=1\to 1.

Na podstawie twierdzenia o trzech ciągów mamy to, co chcemy.
Góra
Mężczyzna Online
PostNapisane: 12 maja 2018, o 23:50 
Użytkownik

Posty: 12059
Coś mi tutaj nie pasuje. Może jakiś błąd w przepisywaniu?

Przecież skoro
\frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}\leqslant 1
oraz
\frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}\geqslant 1,
to otrzymalibyśmy
\frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}=1,
co jest oczywistą bzdurą.

-- 13 maja 2018, o 03:15 --

Mam jeszcze nieco inny pomysł, o tej porze nie jestem niestety pewien, czy działa:
niech
1+t=e^{t+g(t)}
dla t>-1.
Wówczas g(t)=\ln\left( \frac{1+t}{e^t}\right),
i mamy
0= \lim_{t \to 0}\left( \frac{\ln(1+t)}{t}-1\right) = \lim_{t \to 0}  \frac{g(t)}{t},
co wynika ze znanej granicy specjalnej
\lim_{t \to 0} \frac{\ln(1+t)}{t}=1.
Zatem otrzymujemy
1-\frac{k}{n^2}=\exp\left(-\frac{k}{n^2}+g\left( -\frac{k}{n^2}\right)  \right)
dla k=1,2\ldots n-1 i po pomnożeniu stronami:
\prod_{k=1}^{n-1}\left( 1-\frac{k}{n^2}\right)=\exp\left( - \sum_{k=1}^{n-1}\frac{k}{n^2} + \sum_{k=1}^{n-1}g\left( -\frac{k}{n^2}\right)  \right)
i pozostaje zauważyć, że
- \sum_{k=1}^{n}  \frac{k}{n^2} = -\frac{n-1}{2n} \stackrel{n\rightarrow\infty}\longrightarrow -\frac 1 2
oraz że
0\ge g\left( -\frac{k}{n^2}\right)\ge g\left( -\frac {n-1} {n^2}\right)
dla k=1,2 \ldots n-1 (gdyż dla t\in (-1,0) funkcja g(t)=\ln(1+t)-t jest rosnąca i g(0)=0)
więc
0\ge  \sum_{k=1}^{n-1}g\left( -\frac{k}{n^2}\right)  \ge (n-1)g\left( -\frac{n-1}{n^2}\right)\stackrel{n\to \infty}\longrightarrow 0
i z ciągłości funkcji eksponencjalnej
\lim_{n \to  \infty }\prod_{k=1}^{n-1}\left( 1-\frac{k}{n^2}\right)=e^{-\frac 1 2}

Myślę, że aż tak elementarnie jak próbowałeś nie da się tego udowodnić (choć wolałbym się mylić w tej kwestii). W powyższym rozwiązaniu ominąłem szereg Taylora, trzeba tylko znać granicę z logarytmem naturalnym i policzyć pochodną tej funkcji \ln(1+t)-t, koszmar to nie jest.
Góra
Mężczyzna Online
PostNapisane: 13 maja 2018, o 11:50 
Użytkownik
Avatar użytkownika

Posty: 2375
Lokalizacja: Katowice
Ale wtopa :oops:, druga nierówność daje to samo ograniczenie w tę samą stronę (a napisałem przeciwnie) :(. Lecimy jeszcze raz, elementarnie, ale mniej elegancko (część żmudnych przeliczeń ominąłem):

\frac{\left(n^2-\tfrac{n}{2}\right)^n}{\left(n^2-\tfrac{n-1}{2}\right)^n}\leqslant\frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}\leqslant\frac{\left(n^2-\tfrac{n-1}{2}\right)^n}{\left(n^2-\tfrac{n-1}{2}\right)^n}=1

Pozostaje sprawdzić, że dla n>1 mamy

(n^2-n+k)(n-k+1)\geqslant \left(n^2-\tfrac{n}{2}\right)^2

Po rozpisaniu powyższego mamy do rozwiązania (przy 1\leqslant k\leqslant n)

f(n,k)=\frac{3n^2}{4}+n(k-1)+k-k^2\geqslant 0

Szukamy miejsc zerowych ze względu na n, można przeliczyć, że dodatnie miejsce zerowe jest dla

n_0^{(k)}= \frac{2}{3}\left(1 - k + \sqrt{4k^2-5k+1}\right)

co jest dobrze określone, ponieważ k\geqslant 1 (krótkie przeliczenie).

Ponieważ nasza funkcja f(n,k) jest funkcją kwadratową o współczynniku przy najwyższej potędze dodatnim, nierówność jest prawdziwa dla wszystkich n\geqslant n_0^{(k)} przy k w przedziale [1,n]. Liczymy na to, że n_0^{(k)}\leqslant n dla każdego k\in[1,n].

Przy odrobinie wysiłku można sprawdzić, że funkcja

n_0(k)=\frac{2}{3}\left(1 - k + \sqrt{4k^2-5k+1}\right)

jest rosnąca dla k\geqslant 1. Wystarczy zatem przekonać się, że n_0(n)\leqslant n, wtedy będziemy mieli pewność, że przy naszych założeniach n>1 oraz k\in[1,n] nierówność f(n,k)\geqslant 0 jest spełniona.

n_0(n)=\frac{2}{3}\left(1 - n + \sqrt{4n^2-5n+1}\right)\leqslant n

prowadzi do

n-\frac{2}{3}\left(1-n\right)\geqslant\frac{2}{3}\sqrt{4n^2-5n+1}

a więc

\frac{5n}{3}-\frac{2}{3}\geqslant \frac{2}{3}\sqrt{4n^2-5n+1}

Wyrażenia po obu stronach są dodatnie, możemy równoważnie podnieść równanie do kwadratu:

\left(\frac{5n}{3}-\frac{2}{3}\right)^2\geqslant \frac{4}{9}\left(4n^2-5n+1\right)

co się ładnie redukuje do...

n^2\geqslant 0

Ble, paskudne rozwiązanie.
Góra
Mężczyzna Online
PostNapisane: 13 maja 2018, o 12:26 
Użytkownik

Posty: 12059
Mała literówka (a może cyfrówka):
Cytuj:
(n^2-n+k)(n-k+1)\geqslant \left(n^2-\tfrac{n}{2}\right)^2

miało pewnie być
(n^2-n+k)(n^2-k+1)\geqslant \left(n^2-\tfrac{n}{2}\right)^2

Cytuj:
f(n,k)=\frac{3n^2}{4}+n(k-1)+k-k^2\geqslant 0

Myślę, że można to trochę przyspieszyć:
\frac{3n^2}{4}+n(k-1)+k-k^2=\frac{3n^2}{4}+(n-k+k)(k-1)+k-k^2=\\=\frac 3 4 n^2+(n-k)(k-1)\ge 0
co wynika bezpośrednio z tego, że n\in \NN^+ i k\in \left\{ 1,2,\ldots n-1\right\}.
Góra
Mężczyzna Online
PostNapisane: 13 maja 2018, o 12:34 
Użytkownik
Avatar użytkownika

Posty: 2375
Lokalizacja: Katowice
Jasne, zgadza się :).

Pod koniec już pałowałem.
Góra
Mężczyzna Online
PostNapisane: 13 maja 2018, o 12:41 
Użytkownik

Posty: 12059
No to fajnie, że jednak da się to policzyć elementarnie, ja bym nigdy nie wpadł na takie szacowania.
Góra
Mężczyzna Offline
PostNapisane: 17 maja 2018, o 20:55 
Użytkownik

Posty: 8
Lokalizacja: Warszawa
Mam pytanie. Dlaczego chcemy aby nasze wyrażenie równało się temu?
(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2\approx n^{2n}e^{-1/2}=\frac{n^{2n}}{\sqrt{e}}
i jeszcze skąd to się wzięło?
\frac{\left(n^2-\tfrac{n-1}{2}\right)^n}{n^{2n}}=\left(1-\frac{\tfrac{n-1}{2}}{n^2}\right)^n\approx\left(1-\frac{\tfrac{1}{2}}{n}\right)^n\to e^{-1/2}
Góra
Mężczyzna Online
PostNapisane: 17 maja 2018, o 21:44 
Użytkownik
Avatar użytkownika

Posty: 2375
Lokalizacja: Katowice
Zacznę od wyjaśnienia drugiej części: znana jest nam granica:

\lim_{n\to\infty}\left(1+\frac{x}{n}\right)^{n}=e^x

Zapis

\frac{\left(n^2-\tfrac{n-1}{2}\right)^n}{n^{2n}}=\left(1-\frac{\tfrac{n-1}{2}}{n^2}\right)^n\approx\left(1-\frac{\tfrac{1}{2}}{n}\right)^n\to e^{-1/2}

oznacza dokładniej:

\lim_{n\to\infty}\frac{\left(n^2-\tfrac{n-1}{2}\right)^n}{n^{2n}}=\lim_{n\to\infty}\left(1-\frac{\tfrac{n-1}{2}}{n^2}\right)^n= \lim_{n\to\infty}\left(1-\frac{\tfrac{1}{2}}{n}\right)^n\to e^{-1/2}

Ostatnie przejście wynika z podanej granicy dla x=-\tfrac{1}{2}. Równość przedostatnich granic nie jest aż tak oczywista, ale można i to elementarnie pokazać.

Co do pierwszego pytania: cóż, intuicyjnie oceniłem tempo wzrostu funkcji, próbując skojarzyć iloczyn z wyrażeniami typu \left(1-\frac{n+\text{coś}}{n^2}\right)^n. Przeliczyłem - zadziałało.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 pytanie odnośnie rekurencji  manduka  1
 Na ile sposobów... i szacowanie liczb  mkopmkop  1
 Zadanie tekstowe z rekurencji  squeaky  1
 Postać zwarta rekurencji liniowej  kocix  3
 Brak warunków początkowych rekurencji liniowej  Flakez  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl