How to prove binomial coefficient $ {2^n \choose k} $ is even number?

Prove:

${2^n \choose k}$ (for integers $k$ & $n$ : $0<k<2^n$) is even number.

I have tried induction but was unable to get any useful results.

Solution 1:

We can prove by induction on $n$ that if you treat $(x+1)^{2^n}$ formally as a polynomial in $x$ and reduce each coefficient $\pmod{2}$, then $(x+1)^{2^n} \equiv x^{2^n} + 1 \pmod{2}$. For $n=0$, this is trivial to check. For the inductive step, $(x+1)^{2^{n+1}} = \left[(x+1)^{2^n} \right]^2 \equiv (x^{2^n}+1)^2 = x^{2^{n+1}} + 2 x^{2^n} + 1 \equiv x^{2^{n+1}} + 1 \pmod{2}$.

On the other hand, by the binomial theorem, $(x+1)^{2^n} = \sum_{k=0}^{2^n} \binom{2^n}{k} x^k$. Therefore, if $\sum_{k=0}^{2^n} \binom{2^n}{k} x^k \equiv x^{2^n} + 1 \pmod{2}$, then by comparing coefficients, we must have $\binom{2^n}{k} \equiv 0 \pmod{2}$ for $0 < k < 2^n$. (And then, since $2^n > n$ for $n \ge 0$, this implies the desired result.)

(Note that in this argument, it is important to treat the expressions formally as polynomials - or as elements of $(\mathbb{Z} / 2 \mathbb{Z})[x]$ if you're familiar with that notation. Otherwise, if we treated them as functions $\mathbb{Z} \to \mathbb{Z}$, then just knowing that $f(n) \equiv g(n) \pmod{2}$ for every $n \in \mathbb{Z}$ is not sufficient to conclude that the coefficients of $f$ are congruent to the corresponding coefficients of $g$ $\pmod{2}$. For example, $n^2 + n \equiv 0 \pmod{2}$ for every $n \in \mathbb{Z}$, yet we do not have $x^2 + x \equiv 0 \pmod{2}$ formally as a polynomial identity.)

Solution 2:

Provided that you already know $\binom{2^n}{k}$ is an integer, it suffices to show the numerator has more factors of $2$ than the denominator. We have: $$\binom{2^n}{k}=\frac{(2^n)(2^n-1)\cdots(2^n-k+1)}{k!}.$$ There are at least $n$ factors of $2$ in the numerator because $2^n$ is a factor. So now we need to count the number of factors of $2$ in the denominator, $k!$.

We have $k!=k(k-1)(k-2)\cdots 3\cdot 2 \cdot 1$. At most $\frac{k}{2}$ of these numbers are divisible by $2$. At most $\frac{k}{4}$ of them are divisible by $4$. At most $\frac{k}{8}$ of them are divisible by $8$. And so on. Each number that is divisible by $2$ contributes a factor of $2$, each number that is divisible by $4$ contributes an additional factor of $2$, each number that is divisible by $8$ contributes a third factor of $2$, and so on. So the number of factors of $2$ in $k!$ is no more than $$\frac{k}{2}+\frac{k}{4}+\frac{k}{8}+\cdots = k.$$ Since $k<n$, the denominator has strictly fewer factors of $2$ than the numerator.

Solution 3:

There is a proof by induction using the Vandermonde identity: $$ \binom{2^n}k=\sum_{i=0}^k \binom{2^{n-1}}i\binom{2^{n-1}}{k-i}, $$ You can verify all of the summands are even using the induction hypothesis, as long as $n>1$. You then just need the base case $n=1$.

Solution 4:

Let $n,k$ be integers, $0\lt k\lt2^n$.

Let $S$ be the set of all bitstrings of length $n$, and let $\binom Sk$ be the set of all $k$-element subsets of $S$, so that $|S|=2^n$ and $|\binom Sk|=\binom{2^n}k$. We show that $\binom Sk$ has an even number of elements by defining a fixed-point-free involution $\varphi:\binom Sk\to\binom Sk$.

For $i\in[n]=\{1,\dots,n\}$, let $\varphi_i:S\to S$ be the involution which flips the $i^\text{th}$ bit; and for $X\in\binom Sk$, let $\varphi_i[X]=\{\varphi_i(x):x\in X\}\in\binom Sk$.

If $X\in\binom Sk$, since $\emptyset\ne X\ne S$, there is some $i\in[n]$ such that $\varphi_i[X]\ne X$; let $i(X)$ be the least such $i$.

Finally, define $\varphi:\binom Sk\to\binom Sk$ by setting $\varphi(X)=\varphi_{i(X)}[X]$. It is easy to see that $\varphi$ is a fixed-point-free involution.

More generally, a similar argument shows that $\binom{p^n}k$ is divisible by p whenever $p$ is a prime number and $n,k$ are integers, $0\lt k\lt p^n$.

Solution 5:

More generally, if $p$ is a prime number, and if $n,k$ are integers such that $0\lt k\lt p^n$, then the binomial coefficient $\binom{p^n}k$ is divisible by $p$.

Let $\nu_p(m)$ denote the highest exponent $\nu$ such that $p^\nu$ divides $m$. Let $h=p^n-k$. Since $$\nu_p\left(\binom{p^n}k\right)=\nu_p\left(\frac{p^n!}{h!k!}\right)=\nu_p(p^n!)-\nu_p(h!)-\nu_p(k!),$$ it will suffice to show that $\nu_p(p^n!)-\nu_p(h!)-\nu_p(k!)\ge1.$ In view of Legendre's formula $$\nu_p(m!)=\sum_{i=1}^\infty\left\lfloor\frac m{p^i}\right\rfloor,$$ this is the same as showing that $$\sum_{i=1}^\infty\left(\left\lfloor\frac{p^n}{p^i}\right\rfloor-\left\lfloor\frac h{p^i}\right\rfloor-\left\lfloor\frac k{p^i}\right\rfloor\right)\ge1.\tag1$$ Now, every term of the series is nonnegative, since $\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor$ for all real $x,y$.
Since the $i=n$ term is $$\left\lfloor\frac{p^n}{p^n}\right\rfloor-\left\lfloor\frac h{p^n}\right\rfloor-\left\lfloor\frac k{p^n}\right\rfloor=1-0-0=1,$$ the inequality $(1)$ follows and everything is fine.