Pascal triangle, binomial coefficients odd/even?

Question

I have managed to prove that $\dbinom{2^n}{k}$ is even for all $1\leq k \leq 2^n-n$ and that $\dbinom{2^n-1}{k}$ is odd for all $k$ using induction on $m$.

How can I prove that $\dbinom{2^n+r}{1+r},\dots,\dbinom{2^n+r}{2^m-1}$ are even for $0 \leq r \leq 2^m-2$ ?

How can I prove that $\dbinom{2^n+r}{r},\dbinom{2^n+r}{2^m}$ are odd for $0 \leq r \leq 2^m-1$?

Answer 1

You've already proven all there is to prove about the case $r=0$, so I'll assume $1 \le r < 2^n$.

We can summarise the cases of interest as $$\binom{2^n+r}{m}, \quad r \le m \le 2^n$$ Since you're willing to assume Vandermonde's identity, we have $$\binom{2^n+r}{m} = \sum_{k=0}^m \binom{2^n}{k} \binom{r}{m-k}$$ Since $m \le 2^n$, all but the $k=0$ term and the $k=m$ term (in the case $m=2^n$) must be even, so $$\binom{2^n+r}{m} \equiv \binom{r}{m} + \binom{2^n}{m} \pmod 2$$

• When $m=r$ we get $\binom{2^n+r}{m} \equiv 1 + 0 \pmod 2$
• When $m=2^n>r$ we get $\binom{2^n+r}{m} \equiv 0 + 1 \pmod 2$
• When $r < m < 2^n$ we get $\binom{2^n+r}{m} \equiv 0 + 0 \pmod 2$.