Show that for any given positive integer n, the number of odd nCm with 0 ≤ m ≤ n is a power of 2.
Solution
(2n)C(2m+1) = 2n/(2m+1) (2n-1)C2m, which is even. There are n even factors in the numerator of 2nC2m and n even factors in its denominator. If we cancel 2 from each of these even factors, then we get nCm. So 2nC2m has the same parity as nCm. Hence there are the same number of odd binomial coefficients for 2n as for n.
(2n+1)C2m =2nC(2m-1) + 2nC2m, so (2n+1)C2m has the same parity as 2nC2m. Similarly, (2n+1)C(2m+1) = 2nC2m + 2nC(2m+1), so (2n+1)C(2m+1) has the same parity as 2nC2m. Hence there are twice as many odd binomial coefficients for 2n+1 as for 2n.
The required result now follows by a trivial induction.
© John Scholes
jscholes@kalva.demon.co.uk
4 Dec 1999