Thm.(Vandermonder's Indentity)Vm,n,r20 (+）=(0()-(O) a(+）-(0) proof: 1) (1+x)m+n=(1+x)m=(1+x)" →(-0)》 compute coefficient offor both side +)-王)）-2() (2) 三(0G)-2(0(m)-王（(m）-(+) [Exercise】 含（因-(） ()）()-(C+） 同()-）-（+0-) ④（图）(）=(a)-m）≥≥m )()-(a） Thm.(Vandermonder’s Indentity) ∀m, n, r ≥ 0 (1)  m + n r  = Pr i=0  n i  m r − i  = P i+j=r  n i m j  . (2)  m + n r + m  = P i−j=r  n i m j  . proof: (1) (1 + x) m+n = (1 + x) m = (1 + x) n ⇒ mX +n r=0  m + n r  x r = Xn i=0  n i  x iXm j=0  m j  x j compute coefficient of x r for both side.  m + n r  = X i+j=r  n i m j  = Xr i=0  n i  m r − i  . (2) X i−j=r  n i m j  = X i−j=r  n i  m m − j  = X i+(m−j)=m+r  n i  m m − j  =  m + n r + m  . [Exercise] (1) Pn k=0  n k 2 =  2n n  . (2) Pn k=0  m k  n p + k  =  n + m p + m  . (3) Pm k=1  m k n − 1 k − 1  =  n + m − 1 n  . (4)  n k  k m  =  n m n − m k − m  (n ≥ k ≥ m). (5) Pn k=0  n k  k m  =  n m  2 n−m. 9