조합식에 관련된 흥미로운 등식

$$\sum_{y=0}^x ( {}_a C_y ~{}_b C_{x-y} ) = {}_{a+b} C_x$$

위 등식이 성립합을 확인해보자.

우선

$(t+1)^a(t+b)^b = (t+1)^{a+b}$

위 식의 양변에서 임의의 항의 계수는 같음을 보여보자

가령 $t^n$의 계수를 구해보자

우변의 경우 $t^n$의 계수는 ${}_{a+b} C_n$이다 $(n \leq a+b)$

좌변의 경우를 구하기 위해 식을 전개해보면

$$[{}_a C_{a} t^{a} + {}_a C_{a-1} t^{a-1} + \cdots + {}_a C_{1} t^{1} + {}_a C_{0} t^{0} ]\cdot [{}_b C_{b} t^{b} + {}_b C_{b-1} t^{b-1} + \cdots + {}_b C_{1} t^{1} + {}_b C_{0} t^{0} ]$$

$t^n$의 항만을 계산하고 계수를 비교해보자

$$\begin{align*} &{}_{a} C_{n}t^{n} \cdot {}_{b} C_{0}t^{0}  + {}_{a} C_{n-1}t^{n-1} \cdot {}_{b} C_{1}t^{1} + \cdots {}_{a} C_{1}t^{1} \cdot {}_{b} C_{n-1}t^{n-1}  +{}_{a} C_{0}t^{0} \cdot {}_{b} C_{n}t^{n} \\ &= ({}_{a} C_{n} \cdot {}_{b} C_{0}  + {}_{a} C_{n-1} \cdot {}_{b} C_{1} + \cdots {}_{a} C_{1} \cdot {}_{b} C_{n-1} +{}_{a} C_{0} \cdot {}_{b} C_{n})t^n\\ &= \sum_{i=0}^{n}({}_a C_i)({}_b C_{n-i}) \cdot t^n~~~~~, n \leq a,b \end{align*}\\ \therefore \sum_{i=0}^{n}({}_a C_i)({}_b C_{n-i}) = {}_{a+b} C_n$$