Is $\binom{2^{n}}{j}\cdot 2^{2^{n}-j}$ divisible by $2^{n}$ for all $0 \leq j < 2^{n}$?

Question

This is immediate for $j \leq 2^{n}-n$. I also know that $0 \equiv 3^{2^{n}} - 1 = \sum_{j=0}^{2^{n}-1} \binom{2^{n}}{j}\cdot 2^{2^{n}-j} \mod{2^{n}}$. Induction does not seem to help. Any hints or suggestions?

Answer 1

The case $j = 0$ is trivial.

For any $q \in \mathbb{Q}$, let $\epsilon(q)$ denote the exponent of $2$ in the prime factorization of $q$ (we can define $\epsilon(0) = +\infty$ by convention, but it doesn't matter). We will prove that $$(\forall j \in \{1, \ldots, j-1\}) \epsilon \left( \binom{2^n}{j} \right) \geq n + j - 2^n.$$ Since $\binom{2^n}{j} = \binom{2^n}{2^n - j}$, we can equivalently prove that $$(\forall j \in \{1, \ldots, j-1\})\epsilon \left( \binom{2^n}{j} \right) \geq n - j.$$

In the expression $$\binom{2^n}{j} = \frac{2^n}{j} \times \frac{2^n-1}{1} \times \frac{2^n - 2}{2} \times \frac{2^n - 3}{3} \times \cdots \times \frac{2^n - (j-1)}{j-1}$$ every factor in the numerator except for $2^n$ is paired with a factor in the denominator divisible by an identical power of $2$, so $$\epsilon\binom{2^n}{j} = n - \epsilon(j)$$ and the conclusion follows from the fact that $\epsilon(j) \leq \log_2(j) < j$ for all positive integers $j$.