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?

  • 10
    $\begingroup$ Stolz–Cesàro? $\endgroup$ – J. M. isn't a mathematician Dec 20 '11 at 13:41
  • $\begingroup$ @J.M. answer? (I'm almost sure that one link answers the question posed.) $\endgroup$ – Willie Wong Dec 20 '11 at 13:56
  • $\begingroup$ Indeed. This is what I had in mind but did not quite see a proof for. $\endgroup$ – Raphael Dec 20 '11 at 14:02

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


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


if the second limit exists.


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


if the second limit exists.

  • $\begingroup$ 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). $\endgroup$ – Raphael Dec 20 '11 at 14:11
  • $\begingroup$ @Raphael: Well, that square root you added certainly throws a wrench on things... :) $\endgroup$ – J. M. isn't a mathematician Dec 20 '11 at 14:12
  • $\begingroup$ 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. $\endgroup$ – Raphael Dec 20 '11 at 14:14
  • 7
    $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.