Binomial coefficient in Andrews' partition book

Question

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...

Answer 1

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.

Answer 2

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}.$$

Answer 3

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$.

Answer 4

Your identity is the same as $f_s:=\sum_{j=0}^s\binom{A-n+j}j\binom{n-j}{s-j}\binom{A+1}s^{-1}=1$ for all $s\geq0$. Define $$F(s,j):=\binom{A-n+j}j\binom{n-j}{s-j}\binom{A+1}s^{-1} \qquad \text{and} \qquad G(s,j)=-\frac{j(n+1-j)F(s,j)}{(s+1-j)(A+1-s)}.$$ Check routinely (say dividing both sides by $F(s,j)$ and simplifying) that $$F(s+1,j)-F(s,j)=G(s,j+1)-G(s,j). \tag1$$ Summing both sides over all integers $j$ and telescoping on the RHS gives $$f_{s+1}-f_s=\sum_{j\in\mathbb{Z}}G(s,j+1)-\sum_{j\in\mathbb{Z}}G(s,j)=0.$$ Note: we have used the convention $\binom{a}b=0$ of $b<a$ or $b<0$.

Since $f_0=1$, it follows that $f_s=1$ for all $s$. The proof is complete.