A limit from an Erdos paper - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:58:06Z http://mathoverflow.net/feeds/question/82491 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82491/a-limit-from-an-erdos-paper A limit from an Erdos paper Bob 2011-12-02T17:37:19Z 2011-12-03T00:33:33Z <p>Hi,</p> <p>I need help to prove that, for $N = \big\lfloor \frac{1}{2}n\log(n)+cn \big\rfloor$ with $c \in \mathbb R$ and $0 \leq k \leq n:$ </p> <p>$$\lim_{n\rightarrow +\infty} \dbinom{n}{k} \frac{\dbinom{\binom{n - k}{2}}{N} }{\dbinom{\binom{n}{2} }{N}} = \frac{e^{-2kc}}{k!}$$</p> http://mathoverflow.net/questions/82491/a-limit-from-an-erdos-paper/82498#82498 Answer by Jacques Carette for A limit from an Erdos paper Jacques Carette 2011-12-02T18:25:29Z 2011-12-02T18:25:29Z <p>First note that $\binom{m}{2} = \frac{m(m-1)}{2}$ and use that to get rid of the nested binomials. Also, the floor function will not (here) make any difference, so ignore it.</p> <p>Then convert all binomials to their $\Gamma$ equivalents, and use Stirling's formulas for each term. The next step is the messiest, as you'll have a lot of arithmetic to perform on the result, which will give you the result.</p> <p>This is sufficiently mechanical that, using Maple, I can quickly derive that $$\frac{e^{-2kc}}{k!} + \frac{-\frac{1}{2}e^{-2kc}((4c+k+1)\ln{n}+2kc+4c^2+\ln^2{n}-1+2c+k)}{n (k-1)!}+O(n^{-2})$$</p> <p>Of course, that second term might not be quite right, since the previously ignored floor function might here contribute, I have not checked that.</p> http://mathoverflow.net/questions/82491/a-limit-from-an-erdos-paper/82504#82504 Answer by Bob for A limit from an Erdos paper Bob 2011-12-02T20:18:38Z 2011-12-02T20:18:38Z <p>Hi,</p> <p>thank you for your calculation, in fact I wanted to generalize the method to obtain the following limit:</p> <p>for $N' = \lfloor n^2 log(n)+cn^2 \rfloor$ with $c \in \mathbb R$ and $0 \leq k \leq n$</p> <p>$$\lim_{n\rightarrow +\infty} \dbinom{n}{k} \frac{\dbinom{3 \binom{n-k}{3} }{N'} }{\dbinom{3 \binom{n}{3} }{N'}}$$</p> <p>but I think it's a little hard without Maple, so if you could give me the value of this limit with your method it would help me a lot.</p> <p>Friendly.</p> http://mathoverflow.net/questions/82491/a-limit-from-an-erdos-paper/82518#82518 Answer by Brendan McKay for A limit from an Erdos paper Brendan McKay 2011-12-02T22:49:04Z 2011-12-02T22:58:44Z <p>Note that the limit is not in general correct if $k$ is a function of $n$. I'll assume you meant us to assume it is constant or very slowly growing.</p> <p>You don't need a computer. Just remember this one: $$\binom{M}{t} = \frac{M^t}{t!} \exp\biggl( -\frac{t(t-1)}{2M} + O(t^3/M^2)\biggr),$$ as $M\to\infty$. The variable $t$ can be a function of $M$ provided $t^3/M^2$ is bounded. You can prove this using Stirling's formula, but it is easier to just take the logarithm of both sides and use the Taylor expansion of the logarithm.</p> <p>Apply this to the three binomials in your problem and simplify. This will also tell you how fast $k$ can increase before the limit changes.</p> <p>For your second problem $t^3/M^2$ doesn't go to zero, so you need the next term inside the exponential, which is $$-\frac{t(t-1)(2t-1)}{12M^2}$$ and the error term is then $O(t^4/M^3)$. If you don't care about precise error terms, put this together and infer that whenever $t=o(M^{3/4})$, $$\binom{M}{t} = \frac{M^t}{t!} \exp\biggl( -\frac{t^2}{2M} -\frac{t^3}{6M^2} + o(1)\biggr).$$</p>