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
Tell me more
×
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.
|
|
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. |
|||
|
|
