Sunday, 3 July 2016

combinatorics - Proof strategy to show $large sum_{0 le x le a} normalsize binom{a}{x} binom{b}{n+x} = binom{a+b}{a+n} $



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?


Answer



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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...