# alternating sum of binomial coefficients

I would like to know a closed formula for $\sum_{j=0}^{p-n } (-1)^j\binom{n^2}{p-n-j} \binom{n+j-1}j\binom{2n+j}{n+j+1}$, especially in the case $p$ is near $n^2/2$. Similarly, I would like a closed formula for: setting $q=2\cdot\lceil\frac{n(n+1)}{4}\rceil -1$, and setting $p=\lceil\frac{q}{2}\rceil-1$, what is the sum $\sum_{j=0}^{p-n } (-1)^j\binom{q}{p-n-j} \binom{n+j-1}j\binom{2n+j}{n+j+1}$?

In either case I would be happy for an estimate of the growth of the sum (divided by $\binom {n^2-1}p$ in the first case, and divided by $\binom{q-1}p$ in the second).

-
Some of the terms are the (n-1) coefficients; you can get rid of some j's in the expression, and then try Knuth's Concrete Mathematics. Gerhard "Ask Me About System Design" Paseman, 2012.02.15 – Gerhard Paseman Feb 15 '12 at 23:55

I played around with your sum in Maple and got

$$\frac{2n}{n+1}{2n-1 \choose n-1}{n^2 \choose p-n} 3F_{2}([n,n-p,2n+1],[n+2,n^2+n+1-p],1)$$

I make no guarantees that this is correct (especially as the original answer contained a $\binom{n^2}{-1}$ in it).

-
I can't get my 3F2 to display nicely - how do I do that in MathJax? The usual {}_{3}F_{2} does not seem to work. – Jacques Carette Mar 18 '12 at 13:02
I can't prove this, but it works for as large as my computer can handle. A proof, or estimates of the asymptotic behavior (again, as p~ n^2/2) and n goes to infinity) would be most welcome. Thanks! – JM Landsberg Mar 20 '12 at 16:13
I checked on a better computer, this diverges from the sum when n>70 unfortunately. – JM Landsberg Mar 20 '12 at 19:33
How are you doing these evaluations? This is unlikely to be numerically stable, so you would need fairly high accuracy to know, especially for n>70. – Jacques Carette Mar 21 '12 at 2:02

$\sum_{j=0}^{p-n} (-1)^j a_{n,p}(j) = \sum_{j=0}^{\frac{p-n}{2}} a_{n,p}(2j)-a_{n,p}(2j+1)$

so examine this difference $a_{n,p}(2j)-a_{n,p}(2j+1)$, we can factor out $c_{n,p}(j):=\frac{(n^2)!(2n+2j)!(n+2j)!}{(n-1)!(n-1)!(2j+1)!(n+2j+2)!(p-n-2j)!(n^2-p+n+2j)!}$

giving $c_{n,p}(j) \left[ \frac{(n+2j+2)(2j+1)}{(n+2j)} - \frac{(2n+2j+1)(p-n-2j)}{(n^2-p+n+2j+1)}\right]$

$=c_{n,p}(j) \left[ (2j+1)\left(1+\frac{2}{n+2j}- \frac{p-n-2j}{n^2-p+n+2j+1}\right)-\frac{2n(p-n-2j)}{n^2-p+n+2j+1}\right]\approx -2nc_{n,p}(j)$

this is assuming $p\approx \frac{n^2}{2}$ is large. not sure if this helps

-