0
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.