两道高中排列组合的等式证明题目。

Question

注释：为方便表示，如nCr表示n个元素中选r个的组合数

需证明以下两个等式：
kCk+(k+1)Ck+(k+2)Ck+······+(k+n)Ck=(n+k+1)C(k+1)
nC1+2*nC2+3*nC3+······n*nCn=(1/2)*(cC0+cC1+······+nCn)

Answer 1

C(r,n)：r是上标、n是下标。
【1】
C(k,k)＋C(k,k＋1)＋C(k,k＋2)＋…＋C(k,k＋n)
=C(k＋1,k＋1)＋C(k,k＋1)＋C(k,k＋2)＋…＋C(k,k＋n)
利用：C(k＋1,n＋1)＋C(k,n＋1)=C(k＋1,n＋2)
则：
原式=C(k＋1,k＋1)＋C(k,k＋1)＋C(k,k＋2)＋…＋C(k,k＋n) 【前2个继续用公式】
=C(k＋1,k＋2)＋C(k,k＋2)＋C(k,k＋3)＋…＋C(k,k＋n)
=C(k＋1,k＋3)＋C(k,k＋3)＋…＋C(k,k＋n)
=…………
=C(k＋1,n＋k＋1)

【2】
S=(1,n)＋2C(2,n)＋3C(3,n)＋…＋nC(n,n)
倒序，得：
S=nC(n,n)＋(n－1)C(n－1,n)＋…＋2C(2,n)＋C(1,n)
相加，得：[注意：需要错位，即：第一个等式中的第一个和第二个等式中的第二个配对，并注意到：C(k,n)=C(n－k,n)]
则：
2S=nC(n,n)＋nC(1,n)＋nC(2,n)＋…＋nC(n,n)
2S=nC(0,n)＋nC(1,n)＋nC(2,n)＋…＋nC(n,n)
2S=n×[C(0,n)＋C(1,n)＋C(2,n)＋C(3,n)＋…＋C(n,n)]
2S=n×2^n
S=n×2^(n－1)