Twierdzenie to mówi, że funkcja wykładnicza rośnie szybciej niż dowolny wielomian. Innymi słowy: wzrost wykładniczy dominuje nad wzrostem potęgowym.
Dla każdego $k \in \mathbb{N}$ i $a \gt 1$ zachodzi: \[ \lim\limits_{n \to \infty} \frac{n^k}{a^n} = 0. \]
Ponieważ $a \gt 1$, możemy zapisać $a = 1 + h$, gdzie $h \gt 0$.
Z dwumianu Newtona, dla $n \gt k+1$: \[ a^n = (1 + h)^n = \sum_{j=0}^{n} \binom{n}{j} h^j \geq \binom{n}{k+1} h^{k+1}. \]
Wybraliśmy wyraz z $j = k+1$, bo potrzebujemy potęgi $n$ wystarczająco wysokiej w liczniku $\binom{n}{k+1}$.
Mamy: \[ \binom{n}{k+1} = \frac{n(n-1)(n-2)\cdots(n-k)}{(k+1)!}. \]
Zatem: \[ a^n \geq \frac{n(n-1)(n-2)\cdots(n-k)}{(k+1)!} \cdot h^{k+1}. \]
Stąd: \[ 0 \leq \frac{n^k}{a^n} \leq \frac{n^k}{\dfrac{n(n-1)(n-2)\cdots(n-k)}{(k+1)!} \cdot h^{k+1}} = \frac{(k+1)!}{h^{k+1}} \cdot \frac{n^k}{n(n-1)(n-2)\cdots(n-k)}. \]
Oznaczmy stałą $C = \frac{(k+1)!}{h^{k+1}}$. Pozostaje zbadać: \[ \frac{n^k}{n(n-1)(n-2)\cdots(n-k)}. \]
W mianowniku mamy iloczyn $k+1$ czynników: $n, (n-1), \ldots, (n-k)$. Jest to wielomian stopnia $k+1$ względem $n$, natomiast w liczniku mamy $n^k$ — wielomian stopnia $k$. Zatem: \[ \frac{n^k}{n(n-1)\cdots(n-k)} = \frac{n^k}{n^{k+1}\left(1 - \frac{1}{n}\right)\left(1 - \frac{2}{n}\right)\cdots\left(1 - \frac{k}{n}\right)} = \frac{1}{n \cdot \prod_{j=1}^{k}\left(1 - \frac{j}{n}\right)}. \]
Ponieważ $\prod_{j=1}^{k}\left(1 - \frac{j}{n}\right) \to 1$, mamy: \[ \frac{n^k}{n(n-1)\cdots(n-k)} \sim \frac{1}{n} \to 0. \]
Łącząc: \[ 0 \leq \frac{n^k}{a^n} \leq \frac{C}{n \cdot \prod_{j=1}^{k}\left(1 - \frac{j}{n}\right)} \to 0. \]
Z twierdzenia o trzech ciągach: \[ \lim\limits_{n \to \infty} \frac{n^k}{a^n} = 0. \quad \square \]
$\frac{n^0}{a^n} = \frac{1}{a^n} \to 0$, bo $a \gt 1$. $\checkmark$
Pokażemy, że $\frac{n}{a^n} \to 0$. Niech $a = 1 + h$, $h \gt 0$. Z nierówności Bernoulliego (a dokładniej z dwumianu Newtona): \[ a^n = (1+h)^n \geq \binom{n}{2} h^2 = \frac{n(n-1)}{2} h^2 \quad \text{dla } n \geq 2. \]
Zatem: \[ 0 \leq \frac{n}{a^n} \leq \frac{n}{\frac{n(n-1)}{2} h^2} = \frac{2}{h^2(n-1)} \to 0. \quad \checkmark \]
Załóżmy, że $\frac{n^k}{a^n} \to 0$ dla pewnego $k \geq 1$. Pokażemy, że $\frac{n^{k+1}}{a^n} \to 0$.
Niech $b = \sqrt{a}$. Wtedy $b \gt 1$ i $a = b^2$, więc: \[ \frac{n^{k+1}}{a^n} = \frac{n^{k+1}}{b^{2n}} = \frac{n^k}{b^n} \cdot \frac{n}{b^n}. \]
Z założenia indukcyjnego (dla podstawy $b \gt 1$): \[ \frac{n^k}{b^n} \to 0 \quad \text{oraz} \quad \frac{n}{b^n} \to 0. \]
Ciąg $\frac{n}{b^n}$ jest ograniczony (bo jest zbieżny do $0$), powiedzmy $\frac{n}{b^n} \leq M$ dla pewnego $M$.
Zatem: \[ 0 \leq \frac{n^{k+1}}{a^n} = \frac{n^k}{b^n} \cdot \frac{n}{b^n} \leq M \cdot \frac{n^k}{b^n} \to 0. \]
Z twierdzenia o trzech ciągach: $\frac{n^{k+1}}{a^n} \to 0$. $\square$
Dlaczego $a^n$ rośnie szybciej niż $n^k$?
Funkcja $n^k$ jest wielomianem stopnia $k$ — rośnie „potęgowo". Funkcja $a^n$ (dla $a \gt 1$) rośnie „wykładniczo" — w każdym kroku mnoży się przez stałą $a \gt 1$.
Kluczowe spostrzeżenie: $(1+h)^n$ zawiera w rozwinięciu dwumianowym wyrazy rzędu $n^{k+1}$, które dominują nad $n^k$ w liczniku.
$\frac{n^2}{2^n} \to 0$.
Kilka wartości: $\frac{10^2}{2^{10}} = \frac{100}{1024} \approx 0{,}098$, $\frac{20^2}{2^{20}} = \frac{400}{1048576} \approx 0{,}00038$.
$\frac{n^{10}}{1{,}01^n} \to 0$. Zbieżność jest bardzo wolna, ale nieunikniona.
$\frac{n^{100}}{2^n} \to 0$. Dla małych $n$ ułamek rośnie, ale od pewnego momentu $2^n$ dominuje i ułamek maleje do zera.
Dla $a \gt 1$ i dowolnego wielomianu $W(n) = c_k n^k + c_{k-1} n^{k-1} + \ldots + c_0$: \[ \lim\limits_{n \to \infty} \frac{W(n)}{a^n} = 0. \]
Dowód: $\frac{|W(n)|}{a^n} \leq \frac{(|c_k| + |c_{k-1}| + \ldots + |c_0|) \cdot n^k}{a^n} \to 0$.