2
$\begingroup$

I'm trying to find the limit: $\displaystyle\lim_{n\to\infty}\frac {1\cdot2\cdot3\cdot...\cdot n}{(n+1)(n+2)...(2n)}$

I thought of taking a pretty obvious binding from above expression: $\frac {n^n} {(n+1)^n}$ which is $n$ times the largest numerator and $n$ times the smallest denominator, but this limit isn't zero and it looks like the given does go to zero.

So maybe 'multiplying' $\frac 1 {n+1}$ by $1$, $n$ times is a good bound but it isn't very obvious that: $\frac {1\cdot2\cdot3\cdot...\cdot n}{(n+1)(n+2)...(2n)}\le \frac 1 {n+1}$ so why is it true?

$\endgroup$
4
$\begingroup$

The numerator has a term 1, so upper bound $n^{n-1}$ is acceptable.

Since you found denominator is at least $(n+1)^n$, you get $$ \frac{1\cdots n}{(n+1)\cdots 2n} \leq \frac{n^{n-1}}{(n+1)^n}\leq \frac1{n+1}.$$

$\endgroup$
  • $\begingroup$ Oh now I got it. Thanks. $\endgroup$ – shinzou Dec 8 '14 at 20:29
3
$\begingroup$

Write your left-hand side as

$${1 \over (n+1)} \times {2 \cdot 3 \cdot \cdots \cdot n \over (n+2)(n+3) \cdot \cdots \cdot 2n}$$

Now the first factor is $1/(n+1)$, and the second factor is obviously less than 1 (since the numerator is smaller than the denominator). So the product is less than $1/(n+1)$.

This throws out a lot of information, but your bound is very weak - as has been observed, your function is approximately $\sqrt{\pi n}/4^n$, which is much smaller than $1/(n+1)$.

Edited to add: we can rewrite the product as $(n!)^2/(2n)!$. Using Stirling's approximation $n! \approx \sqrt{2\pi n} (n/e)^n$ you get

$$(n!)^2/(2n)! \approx { (2\pi n) (n/e)^{2n} \over \sqrt{4 \pi n} (2n/e)^{2n}}$$

and you can simplify that to get the approximation $\sqrt{\pi n}/4^n$.

$\endgroup$
  • $\begingroup$ How do you get to $\sqrt{\pi n}/4^n$? $\endgroup$ – shinzou Dec 8 '14 at 20:58
  • $\begingroup$ See my edits to answer that question. $\endgroup$ – Michael Lugo Dec 8 '14 at 21:08
1
$\begingroup$

Try to express your term with binomial coefficients!

$\endgroup$
  • $\begingroup$ A better approximation for your term is $\frac{\sqrt{\pi n}}{4^n}$ using Stirling's formula. See also here: en.wikipedia.org/wiki/Central_binomial_coefficient $\endgroup$ – Tintarn Dec 8 '14 at 20:26
  • $\begingroup$ Isn't it kinda complicated to get to that expression on your own? $\endgroup$ – shinzou Dec 8 '14 at 20:33
  • $\begingroup$ Of course it is. I just wanted to point out that there is actually a much stronger estimation for your term. $\endgroup$ – Tintarn Dec 9 '14 at 13:35
1
$\begingroup$

Hint: $\binom{2n}{k}$ is unimodal by moving k with maximum at $\binom{2n}{n}$. See also that $n+1\leq 2n=\binom{2n}{1}$.

$\endgroup$
  • $\begingroup$ How is unimodality relevant here? $\endgroup$ – shinzou Dec 8 '14 at 20:31
  • $\begingroup$ because $\binom{2n}{k}\leq \binom{2n}{n}$ for every possible $k$, in particular for $k=1$. $\endgroup$ – Phicar Dec 8 '14 at 20:32

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.