# Summation of Series of product of Combinations

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.

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$

• You're right, I got a wrong formula to work on. – Kenneth Chen Sep 16 '16 at 3:27

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$

• Thank you, I got it wrong. The formula is useful. – Kenneth Chen Sep 16 '16 at 3:28