1
$\begingroup$

I want to prove that if ${n\choose 1}=0\mod 2, {n\choose 2}=0\mod 2,...,{n \choose n-1}=0\mod 2$ then $n=2^r$. The first condition already gives us that $n=2^rm$ for some $m\in \mathbb{N}$. So these conditions can be summarized in the condition that $${2^rm\choose 2^{r-1}m+k}=0\mod 2$$ for $k=0,...,2^{r-1}m-1$. Then I came across Lucas' theorem which says that if $a=a_kp^k+a_{k-1}p^{k-1}+...+a_0$ and $b=b_kp^k+b_{k-1}p^{k-1}+...+b_0$ are base $p$ expansions of $a$ and $b$ (the $a_i$ and $b_i$ are not divisible by $p$) then $${a\choose b}=\prod_{i=0}^k{a_i\choose b_i}\mod p$$ with the convention that ${x\choose y}=0$ if $x<y$. This means that ${a\choose b}=0\mod p$ if and only if one of the base $p$ digits of $b$ is bigger than that of $a$.

To apply this in our case: ${2^rm\choose 2^{r-1}m+k}=0\mod 2$ if and only if one of the base 2 digits of $2^{r-1}m+k$ is bigger than that of $2^rm$. But this is always the case since we have always the coefficient $m$ before $2^{r-1}$ which we dont have in $2^rm$.

So I am confused because then this result should be true for all $m\in \mathbb{N}$, but it should not be. I hope you can clarify this.

$\endgroup$
3
  • $\begingroup$ In the base-$p$ expansion of a number, the coefficient of $p^s$ is always a non-negative integer strictly smaller than $p$. For $p = 2$, that leaves only $0$ and $1$. If $m > 1$, the coefficient of $2^{r-1}$ is therefore not $m$. Since $m$ is odd, the coefficient of $2^{r-1}$ in $2^{r-1}m$ is $1$, but that can be cancelled by the coefficient of $2^{r-1}$ in $k$. $\endgroup$ Oct 25, 2016 at 9:27
  • $\begingroup$ @DanielFischer I see, I got the definition of base p expansion totally wrong. Do you think I can use Lucas' theorem to solve this? Or are these better ways? $\endgroup$
    – Badshah
    Oct 25, 2016 at 9:40
  • $\begingroup$ By Lucas' theorem, $\binom{n}{k}$ is even if and only if there is at least one carry in the binary addition $k + (n-k)$. When does there exist a nontrivial ($0 < k < n$) carry-free binary addition $k + (n-k)$? $\endgroup$ Oct 25, 2016 at 10:02

1 Answer 1

1
$\begingroup$

HINT: You can use Vandermonde’s identity to prove by induction on $r$ that

  • $\binom{2^r}m\equiv0\pmod2$ for $1\le m\le 2^r-1$, and that
  • if $2^r<n<2^{r+1}$, there is an $m\in\{1,\ldots,n-1\}$ such that $\binom{n}m\equiv1\pmod2$.

Specifically, if $1\le n\le 2^r$ we have

$$\binom{2^r+n}m=\sum_k\binom{2^r}k\binom{n}{m-k}\;,$$

and by the induction hypothesis this is congruent mod $2$ to

$$\binom{2^r}0\binom{n}m+\binom{2^r}{2^r}\binom{n}{m-2^r}=\binom{n}m+\binom{n}{m-2^r}\;.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .