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$$