Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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

2 Answers 2

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|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

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

share|improve this answer

Your Answer

 
discard

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.