choose(n, k) is an integer!

 On this image, I merely wanted to test the Blender integrated renderer with some highly refractive material. It does work: the cube seems elevated (as objects in water) and stretched into the lens. However, I did not really try to make the lens crystal clear. (See the Blender source file)

The number of combination of objects (from 0 to ) taken among , which we denote either by or , is computed by:

.

Because is the same as , let's replace by wherever it is greater than half of . We may also write this more explicitly:

.

If we forget the relation between this quotient of products and the number of combinations, it struck me as non-evident and even astonishing that the above always yield an integer. Consider, for example:

.

For the result to be integer, each factor in the denominator has to be completed consumed by some part of the numerator. How does it work here? The 5 ought to be matched with the 10. Let's match 3 with 9. The 7 is not useful, here. 4 could be matched with 8 and 2 by 6. Now, consider:

.

Both 7 and 11 are useless. 3 has to go with 9. 4 could go with 8 and 2 with whatever is left from 8 or 10. As you see, the strategy is different, and working more examples show that there is no simple preset strategy for getting rid of the whole denominator, or at least, I did not see it. How comes the guarantee that simplification is always possible? This looks far more obscure than evident.

Moreover, the challenge may be extended from the binomial case, as above, to the multinomial case:

As , is merely a particular case of the multinomial.

From a purely mathematical standpoint, how comes multinomial numbers are always integers? What certainty do we have that the simplification always occurs? Strangely, I did not find a direct proof of this (I did not overly tried, and am not sure I would have succeeded). However, in a book, I found an inductive proof for this theorem stating that the product of any successive positive integers is divisible by .

Let's say means the product of consecutive integers starting with . (You may note that , but we do not use this). Because , the theorem trivially holds for all . If it holds for , let's prove it also holds for . Merely consider this:

The first term of the sum is already divisible by . The second term of the sum is divisible by and, because it has as a supplementary factor, it is divisible by as well!

From this theorem, the integral property for multinomials quickly follows, and consequently, the integral property for binomials as well. Despite the proof exists, the magic of factor matching between numerators and denominators, remains an intriguing matter!