# Binomial coefficient in Andrews' partition book

First of all, i think MathOverflow is a very great community to discuss math, either basic or advanced, and i'm glad to participate here. It's my first post, so i'm sorry if i did anything wrong, and hope that people help me to make this post better. I also hope this post helps somebody with similar problem...

I've studied partition theory for my undergraduate math monography, and the Simon Newcomb's problem is a topic of the essay. The masterpiece of George Andrews, "The Theory of Partitions" is my main guide; I reached a "binomial identity" that i cannot proof. In fact, Andrews proves it, but i cannot understand the proof clearly, and more important, his demonstration uses Gaussian Polynomials, a topic that my work doesn't cover.

That's the identity: $$\sum_{\substack{i+j=s \atop i\geq 0, j \geq 0}}\binom{A-n+j}{j}\binom{n-j}{i} = \binom{A+1}{s},$$ for positive integer $A$.

I'm asking here an "elementary" proof that doesn't use Gaussian Polynomials.

Sorry to bother you all with so basic question (comparing with advanced stuff that is posted here), and thanks in advance.

P.S. Sorry for my "not so good" english...

-
I think this question is better suited for Math Stack Exchange. It follows directly from looking at the generating series. –  Eric Naslund Oct 19 '11 at 19:08
I took the liberty of inserting an " \atop " in the sum's index ;) –  Pietro Majer Oct 19 '11 at 19:16
@ Pietro Majer: Thanks a lot ! :) –  Guilherme Oct 19 '11 at 19:20
@Pietro Majer: \atop is not what you should use for a sum, as it makes both the top and bottom smaller, and hard to read. I personally use arrays or a line break. –  Eric Naslund Oct 19 '11 at 21:51
@Guilherne: You might consider getting a hold of Concrete Mathematics by Graham, Knuth, and Patashnik, which well covers the necessary techniques, including those given by Eric and Mike. –  Todd Trimble Oct 19 '11 at 23:34

Consider the generating series

$$\sum_{s=0}^{\infty}\left(\sum_{i+j=s}\binom{A-n+j}{j}\binom{n-j}{i}\right)x^{s}.$$ This equals $$\sum_{j=0}^{\infty}\binom{A-n+j}{j}x^{j}\sum_{i=0}^{\infty}\binom{n-j}{i}x^{i}=(1+x)^{n}\sum_{j=0}^{\infty}\binom{A-n+j}{j}\left(\frac{x}{1+x}\right)^{j},$$ where we use the binomial theorem for the last equality. As $\sum_{k=0}^{\infty}\binom{n+k}{k}x^{k}=\frac{1}{(1-x)^{k}}$ our series becomes $$(1+x)^{n}\frac{1}{\left(1-\frac{x}{1+x}\right)^{A-n+1}}=(1+x)^{A+1}$$ which is $$\sum_{s=0}^{\infty}\binom{A+1}{s}x^{s}$$ by the binomial theorem. Your equality follows from comparing coefficients.

-
Awesome proof ! Thanks very very much for this! i'll wait some time, if anyone wants to proof using an alternate method, and then accept your answer ! Thanks again... –  Guilherme Oct 19 '11 at 19:22

Consider all subsets of $\{1,2,\dots,A+1\}$ of cardinality $A-s+1$. There are exactly $\binom{A+1}{s}$ subsets. For each such subset $x_1 < x_2 < \dots < x_{A-s+1}$ consider the element $x_{A-n+1}$. The number of subsets with fixed value $x_{A-n+1}=p:=A-n+j+1$ the number of desired subsets equals $\binom{A-n+j}{A-n}\binom{n-j}{n-s}=\binom{A-n+j}{j}\binom{n-j}{i}$. Then just sum up by all possible values of $j=x_{A-n+1}-A+n-1$.

-
Thanks for this answer...i like this combinatorial approach...although is a little confusing :) –  Guilherme Oct 20 '11 at 13:14

This also follows from the Chu-Vandermonde identity ${s+t \choose n}=\sum_{k=0}^n {s \choose k}{t \choose n-k}$ and the upper negation rule for binomial coefficients $\binom{r}{k} = (-1)^k \binom{k-r-1}{k}$.

$$\sum_{\substack{i+j=s \atop i\geq 0, j \geq 0}}\binom{A-n+j}{j}\binom{n-j}{i} = \sum_{j=0}^s \binom{A-n+j}{j}\binom{n-j}{s-j}.$$ Then apply upper negation to get $$\sum_{j=0}^s (-1)^j \binom{-A+n-1}{j} (-1)^{s-j}\binom{s-n-1}{s-j}.$$ Chu-Vandermonde followed by upper negation again yields $$= (-1)^s \binom{-A+s-2}{s} = \binom{A+1}{s}.$$

-
Thanks very much for this answer...Andrews used this approach to demonstrate the identity...but you really explained better ! –  Guilherme Oct 19 '11 at 20:40