Maths Olympiad Prep

Library / /474 of 520

Combinatorics Difficulty 5.9 AIME, harder Prove it

Example 3 Prove: For any positive integer nn, among the binomial coefficients Cnm(0mn)\mathrm{C}_{n}^{m}(0 \leqslant m \leqslant n), the number of odd ones is a power of 2.

Solution

Prove that representing nn 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). \begin{array}{l} n=2^{\alpha_{1}}+2^{\alpha_{2}}+\cdots+2^{\alpha_{k}}\left(\alpha_{1} \geqslant \alpha_{2} \geqslant \cdots \geqslant \alpha_{k}\right) \\ \Rightarrow(1+x)^{n}=(1+x)^{2 \alpha_{1}}(1+x)^{2 \alpha_{2}} \cdots(1+x)^{2 \alpha_{k}} \\ \Rightarrow(1+x)^{n} \\ \quad \equiv\left(1+x^{2 \alpha_{1}}\right)\left(1+x^{2 a_{2}}\right) \cdots\left(1+x^{2 \alpha_{k}}\right)(\bmod 2) . \end{array}

The polynomial on the right side of the equation contains exactly 2k2^{k} terms, all of whose coefficients are 1 (odd), meaning that in the expansion of (1+x)n(1+x)^{n}, exactly 2k2^{k} terms have coefficients Cnm\mathrm{C}_{n}^{m} 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.