W pewnych sytuacjach łatwiejsze do uzyskania, ale słabsze oszacowanie zastosowane w odpowiedni sposób może prowadzić do lepszego końcowego szacowania zachowania asymptotycznego. Poznamy tę metodę w kilku kolejnych przykładach.
Przykład
Dla ciągu zadanego przez
\( \displaystyle \begin{align*} a_0 & =1, \\ a_{n+1} & =\frac{1}{n^3}\sum_{i=0}^{n-1}a_i, \end{align*} \)
najpierw dowodzimy indukcyjnie, że \( \displaystyle 0 < a_n\leq 1 \), czyli \( \displaystyle a_n=O(1) \). Podstawiając uzyskane oszacowanie do równania rekurencyjnego otrzymujemy:
\( \displaystyle a_n=\frac{1}{n^3}\sum_{i=0}^{n}a_i=\frac{1}{n^3}\cdot \sum_{i=0}^n O(1)=\frac{1}{n^3}\cdot O( \sum_{i=0}^n1 )=\frac{1}{n^3}\cdot O(n)=O( \frac{1}{n^2} ). \)
Operację tę możemy powtórzyć uzyskując jeszcze lepsze oszacowanie
\( \displaystyle \begin{align*} a_n & =\frac{1}{n^3}\sum_{i=0}^na_i=\frac{1}{n^3}( a_0+\sum_{i=1}^na_i )=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^{n}O( \frac{1}{n^2} )= \frac{1}{n^3}+\frac{1}{n^3}O(1) \\ & =O( \frac{1}{n^3} ). \end{align*} \)
Wykorzystaliśmy tu fakt, iż szereg \( \displaystyle \sum_{i=0}^{\infty}\frac{1}{i^2} \) jest zbieżny. Zauważmy też, że następne powtórzenie podobnej procedury szacującej już nam nic nie da.
\( \displaystyle a_n=\frac{1}{n^3}\sum_{i=0}^na_i=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^nO( \frac{1}{n^3} )=\frac{1}{n^3}+\frac{1}{n^3}\cdot O( \frac{1}{n^2} )=O( \frac{1}{n^3} ). \)
Przykład
Niech ciąg \( \displaystyle b_n \) spełnia
\( \displaystyle b_n\cdot\ln{b_n}=n. \)
Z monotoniczności funkcji \( \displaystyle n\ln{n} \) dostajemy, że \( \displaystyle 0 < b_n < n \). Podstawiając to oszacowanie za drugie wystąpienie \( \displaystyle b_n \) w równaniu otrzymujemy:
\( \displaystyle n=b_n\cdot\ln{b_n} < b_n\ln{n}, \)
czyli \( \displaystyle b_n>\frac{n}{\ln{n}} \). Podstawiając powtórnie dostajemy:
\( \displaystyle n=b_n\ln{b_n}>b_n\cdot\ln{\frac{n}{\ln{n}}}, \)
czyli \( \displaystyle b_n < \frac{n}{\ln{n}-\ln{\ln{n}}} \). Uzyskaliśmy zatem, że \( \displaystyle b_n=\Theta( \frac{n}{\ln{n}} ) \).
Na zakończenie tego wykładu poznamy jeszcze jeden symbol asymptotyczny. Jest on podobny do \( \displaystyle \Theta \) lecz znacznie precyzyjniejszy.
Funkcje asymptotycznie równe to takie funkcje \( \displaystyle f(n) \) i \( \displaystyle g(n) \), że
\( \displaystyle \lim_{narrow\infty}\frac{f(n)}{g(n)}=1. \)
Fakt, że funkcje \( \displaystyle f(n) \) i \( \displaystyle g(n) \) są asymptotycznie równe zapisujemy jako \( \displaystyle f(n)\sim g(n) \).
Jednym z najbardziej znanych przybliżeń asymptotycznych jest tzw. Wzór Stirlinga przybliżający zachowanie silni.
Twierdzenie 9.5 [wzór Stirlinga]
\( \displaystyle n!\sim \sqrt{2\pi n}( \frac{n}{e} )^n. \)
Wzór ten został odkryty przez Abrahama de Moivre w postaci
\( \displaystyle n!\sim c \cdot n^{n+1/2} e^{-n}, \)
dla pewnej stałej \( \displaystyle c \). Wkładem Jamesa Stirlinga było pokazanie, że stałą tą jest \( \displaystyle c=\sqrt{2\pi} \). Dowód tego oszacowania wykracza poza metody tego kursu. W oszacowaniach przez nierówności przydatna jest następująca wersja wzoru Stirlinga:
\( \displaystyle \sqrt{2\pi n}( \frac{n}{e} )^ne^{-(12n+1)}\leq n!\leq \sqrt{2\pi n}( \frac{n}{e} )^{n}e^{-12n} \)
Innym ważnym przybliżeniem asymptotycznym jest wzór na liczbę podziałów liczby naturalnej \( \displaystyle n \) na sumy dodatnich liczb naturalnych, tzn. asymptotyczne przybliżenie funkcji \( \displaystyle p_n = \sum_{k=1}^n P(n,k) \) .
Twierdzenie 9.6
\( \displaystyle p_n \sim \frac{e^{\pi\sqrt{\frac{2n}{3}}}}{4n\sqrt{3}} \)
Podamy też asymptotyczne przybliżenie na liczbę liczb pierwszych nie większych niż \( \displaystyle n \).
Twierdzenie 9.7
Jeśli \( \displaystyle \pi(n) \) oznacza liczbę liczb pierwszych w zbiorze \( \displaystyle \lbrace 1,2,3,\ldots,n \rbrace \), to
\( \displaystyle \pi(n) \sim \frac{n}{\ln n} \)