Why is the binomial coefficient $\binom{\text{even}}{\text{odd}}$ always even?

Question

I recently came across the following:

Fix an odd $k\in\mathbb{N}$. Then for all even $n\in\mathbb{N}, \binom{n}k \text{ is even.}$

I'd like to complete my attempted proof by induction (see below), although other arguments are equally welcomed.

Proof attempt

Let $k\in\mathbb{N}$ with $k$ odd.

$\underline{\text{Base Case:}}$ [n=2] Then $\binom{n}k=\binom{2}k$. If $k=1$, then $\binom{2}1=2$ is even. If $k>1$, then $\binom{2}k=0$, which is also even.

$\underline{\text{Induct:}}$ Let $n\in\mathbb{N}$ be even. Assume that $\binom{n}k$ is also even. Say, $\binom{n}k=2l$ for some $l\in\mathbb{N}$. We'll show $\binom{n+2}k$ is even. Consider,

$$ \begin{aligned} \binom{n+2}k&=\frac{(n+2)!}{k![(n+2)-k]!}\\[10pt] &=\frac{(n+2)(n+1)n}{k![(n-k)+2][(n-k)+1](n-k)!}\\[10pt] &=\frac{(n+2)(n+1)}{[(n+2)-k][(n+1)-k]}\cdot\frac{n!}{k!(n-k)!}\\[10pt] &=\frac{(n+2)(n+1)}{[(n+2)-k][(n+1)-k]}\cdot 2l \end{aligned} $$

I suppose if one can show that $\frac{(n+2)(n+1)}{[(n+2)-k][(n+1)-k]}$ is a natural number, they'd be done. However, I'm unsure how to do this, and I'm not entirely convinced it's always true. Suppose $n=6$ and $k=3$, then: $$\frac{(n+2)(n+1)}{[(n+2)-k][(n+1)-k]}=\frac{8\cdot 7}{5\cdot 4}=\frac{14}{5}$$ which is certainly not a natural number. This leads me to believe there's an error in my reasoning, but I cannot see where I went wrong.

Answer 1

Assume your induction hypothesis. Write $${{n+2}\choose{k}}={{n+1}\choose k} + {{n+1}\choose {k-1}}={n\choose k}+2{n\choose {k-1}}+{n\choose {k-2}}$$

Can you conclude?

Answer 2

Another method is to use Kummer's Theorem; a proof is given in this answer. It says that the number of factors of a prime $p$ that divide $\binom{n}{k}$ is the number of carries when adding $k$ and $n-k$ in base $p$.

In this case $p=2$, and both $k$ and $n-k$ are odd. Adding $k$ and $n-k$ produces at least one carry in the $0$ bit ($1+1=10)$. Thus, there is at least one factor of $2$ in $\binom{n}{k}$.

Answer 3

We can give a combinatorial proof of this as well. We just need to prove that there are an even number of subsets of $\{1,\dots,n\}$ which have a size of $k$. We do this by showing how to pair up all of the subsets.

Let $S\subset \{1,\dots,n\}$ be a subset whose size is $k$. Also, given sets $A$ and $B$, let $A\oplus B=(A\setminus B)\cup (B\setminus A)$ be the symmetric difference of $A$ and $B$.

• Suppose that $|S\cap \{1,2\}|=1$. In this case, we pair $S$ with $S\oplus \{1,2\}$. In words, if $S$ contains exactly one of the numbers $1$ or $2$, then we pair $S$ with the result of switching $1$ for $2$.

• Otherwise, $|S\cap \{1,2\}|$ is $0$ or $2$. We next look at $|S\cap \{3,4\}|$. If $|S\cap \{3,4\}|=1$, then $S$ is paired with $S\oplus \{3,4\}$.

• Otherwise, we look at $S\cap \{5,6\}$. In general, we keep examining $S\cap \{2i-1,2i\}$, for $i=1,2,3,\dots$, until we find the first $k$ for which $|S\cap \{2i-1,2i\}|=1$, and then we pair $S$ with $S\oplus \{2i-1,2i\}$.

Note that the process must stop at some point. If the process never stopped, it would mean that $|S\cap \{2i-1,2i\}|$ is $0$ or $2$ for all $i$. However, since $|S|$ is the sum of $|S\cap \{2i-1,2i\}|$, this would mean that the size of $S$ is a sum of even numbers, contradicting that $k$ is odd.

Answer 4

As noticed in the comments, the solution given by Pascal's rule can be obtained directly by counting as follows, assuming that ${n\choose k}$ is even, adding $2$ new elements to $n$ we can obtain the following sets:

• the same ${n\choose k}$ sets obtained previously
• the ${n\choose k-1}$ sets containing the first new element
• the ${n\choose k-1}$ sets containing the second new element
• the ${n\choose k-2}$ sets containing both new elements

that is

$${{n+2}\choose{k}}={n\choose k}+2{n\choose {k-1}}+{n\choose {k-2}}$$

Answer 5

Let $n=2m$. Consider the problem of picking some $x_1,x_2,\ldots,x_m,y_1,y_2,\ldots,y_m\in\{0,1\}$ such that $$ \sum_{i=1}^m x_i + \sum_{i=1}^m y_i = k. $$ The set of all feasible solutions can be partitioned into two disjoint sets $S_1$ and $S_2$, where $\sum_i x_i$ is odd in $S_1$ and even in $S_2$. Since $k$ is odd, $S_2$ is identical to the set of all solutions such that $\sum_i y_i$ is odd. Hence $|S_1|=|S_2|$ by symmetry and the total number of solutions is even. This means $\binom{n}{k}$ is even.

Answer 6

Here's another combinatorial proof.

I'll show that ${ 2a \choose 2b + 1 }$ is even by constructing an explicit involution on the objects we're counting.

First, let's note that when $2b + 1 > 2a$ or $2b + 1 < 0$, then ${ 2a \choose 2b + 1 }$ is zero which is less than one.

Next, suppose we have a combination of $2b + 1$ items from $2a$.

We can write out our choice with $2a$-letter words, with a $1$ corresponding to items that we picked and a zero corresponding to items that we didn't pick.

For example, $10011011000 \cdots$.

None of these words are a palindrome because a palindrome with an even length must have an even number of each letter.

Therefore, reversing the string has no fixed points and corresponds to another way to choose $2b+1$ items.

Therefore we have an involution with no fixed points on the natural combinatorial interpretation of ${ 2a \choose 2b+1 }$

Therefore ${ 2a \choose 2b+1 }$ is even.

Answer 7

Since we're doing proofs which are not necessarily by induction, I thought I'd add my own. The case $k=1$ is trivial. For $k>1$, $${n\choose k}=\frac nk{n-1\choose k-1},\text{ whence }\operatorname{ord}_2\left[{n\choose k}\right]=\operatorname{ord}_2(n/k)+\operatorname{ord}_2\left[{n-1\choose k-1}\right]>1.$$

Answer 8

Another combinatorial answer.

1. Let's take for granted that in a set $S$ of finite even cardinality $2m$, we can isolate a subset $A \subseteq S$ of cardinality $m$ and we can find a bijection $f: A \to S\setminus A$.

2. The bijection $f$ induces the following map on the power set $2^S$: $$g: 2^S \to 2^S: B\mapsto f(B\cap A)\cup f^{-1}(B\cap A^c)$$

3. Note that $g$ preserves the size of any subset of $S$. The restriction of $g$ to the subsets of size $k$ ($k \in \{1,...,2m\}$) is an involution that and if $k$ is odd, this restriction has not a single fixed point...

Now conclude for yourself.