BinomialExpansion MODBasic DifferentBase Difficult

Problem - 4305

Let the binary representation of positive integer $n$ be $b_tb_{t-1}\cdots b_1b_0$. Show that $$\binom{n}{2^j} \equiv b_j \pmod{2}$$

where $j$ is a non-negative integer. Note that $\binom{n}{m} = 0$ if $m > n$.


By the definition of binary representation, we have $$n=\sum_{i=0}^{t}b_i\cdot 2^i$$

For convenience, let the set $\{2^{i_0}, 2^{i_1}, \cdots, 2^{i_t}\}$ be $\mathbb{S}$.

Replacing the exponent $n$ leads to $$(1+x)^n=(1+x)^{\sum_{i=0}^{t}b_i\cdot 2^i}=\prod_{i=0}^{t}(1+x)^{2^i\cdot b_i}$$

Because all the $b_i$ are either $0$ or $1$, therefore the coefficient of the term $x^k$, i.e. $\binom{n}{k}$, will be the number of ways that $k$ can be expressed in the following ways: $$k=2^{j_0} +2^{j_1}+\cdots + 2^{j_s} $$

where $\{2^{j_0}, 2^{j_1}, \cdots, 2^{j_s}\}\in\mathbb{S}$ and $j_0 < j_1 <\cdots < j_s$.

This is essentially the binary representation of $k$. Because a number's binary representation is unique, therefore $k$ will be either $1$ or $0$ depending on whether it can be represented using a linear combination of $2^{i_0}$, $2^{i_1}$, $\cdots$, $2^{i_t}$.

In particular, when $k=2^j$, the result will be $1$ if $2^j\in\mathbb{S}$, or equivalently $b_j = 1$. Otherwise, its value will be $0$ if $2^j\not\in$, or equivalently, $b_j=0$. Either way, we have $$\binom{n}{k}=\binom{n}{2^j}\equiv b_j\pmod{2}$$

report an error