MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 10 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer
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}.$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.