一个重要的母函数定理的证明

一个重要的母函数定理的证明

1/(1-x)^n=C(n-1,n-1)+C(n,n-1)*x+C(n+1,n-1)*x^2+...+C(n+j-1,n-1)*x^j..

用数学归纳法证明：

设有上面等式成立：

方程两边分别乘以1/(1-x)有：

因为1/(1-x)=1+x+x^2+x^3+...

1/(1-x)^(n+1)={ C(n-1,n-1)+C(n,n-1)*x+C(n+1,n-1)*x^2+...+C(n+j-1,n-1)*x^j.. }

               *{ 1+x+x^2+x^3+...  }

Go

1/(1-x)^(n+1)=C(n-1,n-1)+{ C(n-1,n-1) + C(n,n-1) }*x+{ C(n-1,n-1) + C(n,n-1) + C(n+1,n-1)}*x^2+...+{ C(n-1,n-1) + C(n,n-1) + C(n+1,n-1)  +...+ C(n+j-1,n-1)}*x^j.. 

目前我们针对x^j的系数推导：

 C(n-1,n-1) + C(n,n-1) + C(n+1,n-1)  +...+ C(n+j-1,n-1)

=C(n-1,n-1) + {  C(n+1 , n) -C(n,n) } + { C(n+2,n)-C(n+1,n) } +...+ {  C(n+j , n) - C(n+j-1 ,n)}

=C(n+j,n)

所以得到证明；

 

注意这里关于为什么得出这个公式，这个和newton的定理一样是不得而知的。但可以证明；

 

同样也可以做这样的推导：

1/(1-x)*1/(1-x)...*1/(1-x)

=(1+x+x^2+x^3+...)*(1+x+x^2+x^3+...)*...*(1+x+x^2+x^3+...)  (一共有n个)

特别的当每项x的幂最高只能为1时就退化为newton的二项式定理了,这很神奇。