Combinatorial proofs that $\binom{2^n}{k}$ is even for every $n\geq 1$ and $1\leq k \leq 2^n-1$.

Question

I am trying to prove that $\binom{2^n}{k}$ is even for every $n\geq 1$ and $1\leq k \leq 2^n-1$.

The one I could come up with is that the equivalence relation where $A\sim B$ if $B$ is of the form $A+k$ for some $k$ with the addition taken $\bmod 2^n$ splits the subsets into classes, no class has size $1$ and the size is a divisor of $2^n$ so they are all even. I am wondering if there are other combinatorial proofs.

Answer 1

Here is a very simple combinatorial proof which requires no induction. Let $T$ be a complete binary ordered tree with $n$ levels, meaning that there are $2^{n}-1$ internal vertices each with a left child and a right child, and $2^n$ leaves all at depth $n$. Letting $X$ be the set of leaves of $T$, we will define a fixed-point-free involution $f$ on $\binom{X}k$ when $0<k<2^n$, which proves that $\binom{|X|}k=\binom{2^n}k$ is even.

Let $S$ be a subset of $X$ with size $k$. To define $f(S)$, we find an internal vertex $v\in T$ at maximal depth such at least one of the following conditions hold:

1. All leaves which are left descendants of $v$ are in $S$, and all leaves which are right descendants of $v$ are $\notin S$.

2. All leaves which are left descendants of $v$ are in $\notin S$, and all leaves which are right descendants of $v$ are in $S$.

If there are multiple such $v$ on the same level, then choose the leftmost such vertex. Finally, to get $f(S)$, assuming $v$ satisfies the first condition above, we remove all the left descendants of $v$ from $S$, then add in all of the right descendants of $v$ to $S$. If $v$ instead satisfies the second condition, do the reverse. Clearly, $f(S)$ is a new set of size $k$ which is different from $S$.

It is not hard to how that $f$ is well-defined. Such an internal vertex $v$ must exists; if not, all leaves would be forced to simultaneously be in $S$ or out of $S$, so $k=0$ or $2^n$. Furthermore, this in indeed an involution, since the vertex $v$ found for $S$ will also be the same vertex for $f(S)$.

Answer 2

You can prove this by induction on $n$ using combinatorial arguments within the induction step.

For $n \ge 1$, let $\mathcal{S}_n$ be the statement: $$\binom{2^n}{k} \equiv 0 \pmod 2,\quad \forall 1 \le k < 2^n$$

• $\mathcal{S}_1$ is trivally true.

• For $n > 1$, assume $\mathcal{S}_{n-1}$ is true.

  Let $G$ be a set of $2^n$ elements. Let $G_1, G_2$ be two subsets of $G$ with $2^{n-1}$ elements so that $G$ is their disjoint union. For any $1 \le k < 2^n$, split the choices of selecting $k$ elements from $G$ into $3$ groups:

  1. $N_>$ : number of choices of picking more elements from $G_1$ than $G_2$.
  2. $N_=$ : number of choices of picking same number of elements from $G_1$ and $G_2$.
  3. $N_<$ : number of choices of picking less elements from $G_1$ than $G_2$.

  By symmetry, we have $N_< = N_>$. It is clear $$N_= = \begin{cases}0, & k \text{ is odd }\\ \binom{2^{n-1}}{k/2}^2, & k \text{ is even} \end{cases}$$ By $\mathcal{S}_{n-1}$, $\binom{2^{n-1}}{k/2}$ is even when $k$ is even. This leads to $$\binom{2^n}{k} = N_> + N_= + N_< = 2N_> + N_= \equiv 0 + 0^2 = 0 \pmod 2$$ and hence $\mathcal{S}_{n-1} \implies \mathcal{S}_n$.

By principle of induction, $\mathcal{S}_n$ is true for all $n \ge 1$. ie. for all $1 \le k < 2^n$, $\binom{2^n}{k}$ is even.

Answer 3

We can do this in a different way. In fact, I've always loved the Pascal's triangle because I've found combinatorics easier to do with the Pascal's triangle, so I'll use Pascal paths for the proof.

Out interpretation is based on the fact that if we consider a triangle of dots with $n$ dots in the $n$th row and with the notation $(n-1,k-1)$ denoting the $k$th dot from the left in the $n$th row , then $\binom{n}{k}$ is the number of ways in which we can travel using either diagonal left or diagonal right moves from $(0,0)$ to $(n,k)$. This is also the usual Pascal interpretation.

---

Suppose , by induction, that $\binom{2^{n-1}}{k}$ is even for all $1\leq k \leq 2^{n-1}-1$.

Consider the set of all paths that travel from $(0,0)$ from $(2^n,k)$ travelling downward either left or right each time. We break, vertically, the path into $2^{n-1}$ pieces (or subpaths) of length $2$ each starting from top to bottom. That is, for example, if a path looks like $$(0,0) \to (1,1) \to (2,2) \to (3,3)\to(4,3) \to (5,3) \to (6,4) \to (7,4) \to (8,4)$$ then we break it into the four parts $$ (0,0) \to (1,1) \to (2,2) \\ (2,2) \to (3,3)\to(4,3) \\ (4,3) \to (5,3) \to (6,4) \\ (6,4) \to (7,4) \to (8,4) $$

Now, any piece from $(n,k)$ to $(n+2,l)$ can have only the following patterns :

• $l=k$ and the path is $(n,k) \to (n+1,k) \to (n+2,k)$. We call this an $LL$ piece.

• $l=k+2$ and the path is $(n,k) \to (n+1,k+1) \to (n+2,k+2)$. We call this an $RR$ piece.

• $l=k+1$ and the path is either $(n,k) \to (n+1,k+1) \to (n+2,k+1)$ or $(n,k) \to (n+1,k) \to (n+2,k+1)$. We call these an RL and an LR piece respectively.

Now, let $S$ be the subset of all paths from $(0,0)$ to $(2^n,k)$ which contain at least one piece of length $2$ which is LR or RL. Then $S$ is even : because if you consider a path with at least one piece of length $2$ that is LR or RL, then you can consider another path which is identical to the previous path except that all RL pieces are changed to LR pieces, and all LR pieces are changed to RL pieces. This is a bijection with itself as an inverse on $S$ and furthermore, no element of $S$ goes to itself. Thus, $S$ is the union of some set and its image under this bijection, which makes $S$ even.

What about paths which are not in $S$? Every piece of such a path is either LL or RR. The first thing to observe is that $k$ must be even (why? Consider the difference between the two coordinates as you travel down the path) but you can then see, nicely enough, that paths not in $S$ are in fact in bijection with paths from $(0,0)$ to $(2^{n-1},k/2)$, because you can treat each LL piece as just an ordinary L step, and likewise any RR piece as an ordinary R step in the usual grid : this "zooming out by $2$" proves that the set of paths not in $S$ are also even in number.

Note : We used the fact that $1 \leq k \leq 2^n-1$ for paths not in $S$, since those belonging in $S$ will always be subject to the rule mentioned. The point is that if $k=0$ then $k/2 = 0$ so the induction hypothesis fails, and if $k=2^n$ then $k/2 = 2^{n-1}$ and the hypothesis fails again, so I made sure I used the hypothesis well!

---

Hence, we conclude. I assume that the Pascal argument will generalize : essentially speaking, if I take $(2r,s)$ instead of $(2^n,k)$, then removing all paths in $S$, which will continue to be even since I didn't use anywhere the nature of $2^n$ over there, leaves me with nothing if $s$ is odd (which means that $\binom{2r}{s}$ is even for all $r,s$, a nice result) and otherwise leaves me with $\binom{r/2}{s/2}$ if $s$ is even. Thus, we conclude that if $s$ is even, then$$ \binom{2r}{s} \equiv \binom{r}{s/2} \pmod{2} $$

and if $s$ is odd then $$ \binom{2r}s \equiv 0 \pmod{2} $$

using out logic. You might want to divide into pieces of length $3$, $4$ etc. rather than $2$ and find out what kind of conditions and bijections are available there and see how divisibility conditions can be obtained there.

Answer 4

I am trying to prove hat $\binom{2^n}{k}$ is even for every $n\geq 1$ and $1\leq k \leq 2^n-1$.

Assumed that it is intended that $n,k \in \Bbb{Z}.$

Alternative (direct) approach that uses Legendre's Formula. While less elegant than other approaches, this approach provides a nice fail-safe, if elegance eludes you.

---

For $p$ prime, and $n \in \Bbb{Z_{\geq 2}},~$ let $~V_p(n)~$ denote the largest non-negative integer $~\alpha~$ such that $~p^\alpha ~| ~(n!)$.

For $r \in \Bbb{R}$, let $\lfloor r\rfloor$ denote the largest integer $k$ such that $k \leq r.$
That is, $\lfloor r\rfloor$ is the floor of $r$.

---

Preliminary result

(1)
Given: $~\displaystyle a,b,c \in \Bbb{Z^+}, ~\left\lfloor \frac{a}{c} \right\rfloor ~+ ~\left\lfloor \frac{b}{c} \right\rfloor ~\leq ~\left\lfloor \frac{a + b}{c} \right\rfloor.$
Proof:
Denote $\displaystyle ~\left(\frac{a}{c}\right) ~\text{as} ~P_1 + r_1, ~~~\text{and} ~~~ ~\left(\frac{b}{c}\right) ~\text{as} ~P_2 + r_2$
where $~P_1, P_2 \in \Bbb{Z}, ~0 \leq r_1, r_2 < 1.$

Then, $~\displaystyle ~\left\lfloor \frac{a}{c} \right\rfloor ~+ ~\left\lfloor \frac{b}{c} \right\rfloor = P_1 + P_2.$

$\underline{\text{Case 1:} ~~0 \leq (r_1 + r_2) < 1}.$

Then $\displaystyle ~\left\lfloor \frac{a + b}{c} \right\rfloor = P_1 + P_2.$

$\underline{\text{Case 2:} ~~1 \leq (r_1 + r_2) < 2}.$

Then $\displaystyle ~\left\lfloor \frac{a + b}{c} \right\rfloor = P_1 + P_2 + 1.$

---

Per Legendre's formula,
$\displaystyle V_p(n) = \sum_{i=1}^\infty \left\lfloor \frac{n}{p^i}\right\rfloor. $
It is understood that the start of the summation consists of a finite number of non-zero terms, and that all of the remaining terms in the summation are $= (0)$.

For $\displaystyle 1 \leq k \leq 2^n - 1, ~\binom{2^n}{k} = \frac{\left(2^n\right)!}{k!\left[\left(2^n\right) - k\right]!}.$

$$\displaystyle V_2\left(2^n\right) = \sum_{i=1}^{n-1} \left\lfloor \frac{2^n}{2^i}\right\rfloor ~~+ ~~\left\lfloor \frac{2^n}{2^n}\right\rfloor. \tag{A}$$

$$\displaystyle V_2\left(k\right) = \sum_{i=1}^{n-1} \left\lfloor \frac{k}{2^i}\right\rfloor ~~+ ~~\left\lfloor \frac{k}{2^n}\right\rfloor. \tag{B}$$

$$\displaystyle V_2\left(2^n - k\right) = \sum_{i=1}^{n-1} \left\lfloor \frac{2^n - k}{2^i}\right\rfloor ~~+ ~~\left\lfloor \frac{2^n - k}{2^n}\right\rfloor. \tag{C}$$

Since $k < 2^n~~~$ and $~~~\left(2^n - k\right) < 2^n$
the right hand terms in (B) and (C) above are both $= 0$,
while the right hand term in (A) $= 1.$

For each of the other $(n-1)$ terms in the summations of (A), (B), and (C)
you can invoke Preliminary Result (1) above.

That is:

$\displaystyle \left\lfloor \frac{2^n}{2^1} \right\rfloor ~\geq ~\left\lfloor \frac{k}{2^1} \right\rfloor ~+ ~\left\lfloor \frac{2^n - k}{2^1} \right\rfloor.$

$\displaystyle \left\lfloor \frac{2^n}{2^2} \right\rfloor ~\geq ~\left\lfloor \frac{k}{2^2} \right\rfloor ~+ ~\left\lfloor \frac{2^n - k}{2^2} \right\rfloor.$

$\cdots$

$\displaystyle \left\lfloor \frac{2^n}{2^{(n-1)}} \right\rfloor ~\geq ~\left\lfloor \frac{k}{2^{(n-1)}} \right\rfloor ~+ ~\left\lfloor \frac{2^n - k}{2^{(n-1)}} \right\rfloor.$

Therefore, the summation of $(n-1)$ terms in (A) is $\geq$ the corresponding combined summations in (B) and (C) above.

Therefore,

$$ V_2\left(2^n\right) > V_2\left(k\right) + V_2\left(2^n - k\right).$$

---

Addendum
As a corrollary to this answer's analysis, you can immediately conclude that

$$2^1 ~| ~\binom{2^n}{2^{[n-1]}}~~~\text{and} ~~~2^2 ~\not| ~\binom{2^n}{2^{[n-1]}}.$$

This follows, per examination of (A), (B), and (C) in the answer by noting that when $~c|a~$ and $~c|b~$ then

$$\left\lfloor \frac{a}{c} \right\rfloor + \left\lfloor \frac{b}{c} \right\rfloor = \left(\frac{a}{c} + \frac{b}{c}\right) = \left(\frac{a + b}{c}\right) = \left\lfloor \frac{a + b}{c} \right\rfloor.$$