Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
Stolz–Cesàro? –  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
add comment

2 Answers 2

up vote 20 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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