Is there a discrete version of de l'Hôpital's rule?

Question

When considering asymptotics of runtime functions, you often have to find limits of quotients of discrete functions, e.g.

$\displaystyle\qquad \lim\limits_{n \to \infty} \frac{4^n}{\binom{2n}{n}\sqrt{n}}.$

While this particular case can easily be dealt with by Stirling's formula, I have been wondering. Mathematicians often like to use de l'Hôpital's rule, but it can obviously not be applied to the discrete case immediately (no mean value theorem). If—as in this case—you are lucky, you might find nice and well-studied continuations on the reals.

What to do in general, though? Is there a discrete version/relative of de l'Hôpital's rule, maybe using difference quotients?

Answer 1

Stolz–Cesàro seems to be what you're looking for. There are two forms:

1.

Let $a_n$ and $b_n$ be two sequences approaching $0$ as $n\to\infty$, with $b_n$ decreasing. Then,

$$\lim_{n\to\infty}\frac{a_n}{b_n}=\lim_{n\to\infty}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}$$

if the second limit exists.

2.

Let $a_n$ and $b_n$ be two sequences, with $b_n$ unbounded and increasing. Then,

$$\lim_{n\to\infty}\frac{a_n}{b_n}=\lim_{n\to\infty}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}$$

if the second limit exists.