O'Stolz 定理及其应用

1. 基本形式

对于 ⋆∞$/frac{/star}{/infty}$（分母为无穷大，分子无要求），设两数列 an,bn${a_n}, {b_n}$，满足：

如果有 limn→∞an+1−anbn+1−bn=L$/lim/limits_{n/to /infty}/frac{a_{n+1}-a_n}{b_{n+1}-b_n}=L$（L$L$ 为有限实数），则：

limn→∞anbn=limn→∞an+1−anbn+1−bn=L $$/lim/limits_{n/to /infty}/frac{a_n}{b_n}=/lim/limits_{n/to /infty}/frac{a_{n+1}-a_n}{b_{n+1}-b_n}=L$$

2. 等价形式

3. 简单应用

算法的时间复杂度相关的分析证明中，常见的一个结论是：

limn→∞logn!nlogn=1 $$/lim/limits_{n/to /infty}/frac{/log n!}{n/log n}=1$$

证明：

limn→∞logn!nlogn===limn→∞log(n+1)!−logn!(n+1)log(n+1)−nlognlimn→∞log(n+1)nlog(1+1n)+log(n+1)limn→∞log(n+1)1+log(n+1)=1 $$/begin{split}/lim/limits_{n/to /infty}/frac{/log n!}{n/log n}=&/lim/limits_{n/to /infty}/frac{/log (n+1)!-/log n!}{(n+1)/log (n+1)-n/log n}//=&/lim/limits_{n/to /infty}/frac{/log (n+1)}{n/log(1+/frac1n)+/log (n+1)}//=&/lim/limits_{n/to /infty}/frac{/log(n+1)}{1+/log(n+1)}=1/end{split}$$