Berkeley Math Circle Monthly Contest 7

Solution:
We can write $\binom{2^{n}+i}{i}$ as $\prod_{k=1}^{i} \frac{2^{n}+k}{k}$. For any $k \leq i < 2^{n}$, the number of times $2$ divides $2^{n}+k$ is just the number of times $2$ divides $k$, so this product must have an equal number of factors of $2$ in the numerator and denominator, and therefore must be odd. Thus, as there are $2^{n}$ values of $i$ and $2^{n}$ possible values of $r$ $\pmod{2^{n+1}}$, the problem is equivalent to showing that $\binom{2^{n}+i}{i}$ is injective $\pmod{2^{n+1}}$ for $0 \leq i < 2^{n}$.

Let $0 \leq i < j < 2^{n}$. Taking the ratio of the corresponding coefficients gives $\prod_{k=i+1}^{j} \frac{2^{n}+k}{k}$. Let $\nu$ be maximal so that there is a multiple of $2^{\nu}$ in the range $(i, j]$, and let this multiple be $m 2^{\nu}$ where $m$ is odd.

Now take the ratio $\bmod 2^{n-\nu+1}$. For $k = m 2^{\nu}$, $\frac{2^{n}+k}{k} = \frac{2^{n-\nu}+m}{m}$, which is not equivalent to one, whereas for $k \neq m 2^{\nu}$, $\frac{2^{n}+k}{k}$ is equivalent to one. Therefore, the total product is not one $\bmod 2^{n-\nu+1}$, so it is not one $\bmod 2^{n+1}$, as desired.