How to prove binomial coefficient $ {2^n \choose k} $ is even number? Prove:
${2^n \choose k}$ (for integers $k$ & $n$ : $0<k<2^n$) is even number.
I have tried induction but was unable to get any useful results. 
 A: We can prove by induction on $n$ that if you treat $(x+1)^{2^n}$ formally as a polynomial in $x$ and reduce each coefficient $\pmod{2}$, then $(x+1)^{2^n} \equiv x^{2^n} + 1 \pmod{2}$.  For $n=0$, this is trivial to check.  For the inductive step, $(x+1)^{2^{n+1}} = \left[(x+1)^{2^n} \right]^2 \equiv (x^{2^n}+1)^2 = x^{2^{n+1}} + 2 x^{2^n} + 1 \equiv x^{2^{n+1}} + 1 \pmod{2}$.
On the other hand, by the binomial theorem, $(x+1)^{2^n} = \sum_{k=0}^{2^n} \binom{2^n}{k} x^k$.  Therefore, if $\sum_{k=0}^{2^n} \binom{2^n}{k} x^k \equiv x^{2^n} + 1 \pmod{2}$, then by comparing coefficients, we must have $\binom{2^n}{k} \equiv 0 \pmod{2}$ for $0 < k < 2^n$.  (And then, since $2^n > n$ for $n \ge 0$, this implies the desired result.)
(Note that in this argument, it is important to treat the expressions formally as polynomials - or as elements of $(\mathbb{Z} / 2 \mathbb{Z})[x]$ if you're familiar with that notation.  Otherwise, if we treated them as functions $\mathbb{Z} \to \mathbb{Z}$, then just knowing that $f(n) \equiv g(n) \pmod{2}$ for every $n \in \mathbb{Z}$ is not sufficient to conclude that the coefficients of $f$ are congruent to the corresponding coefficients of $g$ $\pmod{2}$.  For example, $n^2 + n \equiv 0 \pmod{2}$ for every $n \in \mathbb{Z}$, yet we do not have $x^2 + x \equiv 0 \pmod{2}$ formally as a polynomial identity.)
A: Provided that you already know $\binom{2^n}{k}$ is an integer, it suffices to show the numerator has more factors of $2$ than the denominator. We have:
$$\binom{2^n}{k}=\frac{(2^n)(2^n-1)\cdots(2^n-k+1)}{k!}.$$
There are at least $n$ factors of $2$ in the numerator because $2^n$ is a factor. So now we need to count the number of factors of $2$ in the denominator, $k!$. 
We have $k!=k(k-1)(k-2)\cdots 3\cdot 2 \cdot 1$. At most $\frac{k}{2}$ of these numbers are divisible by $2$. At most $\frac{k}{4}$ of them are divisible by $4$. At most $\frac{k}{8}$ of them are divisible by $8$. And so on. Each number that is divisible by $2$ contributes a factor of $2$, each number that is divisible by $4$ contributes an additional factor of $2$, each number that is divisible by $8$ contributes a third factor of $2$, and so on. So the number of factors of $2$ in $k!$ is no more than 
$$\frac{k}{2}+\frac{k}{4}+\frac{k}{8}+\cdots = k.$$
Since $k<n$, the denominator has strictly fewer factors of $2$ than the numerator. 
A: There is a proof by induction using the Vandermonde identity:
$$
\binom{2^n}k=\sum_{i=0}^k \binom{2^{n-1}}i\binom{2^{n-1}}{k-i},
$$
You can verify all of the summands are even using the induction hypothesis, as long as $n>1$. You then just need the base case $n=1$. 
A: Let $n,k$ be integers, $0\lt k\lt2^n$.
Let $S$ be the set of all bitstrings of length $n$, and let $\binom Sk$ be the set of all $k$-element subsets of $S$, so that $|S|=2^n$ and $|\binom Sk|=\binom{2^n}k$. We show that $\binom Sk$ has an even number of elements by defining a fixed-point-free involution $\varphi:\binom Sk\to\binom Sk$.
For $i\in[n]=\{1,\dots,n\}$, let $\varphi_i:S\to S$ be the involution which flips the $i^\text{th}$ bit; and for $X\in\binom Sk$, let $\varphi_i[X]=\{\varphi_i(x):x\in X\}\in\binom Sk$.
If $X\in\binom Sk$, since $\emptyset\ne X\ne S$, there is some $i\in[n]$ such that $\varphi_i[X]\ne X$; let $i(X)$ be the least such $i$.
Finally, define $\varphi:\binom Sk\to\binom Sk$ by setting $\varphi(X)=\varphi_{i(X)}[X]$. It is easy to see that $\varphi$ is a fixed-point-free involution.
More generally, a similar argument shows that $\binom{p^n}k$ is divisible by p whenever $p$ is a prime number and $n,k$ are integers, $0\lt k\lt p^n$.
A: The following solution (copypasted from my old coursework) is purely
elementary number theory:
We set $\mathbb{N}=\left\{  0,1,2,\ldots\right\}  $.

Lemma 1. Let $n$ be an integer. Let $m$ be a positive integer. Then,
  $\dbinom{n}{m}=\dfrac{n}{m}\cdot\dbinom{n-1}{m-1}$.

Proof of Lemma 1. We have
\begin{align*}
\dbinom{n}{m} &  =\dfrac{n\cdot\left(  n-1\right)  \cdot\cdots\cdot\left(
n-m+1\right)  }{m!}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}\dbinom{n}{m}\right)  \\
&  =\dfrac{n\cdot\left(  \left(  n-1\right)  \cdot\left(  n-2\right)
\cdot\cdots\cdot\left(  n-m+1\right)  \right)  }{m\cdot\left(  m-1\right)
!}\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}
\text{since}\\
n\cdot\left(  n-1\right)  \cdot\cdots\cdot\left(  n-m+1\right)  =n\cdot\left(
\left(  n-1\right)  \cdot\left(  n-2\right)  \cdot\cdots\cdot\left(
n-m+1\right)  \right)  \\
\text{and }m!=m\cdot\left(  m-1\right)  !
\end{array}
\right)  \\
&  =\dfrac{n}{m}\cdot\dfrac{\left(  n-1\right)  \cdot\left(  n-2\right)
\cdot\cdots\cdot\left(  n-m+1\right)  }{\left(  m-1\right)  !}\\
&  =\dfrac{n}{m}\cdot\underbrace{\dfrac{\left(  n-1\right)  \cdot\left(
n-2\right)  \cdot\cdots\cdot\left(  \left(  n-1\right)  -\left(  m-1\right)
+1\right)  }{\left(  m-1\right)  !}}_{\substack{=\dbinom{n-1}{m-1}
\\\text{(since this is how }\dbinom{n-1}{m-1}\text{ is defined)}}}\\
&  \qquad\qquad\left(  \text{since }n-m=\left(  n-1\right)  -\left(
m-1\right)  \right)  \\
&  =\dfrac{n}{m}\cdot\dbinom{n-1}{m-1}.
\end{align*}
Thus, Lemma 1 is proven. $\blacksquare$

Lemma 2. Let $x$, $y$ and $z$ be three integers such that $x\mid yz$ and
  $\gcd\left(  x,y\right)  =1$. Then, $x\mid z$.

Lemma 2 is a classical result in elementary number theory (see, e.g.,
Proposition 1.2.8 in my 18.781 (Spring 2016): Floor and arithmetic
functions).
$\blacksquare$

Lemma 3. Let $p$ be a prime number. Then, every positive divisor of
  $p^{\alpha}$ is a power of $p$.

Proof of Lemma 3. Let $d$ be a positive divisor of $p^{\alpha}$. We must
show that $d$ is a power of $p$.
Assume the contrary. Thus, the prime factorization of $d$ must contain at
least one prime $q$ distinct from $p$. Consider this $q$. Now, $q\mid d$
(since the prime factorization of $d$ contains $q$). Hence, $q\mid d\mid
p^{\alpha}$ (since $d$ is a divisor of $p^{\alpha}$). Thus, the prime
factorization of $p^{\alpha}$ contains the prime $q$ (since $q$ is a prime).
Since this prime factorization is clearly $\underbrace{pp\cdots p}
_{\alpha\text{ times}}$, we thus conclude that the prime factorization
$\underbrace{pp\cdots p}_{\alpha\text{ times}}$ contains $q$. Hence, $q=p$.
This contradicts the fact that $q$ is distinct from $p$. This contradiction
proves that our assumption was wrong; hence, Lemma 3 is proven. $\blacksquare$

Lemma 4. Let $p$ be a prime number. Let $\alpha\in\mathbb{N}$. Let $u$ be
  an integer such that $u$ is not divisible by $p$. Then, $\gcd\left(
u,p^{\alpha}\right)  =1$.

Proof of Lemma 4. The integer $\gcd\left(  u,p^{\alpha}\right)  $ is a
positive divisor of $p^{\alpha}$, and therefore a power of $p$ (by Lemma 3).
In other words, $\gcd\left(  u,p^{\alpha}\right)  =p^{\beta}$ for some
$\beta\in\mathbb{N}$. Consider this $\beta$. If $\beta>0$, then $p\mid
p^{\beta}=\gcd\left(  u,p^{\alpha}\right)  \mid u$, which contradicts the
assumption that $u$ is not divisible by $p$. Hence, we cannot have $\beta>0$,
and thus we must have $\beta=0$. Hence, $p^{\beta}=p^{0}=1$ and $\gcd\left(
u,p^{\alpha}\right)  =p^{\beta}=1$. This proves Lemma 4. $\blacksquare$

Theorem 5. Let $p$ be a prime number. Let $\alpha\in\mathbb{N}$ and let
  $k$ be an integer such that $0<k<p^{\alpha}$. Then, $\dbinom{p^{\alpha}}{k}$
  is divisible by $p$.

Your claim follows from Theorem 5 (applied to $p=2$ and $\alpha=n$), since your $k$ satisfies $0 < k < n \leq 2^n$.
Proof of Theorem 5. Assume the contrary. Thus, $\dbinom{p^{\alpha}}{k}$ is
not divisible by $p$. Hence, Lemma 4 (applied to $u=\dbinom{p^{\alpha}}{k}$)
that $\gcd\left(  \dbinom{p^{\alpha}}{k},p^{\alpha}\right)  =1$.
Applying Lemma 1 to $n=p^{\alpha}$ and $m=k$, we obtain $\dbinom{p^{\alpha}
}{k}=\dfrac{p^{\alpha}}{k}\cdot\dbinom{p^{\alpha}-1}{k-1}$, so that
$k\dbinom{p^{\alpha}}{k}=p^{\alpha}\dbinom{p^{\alpha}-1}{k-1}$. Thus,
$p^{\alpha}\mid k\dbinom{p^{\alpha}}{k}=\dbinom{p^{\alpha}}{k}k$. Hence, Lemma
2 (applied to $x=p^{\alpha}$, $y=\dbinom{p^{\alpha}}{k}$ and $z=k$) yields
$p^{\alpha}\mid k$ (since $\gcd\left(  p^{\alpha},\dbinom{p^{\alpha}}
{k}\right)  =\gcd\left(  \dbinom{p^{\alpha}}{k},p^{\alpha}\right)  =1$). Since
$k$ is positive, this yields $k\geq p^{\alpha}$; but this contradicts
$k<p^{\alpha}$. This contradiction shows that our assumption was wrong. Thus,
Theorem 5 is proven. $\blacksquare$
A: More generally, if $p$ is a prime number, and if $n,k$ are integers such that $0\lt k\lt p^n$, then the binomial coefficient $\binom{p^n}k$ is divisible by $p$.
Let $\nu_p(m)$ denote the highest exponent $\nu$ such that $p^\nu$ divides $m$. Let $h=p^n-k$. Since
$$\nu_p\left(\binom{p^n}k\right)=\nu_p\left(\frac{p^n!}{h!k!}\right)=\nu_p(p^n!)-\nu_p(h!)-\nu_p(k!),$$
it will suffice to show that $\nu_p(p^n!)-\nu_p(h!)-\nu_p(k!)\ge1.$
In view of Legendre's formula
$$\nu_p(m!)=\sum_{i=1}^\infty\left\lfloor\frac m{p^i}\right\rfloor,$$
this is the same as showing that
$$\sum_{i=1}^\infty\left(\left\lfloor\frac{p^n}{p^i}\right\rfloor-\left\lfloor\frac h{p^i}\right\rfloor-\left\lfloor\frac k{p^i}\right\rfloor\right)\ge1.\tag1$$
Now, every term of the series is nonnegative, since $\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor$ for all real $x,y$.
Since the $i=n$ term is
$$\left\lfloor\frac{p^n}{p^n}\right\rfloor-\left\lfloor\frac h{p^n}\right\rfloor-\left\lfloor\frac k{p^n}\right\rfloor=1-0-0=1,$$
the inequality $(1)$ follows and everything is fine.
A: The solution is immediate using Lucas's theorem since
$${2^n \choose k} = \prod_{i=0}^n{m_i \choose k_i} \mod 2$$ where $m_i$ are the binary coefficients of $2^n$ and $k_i$ those of $k$, and since $k < 2^n$ then some $k_j$ ($j < n$) is equal to 1 while $m_j = 0$ because the only coefficient of $2^n$ equal to 1 is $m_n$.
