Example 3 Prove: For any positive integer n, among the binomial coefficients Cnm(0⩽m⩽n), the number of odd ones is a power of 2.
Solution
Prove that representing n in binary as n=2α1+2α2+⋯+2αk(α1⩾α2⩾⋯⩾αk)⇒(1+x)n=(1+x)2α1(1+x)2α2⋯(1+x)2αk⇒(1+x)n≡(1+x2α1)(1+x2a2)⋯(1+x2αk)(mod2).
The polynomial on the right side of the equation contains exactly 2k terms, all of whose coefficients are 1 (odd), meaning that in the expansion of (1+x)n, exactly 2k terms have coefficients Cnm that are odd.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.