nC4= (n-1)C3 + (n-2)C3 +.... + 3C3

$$證明C^n_4 = \sum_{k=3}^{n-1}C^k_3$$

證明：

方法一

\(C^n_4:\)將\(n\)個人任取4人的組合數；假設\(n\)個人中有一個叫派大星的，因此取4人可以分成有選到派大星及沒有選到派大星的組合數。

派大星必選：\(n\)個人中，先將派大星選出，在剩下的\(n-1\)人任選3人，組合數為\(C^{n-1}_3\)；

不選派大星：\(n\)個人中，先將派大星剔出，在剩下的\(n-1\)人任選4人，組合數為\(C^{n-1}_4\)；

因此，將\(n\)個人任取4人的組合數=\(C^{n-1}_3+C^{n-1}_4\)，即\(C^n_4 =C^{n-1}_3+C^{n-1}_4\)。

同理\(C^{n-1}_4= C^{n-2}_3+C^{n-2}_4 =C^{n-2}_3+C^{n-3}_3+ C^{n-3}_4 = \cdots = C^{n-2}_3+C^{n-3}_3+\cdots +C^3_3\)，因此\(C^n_4 = \sum_{k=3}^{n-1}C^k_3\)。

方法二$$C^n_4={n!\over 4!(n-4)!} ={n\over n-4 }\cdot {(n-1)!\over 4!(n-5)!} ={n\over n-4 }C^{n-1}_4 = \left( 1+{4\over n-4}\right)C^{n-1}_4 =C^{n-1}_4 +{4\over n-4}C^{n-1}_4 \\ =C^{n-1}_4 +{4\over n-4}\cdot {(n-1)! \over 4!(n-5)!} =C^{n-1}_4 + {(n-1)! \over 3!(n-4)!} =C^{n-1}_4+ C^{n-1}_3 \\ \Rightarrow C^n_4=C^{n-1}_4+ C^{n-1}_3\\ 同理，依此類推C^n_4=C^{n-1}_3 + C^{n-1}_4  = C^{n-1}_3+ C^{n-2}_3 +C^{n-2}_4 =C^{n-1}_3+ C^{n-2}_3 +\cdots +C^3_3$$