$2^n$ choose something Let $m$ be a positive integer, and let $n=2^m$. Prove that the numbers  $$ \binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{n-1} $$ are all even.
-Source: ASMP sample problems Counting Strategies number 2
 A: Since you do not show any work, not sure what you are allowed to use. Here is an outline of induction proof.
Assume it true for $n=2^m$. Have to show for $n=2^{m+1}$. Divide $n$ objects into two halves of size $n/2$. Now the number of ways of choosing $k$ objects out of $n$, is the total of number of ways of choosing $l$ objects from first half and $k-l$ from the second half, i.e.
$$
\binom{n}{k} = \sum \binom{n/2}{l} \binom{n/2}{k-l}
$$
You can fill in the rest.
A: Note that in general
$$\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}.$$
This can be proved by expressing the binomial coefficients in terms of factorials, or by a combinatorial argument. Thus
$$n\binom{n-1}{r-1}=r\binom{n}{r}.$$
In our case we get
$$2^m \binom{2^m-1}{r-1}=r\binom{2^m}{r}.$$
The highest power of $2$ that divides the left-hand side is $\ge 2^m$. If $r$ is different from $0$ or $2^m$, the highest power of $2$ that divides $r$ is less than $2^m$. Thus $2$ must divide $\binom{2^m}{r}$. 
A: If $p$ is prime then
$$ \binom{pn}{pk} \equiv \binom{n}{k} \pmod{p} $$
and
$$ \binom{pn}{k} \equiv 0 \pmod{p} \qquad\text{if $p\nmid k$.} $$
(Here's a kind of combinatorial proof (pdf) of these statements that I wrote up a while back.)  (And, as noted there, it can be proved by induction as in user44197's answer.)
So, start with $\binom{2^m}{k}$.  If $k$ is even, cancel a 2 from the top and bottom, using the first statement above, and iterate; eventually the number on the bottom will be odd, and then you're done, by the second statement above.
