0
$\begingroup$

Is there any way to get a formula for the the limit of the following summation?($n$ is a positive number no smaller than 2) $$\lim_{n \to \infty}\frac{\sum_{u=2}^n \binom{u}{2} \binom{n+2 - u}{2}}{n^2} $$

In particular if I can show the numerator is of order $n$ instead of order $n^2$ then I can conclude the limit is $0$, I tried to use Stirling's formula but it's a little tricky because when $n \to \infty$ the upper limit of summation grows too.

I conjecture the order of numerator is of order $n$, so I guess that's the question. If it is or order $n^2$ then we really need a full formula to get the limit.

$\endgroup$
1
$\begingroup$

Expand the choices. We have $$\sum_{u=2}^n \binom{u}{2} \binom{n+2 - u}{2}=\sum_{u=2}^n\frac 12u(u-1)\frac 12(n+2-u)(n+1-u)\\=\frac 14\sum_{u=2}^n(u^2-u)(n^2+3n+2+u^2-3u-2nu)\\=\frac 14\sum_{u=2}^nu^2n^2+3nu^2-u^2+u^4-4u^3-2nu^3-un^2-3nu-2u+2nu^2$$ You can sum all the terms individually using Faulhaber's formula. The leading term comes from the $u^2n^2$ and $n^4$ terms because they are the only ones that result in $n^5$. For that we have $$ \sum_{u=2}^nu^2n^2+u^4=O(\frac {n^5}3+\frac {n^5}5)=O(n^5)$$ so the limit is $+\infty$ and it diverges in proportion to $n^3$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You're right, I got a wrong formula to work on. $\endgroup$ – Kenneth Chen Sep 16 '16 at 3:27
1
$\begingroup$

There is no limit. The series does not converge.

$$\sum_{u=2}^{x-2} \binom{u}{2} \binom{x-u}{2} = \binom {x+1}{4+1} $$

(If we begin with $x+1$ people in a line. Then for each person from third to third last (position $u+1$ for $u$ from $2$ to $x-2$), we count count the ways to select 2 people before and two people after that position $u+1$. Then we have thus counted ways to select $5$ people from $x+1$.)

So using $x=n+2$ we have

$$\sum_{u=2}^{n} \binom{u}{2} \binom{n+2-u}{2} = \binom {n+3}{4+1} $$

Which is of order $n^5$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, I got it wrong. The formula is useful. $\endgroup$ – Kenneth Chen Sep 16 '16 at 3:28

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.