If $n\ge2$, Prove $\binom{2n}{3}$ is even.

Any help would be appreciated. I can see it's true from pascal's triangle, and I've tried messing around with pascal's identity and the binomial theorem to prove it, but I'm just not making any headway.

Solution 1:

$${2n\choose 3}=\frac{(2n)(2n-1)(2n-2)}{6}=\frac{n(2n-1)(n-1)\cdot 2}{3}$$ Note that the numerator is a multiple of 2, while the denominator is not, hence the result must be a multiple of 2.

In fact, since one of $n, n-1$ must be even, the number ${2n\choose 3}$ must be a multiple of $4$, not just $2$.

Solution 2:

Combinatorial arguments are good, too.

Imagine that you have $n$ couples, for a total of $2n$ people. Let $\mathscr{T}$ be the collection of all $\binom{2n}3$ sets of $3$ of these people. For each $T\in\mathscr{T}$ let $T'$ be the member of $\mathscr{T}$ obtained by trading each member of $T$ for that person’s spouse. Thus, if $T$ does not contain a couple, then $T\cap T'=\varnothing$, while if $T$ does contain a couple, $T'$ contains the same couple and the spouse of the third member of $T$. Note that in every case $T\ne T'$, and $(T')'=T$.

$$\big\{\{T,T'\}:T\in\mathscr{T}\big\}$$

is then a partition of $\mathscr{T}$ into two-element sets, so $\binom{2n}3=|\mathscr{T}|$ is even.

Solution 3:

Here's an approach not using factorials:

Take $2n$ objects and separate them into two groups of $n$. You're interested in the number of ways you can choose $3$ of them. For any such choice, you'll have more from one pile than the other. By symmetry, there'll be the same number of choices that "favor" each pile over the other, so in total there will be an even number of choices.

This argument works to prove the evenness of $2n\choose k$ for any odd number $k$.

Solution 4:

$\displaystyle\ \dfrac{(2n)(2n\!-\!1)(2n\!-\!2)}{3\cdot 2\cdot 1} \, =\, \dfrac{\color{#c0f}4}{\color{#0a0}{2n\!+\!1}}\dfrac{(\color{#0a0}{2n\!+\!1})(2n)(2n\!-\!1)(2n\!-\!2)}{\color{#c0f}4\cdot 3\cdot 2\cdot 1}\, =\, \dfrac{\color{#c00}4}{2n\!+\!1}{2n\!+\!1\choose 4}\ $ is $\,\rm\color{#c00}{even}$

Remark $\ $ The same method shows $\ k\!+\!1 \mid {\large {\,n\,\choose k}}\, $ if $\ \gcd(k\!+\!1,n\!+\!1)=1,\,$ e.g.

$$ a^{\large k}\, {\Large \mid}\ {an\choose a^{\large k}\!-1}\qquad\quad$$

Your example is simply the special case $\ a=2 = k.$

Solution 5:

In the spirit of various other answers, let $S=\{\color{red}1,\color{blue}1,\color{red}2,\color{blue}2\dots, \color{red}n,\color{blue}n\}$. If $T$ is a $3$-element subset of $S$, one color predominates among its elements, and the set $T'$, obtained by changing the color of every number in $T$, is a different $3$-element subset of $S$. (The other color predominates.) The $3$-element subsets of $S$ can thus be collected into disjoint pairs, each subset paired with its “color opposite,” so there must be an even number of these subsets.