Szacowanie rekurencji

[piotr159]

Witam,
Mam problem z zadaniem:
Znajdź możliwe najlepsze oszacowanie:

\(\displaystyle{ {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 \(\displaystyle{ O}\).

[JakimPL]

Najlepsze oszacowanie to chyba

\(\displaystyle{ {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

\(\displaystyle{ {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 \(\displaystyle{ f(n)}\), dla której

\(\displaystyle{ \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:

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

za pomocą którego otrzymamy:

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

Stąd:

\(\displaystyle{ {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 \(\displaystyle{ (n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2}\).

Wystarczy sprawdzić, że:

\(\displaystyle{ (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:

\(\displaystyle{ \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 \(\displaystyle{ O}\):

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

Pozostaje zatem sprawdzić, że:

\(\displaystyle{ \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?

[piotr159]

Mógłbyś rozwiązać do końca? Jestem mega słaby w tym

I mam pytanie \(\displaystyle{ { n^{2} \choose n}}\) to nie jest \(\displaystyle{ \frac{n^{2}!}{n( n^2-n)!}}\)?

[Premislav]

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

Mamy
\(\displaystyle{ \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
\(\displaystyle{ a_n=\frac{(n^2-n+1)\cdot\ldots\cdot (n^2-1)n^2}{n^{2n}}}\),
to
\(\displaystyle{ \ln a_n= \sum_{k=1}^{n-1}\ln\left( 1-\frac{k}{n^2}\right)}\)
i teraz korzystając z:
\(\displaystyle{ \ln(1+t)=t+o(t)}\) (co wynika ze wzoru Maclaurina) mamy
\(\displaystyle{ \ln\left( 1- \frac{k}{n^2} \right) =-\frac{k}{n^2}+o\left( -\frac k{n^2}\right)}\),
w szczególności
\(\displaystyle{ \ln\left( 1- \frac{k}{n^2} \right) =-\frac{k}{n^2}+o\left(-\frac 1 n\right)}\)
gdy \(\displaystyle{ k=1\ldots n-1}\), czyli
\(\displaystyle{ \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
\(\displaystyle{ \lim_{n \to \infty }\ln a_n=-\frac 1 2}\) i \(\displaystyle{ \lim_{n \to \infty }a_n=e^{-\frac 1 2}}\)

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

Można również postąpić tak:
\(\displaystyle{ \ln(1-t)=- \sum_{m=1}^{ \infty } \frac{t^m}{m}}\),
dla \(\displaystyle{ |t|<1}\),
więc
\(\displaystyle{ \ln\left( 1-\frac{k}{n^2}\right) =- \sum_{m=1}^{ \infty } \frac{k^m}{n^{2m}}}\)
dla \(\displaystyle{ k=1\ldots n-1}\) (oczywiście \(\displaystyle{ n>1}\)).
oraz
\(\displaystyle{ \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ę:
\(\displaystyle{ \sum_{m=1}^{ \infty } \frac{k^m}{n^{2m}}=\frac{k}{n^2}+ \sum_{m\ge 2}^{} \frac{k^m}{n^{2m}}}\)
toteż
\(\displaystyle{ \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 \(\displaystyle{ \frac{k^m}{n^{2m}}\le \frac{1}{n^m}}\) dla \(\displaystyle{ k=1\ldots n-1}\), więc
\(\displaystyle{ 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
\(\displaystyle{ \lim_{n \to \infty } \sum_{k=1}^{n-1} \sum_{m=2}^{+\infty} \frac{k^m}{n^{2m}}=0}\)
oraz
\(\displaystyle{ \lim_{n \to \infty } \sum_{k=1}^{n-1}\ln\left( 1-\frac{k}{n^2}\right) =-\frac 1 2}\)
gdyż
\(\displaystyle{ \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.

[JakimPL]

Ponieważ

\(\displaystyle{ \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

\(\displaystyle{ \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

\(\displaystyle{ \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 \(\displaystyle{ a \cdot b\leqslant \left(\frac{a+b}{2}\right)^2}\) dostajemy

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

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

\(\displaystyle{ \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ż:

\(\displaystyle{ \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.

[Premislav]

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

Przecież skoro
\(\displaystyle{ \frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}\leqslant 1}\)
oraz
\(\displaystyle{ \frac{(n^2-n+1)\cdot\ldots\cdot n^2}{\left(n^2-\tfrac{n-1}{2}\right)^n}\geqslant 1}\),
to otrzymalibyśmy
\(\displaystyle{ \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
\(\displaystyle{ 1+t=e^{t+g(t)}}\)
dla \(\displaystyle{ t>-1}\).
Wówczas \(\displaystyle{ g(t)=\ln\left( \frac{1+t}{e^t}\right)}\),
i mamy
\(\displaystyle{ 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
\(\displaystyle{ \lim_{t \to 0} \frac{\ln(1+t)}{t}=1}\).
Zatem otrzymujemy
\(\displaystyle{ 1-\frac{k}{n^2}=\exp\left(-\frac{k}{n^2}+g\left( -\frac{k}{n^2}\right) \right)}\)
dla \(\displaystyle{ k=1,2\ldots n-1}\) i po pomnożeniu stronami:
\(\displaystyle{ \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
\(\displaystyle{ - \sum_{k=1}^{n} \frac{k}{n^2} = -\frac{n-1}{2n} \stackrel{n\rightarrow\infty}\longrightarrow -\frac 1 2}\)
oraz że
\(\displaystyle{ 0\ge g\left( -\frac{k}{n^2}\right)\ge g\left( -\frac {n-1} {n^2}\right)}\)
dla \(\displaystyle{ k=1,2 \ldots n-1}\) (gdyż dla \(\displaystyle{ t\in (-1,0)}\) funkcja \(\displaystyle{ g(t)=\ln(1+t)-t}\) jest rosnąca i \(\displaystyle{ g(0)=0}\))
więc
\(\displaystyle{ 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
\(\displaystyle{ \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 \(\displaystyle{ \ln(1+t)-t}\), koszmar to nie jest.

[JakimPL]

Ale wtopa , 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):

\(\displaystyle{ \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 \(\displaystyle{ n>1}\) mamy

\(\displaystyle{ (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 \(\displaystyle{ 1\leqslant k\leqslant n}\))

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

Szukamy miejsc zerowych ze względu na \(\displaystyle{ n}\), można przeliczyć, że dodatnie miejsce zerowe jest dla

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

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

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

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

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

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

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

prowadzi do

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

a więc

\(\displaystyle{ \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:

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

co się ładnie redukuje do...

\(\displaystyle{ n^2\geqslant 0}\)

Ble, paskudne rozwiązanie.

[Premislav]

Mała literówka (a może cyfrówka):

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

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

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

Myślę, że można to trochę przyspieszyć:
\(\displaystyle{ \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 \(\displaystyle{ n\in \NN^+}\) i \(\displaystyle{ k\in \left\{ 1,2,\ldots n-1\right\}}\).

[JakimPL]

Jasne, zgadza się .

Pod koniec już pałowałem.

[Premislav]

No to fajnie, że jednak da się to policzyć elementarnie, ja bym nigdy nie wpadł na takie szacowania.

[piotr159]

Mam pytanie. Dlaczego chcemy aby nasze wyrażenie równało się temu?
\(\displaystyle{ (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?
\(\displaystyle{ \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}}\)

[JakimPL]

Zacznę od wyjaśnienia drugiej części: znana jest nam granica:

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

Zapis

\(\displaystyle{ \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:

\(\displaystyle{ \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 \(\displaystyle{ 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 \(\displaystyle{ \left(1-\frac{n+\text{coś}}{n^2}\right)^n}\). Przeliczyłem - zadziałało.