10
$\begingroup$

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

$\endgroup$
5
  • 7
    $\begingroup$ I think this question is better suited for Math Stack Exchange. It follows directly from looking at the generating series. $\endgroup$ Oct 19, 2011 at 19:08
  • 1
    $\begingroup$ I took the liberty of inserting an " \atop " in the sum's index ;) $\endgroup$ Oct 19, 2011 at 19:16
  • $\begingroup$ @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. $\endgroup$ Oct 19, 2011 at 21:51
  • 3
    $\begingroup$ @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. $\endgroup$
    – Todd Trimble
    Oct 19, 2011 at 23:34
  • $\begingroup$ @Todd Trimble: You are right...that book is amazing! In fact, i have the book and had begun to study it, but i've stopped, to study another topics. Probably in some point i'll return... $\endgroup$
    – Guilherme
    Oct 20, 2011 at 13:06

4 Answers 4

13
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Guilherme
    Oct 19, 2011 at 19:22
11
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Thanks very much for this answer...Andrews used this approach to demonstrate the identity...but you really explained better ! $\endgroup$
    – Guilherme
    Oct 19, 2011 at 20:40
9
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for this answer...i like this combinatorial approach...although is a little confusing :) $\endgroup$
    – Guilherme
    Oct 20, 2011 at 13:14
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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