Question

Prove that nCk (n and k natural numbers with k<=n) (combination) is always a natural number, or that k!(n-k)! is always divisible by n! or that the product of k consecutive natural numbers will always be divisible by k!.

Answer 1

my first reaction is that since \(\dbinom{n}{k}\) is the number of ways to choose \(k\) objects from a set of \(n\) by the counting principle, then it must be a natural number

Answer 2

That is correct, but I am looking for an arithmetical approach to the problem.

Answer 3

how about a nice proof by induction? since you have an \(n\) here that seems like the natural approach
otherwise i guess you will need some argument using the fundamental theorem of arithmetic, i.e. argue about the prime factorization, but i think that will be cumbersome

Answer 4

a quick google search gives and inductive proof here
http://math.stackexchange.com/questions/12067/the-product-of-n-consecutive-integers-is-divisible-by-n-without-using-the-prop

Answer 5

Thank you. Never thought of induction. :)

Answer 6

i think brute force is going to be somewhat longer,
see
http://gowers.wordpress.com/2010/09/18/are-these-the-same-proof/

Answer 7

yw