Widzieliśmy już, że wskazanie postaci zwartej dla ciągu zadanego równaniem rekurencyjnym jest często zadaniem niełatwym. Do tej pory nie jest znana zwarta postać wielu równań. Na szczęście często jesteśmy w sytuacji, w której zadowoli nas przybliżenie odpowiedzi. Wróćmy do rozważanej wielokrotnie sumy kolejnych kwadratów \( \displaystyle \sum_{i=0}^ni^2 \). Fakt, że jest to wielomian \( 3 \)-go stopnia zmiennej \( n \), to już wartościowa informacja, często zupełnie wystarczająca. Spotkaliśmy się już nie raz z oszacowaniami poprzez zwykłe nierówności. To podejście często wymaga użycia narzędzi z analizy matematycznej, w szczególności znajdowania ekstremum funkcji.
Przykład
Silnię liczby naturalnej można trywialnie oszacować przez \( n!=1\cdot\ldots\cdot n\leq n^n \). Przyjrzyjmy się delikatniejszemu oszacowaniu wskazującemu także dolne ograniczenie na \( n! \).
Najpierw zauważmy, że
\( \displaystyle (n!)^2=(1\cdot\ldots\cdot n)(n\cdot\ldots\cdot1)=\prod_{i=1}^ni(n+1-i). \)
Potraktujmy \( i(n+1-i)=\frac{1}{4}(n+1)^2-(i-\frac{1}{2}(n+1))^2 \) jako wielomian drugiego stopnia zmiennej \( i \). Łatwo zauważyć, że dla \( i\in[1,\ldots,n] \) przybiera on najmniejszą wartość w punkcie \( i=1 \), a największą w punkcie \( i=\frac{1}{2}(n+1) \). Zatem dla \( i\in{\{ {1,\ldots,n} \}\ } \) mamy \( n\leq i(n+1-i)\leq\frac{1}{4}(n+1)^2 \) i dalej
\( n^n\leq(n!)^2\leq(\frac{1}{4}(n+1)^2)^n, \)
czyli
\( n^{\frac{n}{2}}\leq n!\leq(\frac{n+1}{2})^n. \)
Nierówności w oszacowaniach bywają niepotrzebnie krępujące. Zaś wyniki w ten sposób otrzymane, często skupiają naszą uwagę na zbędnych i czasem nieinteresujących detalach. Często bowiem wystarczają nam przybliżone, asymptotyczne oszacowania ciągów lub ogólniej funkcji. Opisują one zachowanie funkcji wraz ze wzrostem argumentu. Podczas przekształceń rachunkowych celowo ograniczamy naszą wiedzę o funkcji, dzięki czemu łatwiej jest rachować i otrzymać zadowalającą postać przybliżającą.
W oszacowaniach asymptotycznych posługujemy się ogólnie przyjętymi symbolami opisującymi asymptotyczne zachowanie jednej funkcji wobec drugiej. Najpowszechniej używany jest symbol \( O \) przydatny w analizie górnej granicy asymptotycznej. Po raz pierwszy tego symbolu użył niemiecki teorio-liczbowiec Paul Bachmann w 1894. Prace Edmunda Landau'a (także niemieckiego teorio-liczbowca) spopularyzowały tę notację, stąd czasami \( O \) jest nazywany symbolem Landau'a. Notację asymptotyczną wprowadzimy jedynie dla funkcji zdefiniowanych na zbiorze \( \mathbb{N} \) (lub jego podzbiorach postaci \( \mathbb{N}-\mathbb{Z}_k \)) o wartościach w \( \mathbb{R} \).