# Prove that $2^n-k\choose k-1$ is even with all $k,n\in \mathbb N$, $1\le k\le 2^{n-1}$

Prove that $2^n-k\choose k-1$ is even with all $k,n\in \mathbb N$, $2\le k\le 2^{n-1}$

I'm stuck with it when solve a polynomial problem

Should we expand it? Or may we can use induction?

Thanks

-
When $k = 1$ we have $\binom{2^n-1}{1-1} = \binom{2^n-1}{0} = 1$ which is not even. –  Michael Albanese Jan 9 '13 at 10:52
Sorry $k \ge 2$ –  tangkhaihanh Jan 9 '13 at 11:05

Hint: Use Lucas Theorem for $p=2$. Esp the consequence.

Notice that $(2^n - k) +(k-1) = 2^n-1$. $k=1$ corresponds to the 'base' $k-1=0$ is the only binary number that consists of only 0.

-

The result can be proved by induction on $n$.

Suppose that $\binom{2^n-k}{k-1}$ is even for $2\le k\le 2^{n-1}$, and consider $\binom{2^{n+1}-k}{k-1}$ for some $k$ such that $2\le k\le 2^n$:

\begin{align*} \binom{2^{n+1}-k}{k-1}&=\binom{2^n+2^n-k}{k-1}\\ &\overset{(1)}=\sum_{i=0}^{2^n}\binom{2^n}i\binom{2^n-k}{k-1-i}\\ &=\binom{2^n-k}{k-1}+\binom{2^n-k}{k-1-2^n}+\sum_{i=1}^{2^n-1}\binom{2^n}i\binom{2^n-k}{k-1-i}\\ &=\binom{2^n-k}{k-1}+\sum_{i=1}^{2^n-1}\binom{2^n}i\binom{2^n-k}{k-1-i}\;, \end{align*}

since $k-1-2^n<0$. $\binom{2^n}i$ is even for $1\le i\le 2^n-1$, so by the induction hypothesis $\binom{2^{n+1}-k}{k-1}$ is even if $k\le 2^{n-1}$. And if $k>2^{n-1}$, then $k-1\ge 2^{n-1}>2^n-k$, so $\binom{2^n-k}{k-1}=0$, and again $\binom{2^{n+1}-k}{k-1}$ is even.

At $(1)$ I used the Vandermonde identity

$$\binom{n}k=\sum_{i=0}^m\binom{m}i\binom{n-m}{k-i}\;,$$

and throughout I use the convention that $\binom{n}k=0$ if $k>n$ or $k<0$. The fact that $\binom{2^n}i$ is even for $1\le i\le 2^n-1$ can be found in this PDF; it can also be proved by induction using the Vandermonde identity.

-