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