Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

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


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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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