2
$\begingroup$

Suppose that $N$ and $r$ are positive integers. Prove or disprove that if $N$ is an even integer and $r$ is odd, then $\binom{N}{r}$ is even.

My attempt:

Let $N=2m$ and $r=2k+1$. Then $$\binom{N}{r}=\binom{2m}{2k+1}=\dfrac{(2m)!}{(2(m-k)-1)!(2k+1)!}$$ Also, we know that $\binom{N}{r}$ is always an integer. How do I proceed to show it is even or odd?

Also note that $n!$ is even for all $n\ge2$.

$\endgroup$

3 Answers 3

5
$\begingroup$

By Legendre's formula, the power of $2$ dividing $n!$ is $$v_2(n!)=\sum_{i=1}^\infty \left\lfloor\frac{n}{2^i}\right\rfloor.$$ So the power of $2$ dividing $\binom{n}{r}=\frac{n!}{r!(n-r)!}$ is $$\sum_{i=1}^\infty\left( \left\lfloor\frac{n}{2^i}\right\rfloor-\left\lfloor\frac{r}{2^i}\right\rfloor-\left\lfloor\frac{n-r}{2^i}\right\rfloor\right).$$

For each $i$, the term in parentheses is nonnegative since $\lfloor a\rfloor + \lfloor b\rfloor \leq \lfloor a+b\rfloor$ for any $a,b$. Do you see why the term for $i=1$ must be strictly positive, which would imply that the sum is also positive and give the conclusion you want?

$\endgroup$
4
$\begingroup$

Suppose you have $n$ elements and you choose $r$ of them. Since $n$ is even, pair off the $n$ elements into $n/2$ pairs. Number the pairs $p_1, ... p_{n/2}$. Since $r$ is odd, at least one of the pairs has one chosen and one unchosen element. Let $i$ be the smallest index of such a pair.

Then, "swap" the choice in $p_i$. That is: if $p_i$ consists of objects $a$ and $b$, and $a$ was chosen in the original choice, then choose $b$ instead.

For every way to choose $r$ objects from a set of $n$, this "swap" gives a new way. Swapping twice results in the original way, and swapping once gives a different way.

Therefore, this "swap" corresponds to a function $f$ from $\binom{n}{r}$ to itself that has no fixed points and $f \circ f = id$. This can only happen on a set with an even number of elements.

$\endgroup$
1
$\begingroup$

I think the easiest way to see this is as follows. If $N$ is even and $r$ is odd then any selection of $r$ items from $N$ either has an odd number of items in the first half and an even number in the second half, or vice versa. By symmetry, each of these possibilities gives rise to the same number of selections.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .