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

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?

-
–  Ｊ. Ｍ. Dec 20 '11 at 13:41
@J.M. answer? (I'm almost sure that one link answers the question posed.) –  Willie Wong Dec 20 '11 at 13:56
Indeed. This is what I had in mind but did not quite see a proof for. –  Raphael Dec 20 '11 at 14:02

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.

-
Thanks! Too bad it does not seem to help dealing with the example I have, though (but I did not ask for that, of course). –  Raphael Dec 20 '11 at 14:11
@Raphael: Well, that square root you added certainly throws a wrench on things... :) –  Ｊ. Ｍ. Dec 20 '11 at 14:12
The limit is still nice, though. The original problem is to check wether $4^n \cdot \binom{2n}{n}^{-1} \sim \sqrt{n}$, therefore my edit. Don't see a way to use the theorem even without $\sqrt{n}$, though. –  Raphael Dec 20 '11 at 14:14
Right, but any sort of L'Hopital rule won't work anyway, since both of your sequences grow exponentially, so taking the derivative will give you back essentially the same ratio. –  Willie Wong Dec 20 '11 at 14:31

The discrete version of L'Hôspital's rule, in my opinion, is Abelian theorems, including the L'Hôspital's rule, Silverman-Toeplitz theorem and its sepcial case, Stolz-Cesàro theorem.

On de Bruijn's Asymptotic methods in analysis, it's said that

A theorem which derives asymptotic information about some kind of average of a function from asymptotic information about the function itself, is called an Abelian theorem. If one can find a supplementary condition under which the converse of an Abelian theorem holds, then this condition is called a Tauberian condition, and the converse theorem is called a Tauberian theorem.

The amount you gave, as far as I've tried, couldn't be easily solved with these theorems.

Let $$a_n=\frac{4^n}{\binom{2n}n\sqrt n}$$ we have $$\ln a_{n+1}-\ln a_n=\frac12\ln(n+1)-\ln(n+\frac12)+\frac12\ln n=-\frac1{4n^2}+O\left(\frac1{n^3}\right)\tag1$$ Therefore $\ln a_n$ converges as $n\to\infty$. However, the preceding equation, the asymptotic behavior of the difference, is not enough to determine the limit value, even if the result is refined. Such efforts are generally unsuccessful.

However, if $S=\lim_{n\to\infty}\ln a_n$, we could determine the asymptotic behavior of $a_n-S$ through (1) easily, since $\ln a_n=S-\sum_{k\ge n}(\ln a_k-\ln a_{k+1})$.

Remark One could determine $S$ through Stirling's formula. There's another approach, more elementary, I think:

$$a_n^2=\left(\frac{(2n-1)!!}{(2n)!!}\right)^2(2n+1)\cdot\frac n{2n+1}\to\frac1\pi$$

by Wallis product, therefore $S=1/\sqrt\pi$.

-