9
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ For the inductive step we could use a counting approach. $\endgroup$
    – user
    Commented Jan 3 at 8:25
  • 1
    $\begingroup$ Hint: Use recurrence relation for ${n+2}\choose{k+2}$ $\endgroup$ Commented Jan 3 at 8:34
  • $\begingroup$ 1. If you really want to prove this algebraically, you have to prove your binomial coefficient is divisible by nominator of conducted fraction and result is still even after division. Easier use Legendre formula or combinatoric interpretation like friend above $\endgroup$ Commented Jan 3 at 8:34
  • $\begingroup$ Odd/even decision for binomial coefficients is easy. Write both $n$ and $k$ in base $2$: $$n=\sum_{i=0}^m n_i2^i,\quad k=\sum_{i=0}^m k_i2^i,$$ where $n_i,k_i\in\{0,1\}$ for all $i$. Then $\binom n k$ is odd if and only if $n_i\ge k_i$ for all $i$. For example with $n=6=110_2$ and $k=3=011_2$ the least significant bits fail as $n_0=0<k_0=1$. Indeed, $\binom 6 3=15$ is odd. Something similar holds for other primes $p$ (not only $p=2$). It follows from Lucas's theorem. I jotted down a proof here. $\endgroup$ Commented Jan 4 at 6:53
  • $\begingroup$ (cont'd) Arguably Lucas is overkill for the purposes of your task. I just think it is kinda neat. See also robjohn's answer below. Kummer's theorem enhances Lucas's in the cases where we want to know the power of a prime dividing a binomial coefficient. $\endgroup$ Commented Jan 4 at 6:55

8 Answers 8

16
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Ah yes, I think I understand. You did two successive applications of Pascal's rule for binomial coefficients to obtain that identity. In particular, we know by the inductive hypothesis that $\binom{n}k$ is even. The second term is obviously even. For the last term, I believe it's also even by the inductive hypothesis? Then again, we assumed $\binom{n}k$ was even for some fixed odd $k$. Are we allowed to generalize that and say because $k-2$ is also odd, by the inductive hypothesis $\binom{n}{k-2}$ is also even? Moreover, why did my original approach fail? Why was my counterexample incorrect? $\endgroup$
    – John Smith
    Commented Jan 3 at 8:59
  • 1
    $\begingroup$ Correct, use strong induction. That is, fix $n,k$ with $n$ even and $k$ odd, and assume the statement to be true for all $n'\leq n$ and for all $k'\leq k-2$. Then, continue as my answer. $\endgroup$ Commented Jan 3 at 9:01
9
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ +1 To my taste, this is the nicest argument by far! The core idea can be cut down to a sentence: “${n \choose k}$ counts length-$n$ strings of zeroes and ones containing $k$ ones; when $n$ is even and $k$ odd, reversing gives a fixed-point-free involution of such strings, hence partitions them into pairs.” $\endgroup$ Commented Jan 4 at 10:04
5
$\begingroup$

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}$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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}}$$

$\endgroup$
1
$\begingroup$

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.$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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