(nr)=(n1r1)+(n1r)

言わずもがな.パスカルの三角形

(nr)=nr(n1r1)

定義から明らか.

i=rn(ir)=(n+1r+1)

Hockey-stick identity. 次のように1を繰り返し適用. (n+1r+1)=(nr)+(nr+1)=(nr)+(n1r)+(n1r+1)=(nr)+(n1r)+(n2r)+(n2r+1)=

i=0r(ni)(mri)=(n+mr)

|A|=n, |B|=m であるとき,AB の排他和から r 個取るのは,A から i 個取って B から ri 個取ることになる.

i=0r(ni)(mr+i)=(n+mn+r)

上と類似.左辺は i=0r(nni)(mi+r) と書き直せる. AB の排他和から n+r 個取るときには,少なくとも B から r 個は取るので,B から i+r 個,A から ni 個取ることになる.

r=0nr(nr)=n2n1

(左辺) =r=1nr(nr)=nr=1n(n1r1)=n2n1= (右辺)