# 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?

-

7
– J. M. 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

## 2 Answers

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... :) – J. M. 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

5
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$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9519051313400269, "perplexity_flag": "middle"}