怎樣證明組合數一定是正整數?

Let P(n) be the proposition that
C(n,m) are all integers for all positive integers n where 0 <= m <= n
P(1) is obviously true since
C(1,0) = 1; and C(1,1) = 1 are all integers
Assume P(k) is true, that is,
C(k,0), C(k,1), C(k,2) ... ,C(k,k) are all integers
Then
For 0 <= m <= k
C(k+1,m) = (k+1)! / [(k+1 - m)! m!]
= {k! / [(m - 1)! (k - m)!]}{(k+1) / [m(k + 1 - m)]}
= {k! / [(m - 1)! (k - m)!]}[1/m + 1/(k +1 - m)]
= k! / [m! (k - m)!] + k! / [(m - 1)! (k +1 - m)!]
= C(k, m) + C(k, m-1) is an integer
Also C(k+1,k+1) = 1 is integer
Therefore C(k+1,m) is integer for 0 <= m <= k + 1 => P(k+1) is true
So inductively, P(n) is true for all positive integers n

用 induction，用 Pascal triangle。