Show that $\binom{2n}{n}$ is an even number, for positive integers $n$.

Question

I would appreciate if somebody could help me with the following problem

Show by a combinatorial proof that

$$\dbinom{2n}{n}$$

is an even number, where $n$ is a positive integer.

I tried to solve this problem but I can't.

Answer 1

You should be familiar with the recursive definition of the binomial coefficients, that $\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}$

\begin{matrix}1\\ 1 & 1\\ 1 & 2 & 1\\ 1 & 3 & 3 & 1\\ 1 & 4 & 6 & 4 & 1\\ \vdots & & \vdots & & \vdots&\ddots\\ & \cdots& \binom{n-1}{r-1} & \binom{n-1}{r} & \cdots\\ & \cdots& & \binom{n}{r} & \cdots\end{matrix}

Now, notice that $\binom{2n}{n} = \binom{2n-1}{n-1} + \binom{2n-1}{n}$

Notice further that $\binom{2n-1}{n-1} = \binom{2n-1}{(2n-1)-(n-1)} = \binom{2n-1}{n}$

So, $\binom{2n}{n} = 2\cdot \binom{2n-1}{n}$ and is therefore even.

---

The combinatorial proof of the recursive definition is that to choose $r$ objects out of $n$ with one special object, either the special object is in the choosing or it is not. Breaking it into cases, if it is, you still need to choose $r-1$ objects out of the $n-1$ remaining. If it is not, then you still need to choose $r$ objects out of the $n-1$ remaining.

Hence $\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}$

Answer 2

$\binom{2n}{n}=\binom{n}{0}^2+\binom{n}{1}^2+\dots \binom{n}{n}^2\equiv \binom{n}{0}+\binom{n}{1}+\dots \binom{n}{n}=2^n$

---

$2^n\binom{2n}{n}=\color{red}{\binom{2n}{1}+\binom{2n}{2}+\dots \binom{2n}{n-1}}+\color{blue}{\binom{2n}{n+1}+\binom{2n}{n+2}+\dots\binom{2n}{2n}}=2\binom{2n}{1}+\binom{2n}{2}+\dots \binom{2n}{n-1}$ and hence odd.

---

The Kneser graph $K(2n,n)$ has $\binom{2n}{n}$ vertices and is $1$-regular. Since the number of odd vertices in any graph is even, $\binom{2n}{n}$ is even.

Answer 3

Let $S$ be all subsets of $T=\{1,2,3,\dots,2n\}$ of size $n$. There is an equivalence relation on $S$ where every equivalence class has two elements, $\{A,T\setminus A\}$.

Answer 4

Does this count? Count the number of ways to create a subset from a set of $2n$ elements. For each element, it's either in the set or out of the set for a total of $2^{2n}$ subsets. Now, these subsets can have any size from $0$ to $2n$, so we have

$$\sum_{k=0}^{2n}\binom{2n}k=2^{2n}$$

Now, choosing $k$ elements to include in the subset is the same as selecting $2n-k$ elements to exclude, or

$$\binom{2n}k=\binom{2n}{2n-k}$$

Now we can simply reorder the sum and the rest is algebra

$$\sum_{k=0}^{2n}\binom{2n}k=\binom{2n}n+\sum_{k=0}^{n-1}\left[\binom{2n}k+\binom{2n}{2n-k}\right]=\binom{2n}n+2\sum_{k=0}^{n-1}\binom{2n}k=2^{2n}$$

$$\binom{2n}n=2\left[2^{2n-1}-\sum_{k=0}^{n-1}\binom{2n}k\right]$$