Question

组合数学中恒等式的证明： 1、Σ(i=0,n)i^2*C(n,i)=n*(n+1)*2^(n-2);

还有一个： Σ(i=0,n)(1/(i+1)(i+2))C(n,i)=(2^(n+2)-n-3)/((n+1)(n+2))麻烦给出详解，谢谢！

Answer 1

第一个，利用 (1+x)^n=Σ(i=0,n) C(n,i)*x^i，两边对x求导，得：
n*(1+x)^(n-1)=Σ(i=1,n) i*C(n,i)*x^(i-1). 两边同乘以x，得：
n*x*(1+x)^(n-1)=Σ(i=1,n) i*C(n,i)*x^i. 两边再对x求导，得：
n*(1+x)^(n-1)+n*x*(n-1)*(1+x)^(n-2)=Σ(i=1,n) i^2*C(n,i)*x^(i-1). 令x=1，整理，得证。

第二个，利用 A: Σ(i=0,n) C(n,i)=2^n 和 B: Σ(i=1,n) i*C(n,i)=n*2^(n-1).
左式=Σ(i=0,n) (1/(i+1)-1/(i+2))*C(n,i)
=(1-1/2)*C(n,0)+(1/2-1/3)*C(n,1)+(1/3-1/4)*C(n,2)+...+(1/n-1/(n+1))*C(n,n-1)+(1/(n+1)-1/(n+2))*C(n,n)
=C(n,0)-(1/(n+2))*C(n,n)+(1/2)*(C(n,1)-C(n,0))+(1/3)*(C(n,2)-C(n,1))+...+(1/(n+1))*(C(n,n)-(n,n-1))
=1-1/(n+2)+Σ(i=1,n) (1/(i+1))*(C(n,i)-C(n,i-1))
=(n+1)/(n+2)+Σ (1/(i+1))*(n! / (i!*(n-i)!) - n! / ((i-1)!*(n-i+1)!))
=(n+1)/(n+2)+Σ (1/(i+1))*((n-i-1-i)*n!) / (i!*(n-i+1)!)
=(n+1)/(n+2)+Σ ((n-2*i+1)/(n+1)*(n+2))*((n+2)! / ((i+1)!*(n-i+1)!))
=(n+1)/(n+2)+1/((n+1)(n+2)) Σ (n+3-2*i-2)*C(n+2,i+1)
=(n+1)/(n+2)+(n+3)/((n+1)*(n+2)) Σ C(n+2,i+1) - 2/((n+1)*(n+2)) Σ (i+1)*C(n+2,i+1)
利用A化简第二项
=(n+1)/(n+2)+((n+3)*(2^(n+2)-n-4)) / ((n+1)*(n+2)) - 2/((n+1)*(n+2)) Σ(i=2,n+1) i*C(n+2,i)
利用B化简第三项
=(n+1)/(n+2)+((n+3)*(2^(n+2)-n-4))/((n+1)*(n+2)) - (2*((n+2)*2^(n+1)-2*n-4)) / ((n+1)*(n+2))
然后化简一下，就得证啦。