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



Binomial coefficient in Andrews' partition book
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.


