Answer to Question #192060 in Discrete Mathematics for ANJU JAYACHANDRAN

Question

Use generating function to prove the identity

n

∑

k=o



r

k

 s

n−k



=



r +s

n



Answer 1

$\sum_{k=0}^n\binom rk\binom s{n-k}=\binom {r+s} {n }$

we know, $(1+x)^{r+s}=(1+x)^r(1+x)^s$

$\sum_{k=0}^{r+s}\binom {r+s}{n}x^n=\sum_{j=0}^r \binom{r}{j}x^j+\sum_{a=o}^s\binom{s}{a}x^a$

Now we expand each of the summation on RHS upto $x^2$ -

$=[\binom r0+\binom r1x+\binom r2x^2+....][\binom s0+\binom s1x+\binom s2 x^2+...........] \\[9pt]=[\binom r0\binom s0]+[\binom r0\binom s1+[\binom s0\binom r1]x+[\binom r1\binom s1+\binom r0\binom s2+\binom r2\binom s0]x^2.......$

Thus By inspecting a clear Pattern is evident and the n^{th} Power of ''x'' is of the form -

$\sum _{k=0}^n \binom rk \binom s{n-k}x^k$

and This is equated to $\binom {n+m}{k} x^k.$

Hence, $\sum_{k=0}^n\binom rk\binom s{n-k}=\binom {r+s} {n }$