Skip to main content.

Solution to puzzle 57: Binomial coefficient divisibility

Show that, for n > 0, the binomial coefficient  C(2n,n) = (2n)! / (n! n!)  is divisible by n + 1 and by 4n − 2.

Consider, for n greater than 0, [n/(n+1)] * C(2n,n) = C(2n,n-1)

This is an integer, by virtue of its being a binomial coefficient.

Since n and n + 1 are relatively prime, C(2n,n) must be divisible by n + 1.


Now consider, for n greater than 0, [n/(2n(2n-1))] * C(2n,n) = C(2n-2,n-1) / n

By the previous result, for n > 1, this is an integer.  It is an integer by inspection for n = 1.

Therefore, C(2n,n) is divisible by 2(2n − 1) = 4n − 2.

Source: Inspired by Catalan Number

Back to top