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

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?

• For $j=2^n$, this is obviously wrong. Are you sure of your statement ? – TheSilverDoe Mar 19 at 17:29
• @TheSilverDoe Oops! Meant for $j \geq 1$. Wil fix. – Fred Mar 19 at 17:49
• And ? This is still wrong for $j=2^n$... – TheSilverDoe Mar 19 at 17:51
• @TheSilverDoe Yes, got confused for a sec... fixed. – Fred Mar 19 at 17:57
• Do you know how to calculate the $2$-part of the binomial coefficient? – the_fox Mar 19 at 18:02

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$$.