用母函数证明另一个基础的组合公式
假设要证明:
C(n,r)=C(n-1,r-1)+C(n-1,r)
先根据(1+x)^(n-1)=C(n-1,0)+C(n-1,1)*x+...C(n-1,r)*x^r+...+C(n-1,n-1)*x^(n-1)
然后在方程两边分别乘以1+x
有(1+x)^n={ C(n-1,0)+C(n-1,1)*x+...C(n-1,r)*x^r+...+C(n-1,n-1)*x^(n-1) }*(1+x)
Go
而(1+x)^n的母函数展开为C(n,0)+C(n,1)*x+...C(n,r)*x^r+...+C(n,n)*x^(n)
对应项系数相等，对于x^r,所以有:C(n,r)=C(n-1,r-1)+C(n-1,r).
