If ${n\choose 1}=0\mod 2, {n\choose 2}=0\mod 2,...,{n \choose n-1}=0\mod 2$ then $n=2^r$

Question

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.

Answer 1

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}\;.$$