2
$\begingroup$

The following two combinatorial identities are taken from a textbook. $$\begin{align} &\large \sum_{0\ \le \ x \ \le \ n} \normalsize \binom{a}{x} \binom{b}{n-x} = \binom{a+b}{n} \tag{10} \\ &\large \sum_{0 \ \le \ x \ \le \ a} \normalsize \binom{a}{x} \binom{b}{n+x} = \binom{a+b}{a+n}\tag{11} \\ \end{align}$$

What proof strategy would you suggest to prove identity $(11)$, algebraically? We may assume Vandermonde's Identity $(10)$; it may be useful in a proof of identity $(11)$.

There appear to be many similarities between the two identities. How might we make use of that?

$\endgroup$
  • 1
    $\begingroup$ Does it have to be an "algebraic" proof? I find a more useful strategy is sometimes to interpret everything combinatorially. For instance, the first identity's right side might make me think of counting how many ways to choose $n$ people from a collection of $a$ males and $b$ females. $\endgroup$ – alex.jordan Jan 5 '14 at 4:13
2
$\begingroup$

Identity (11), just like (10), is obvious on combinatorial grounds, but you asked for an algebraic proof. Let $y=a-x$.$$\binom{a+b}{a+n}=\sum_{x=0}^\infty\binom ax\binom b{a+n-x}=\sum_{x=0}^\infty\binom a{a-x}\binom b{a-x+n}=\sum_{y=0}^\infty\binom ay\binom b{y+n}=\sum_{x=0}^\infty\binom ax\binom b{x+n}$$

$\endgroup$
3
$\begingroup$

You can try a change of variable: replace $x$ in (11) with $a-x.$ The summation and the first binomial coefficient are unchanged by this replacement. The second binomial coefficient then starts to look like the second binomial coefficient in (10), except that you have $n+a$ instead of $n.$ To match the form of (10), the summation would need to run up to $n+a$ rather than $a.$ In fact, it's OK to make this change in the summation. (Why?)

$\endgroup$
3
$\begingroup$

The first one:

$$(1+x)^a (1+x)^b = (1+x)^{a+b}.$$ What is the coefficient of $x^n$ on the LHS? RHS?

Second one $$(1+1/x)^a(1+x)^b = (1+x)^a (1+x)^b/x^a.$$ What is the coefficient of $x^n$ on the LHS? RHS?

$\endgroup$
1
$\begingroup$

You just replace $n$ by $b-n$ in the first identity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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