Let \(n\) be a positive integer and set \[ c_n=\binom{2n}{n}. \]
Show that \(c_n\) is even.
Prove that \(c_n\) is divisible by \(4\) if and only if \(n\) is not a power of \(2\).
Solution
For a positive integer \(m\), let \(v_2(m)\) denote the largest integer \(r\) such that \(2^r\) divides \(m\). Write the binary expansion of \(n\) as \[ n=\sum_{j=0}^N\varepsilon_j2^j, \qquad \varepsilon_j\in\{0,1\}, \qquad \varepsilon_N=1. \]
1. For every positive integer \(m\),\[ v_2(m!) = \sum_{r\geq1} \left\lfloor\frac{m}{2^r}\right\rfloor. \]
Each integer in \(\{1,\ldots,m\}\) contributes one factor of \(2\) for each \(r\geq1\) for which it is divisible by \(2^r\). There are exactly \[ \left\lfloor\frac{m}{2^r}\right\rfloor \] multiples of \(2^r\) in this set. Summing these contributions over \(r\) counts every factor of \(2\) in \(m!\) exactly once. Only finitely many terms are nonzero.
2. One has\[ v_2(c_n) = \sum_{j=0}^N\varepsilon_j. \]
2.1. One has\[ v_2(c_n) = \sum_{r\geq1} \left( \left\lfloor\frac{n}{2^{r-1}}\right\rfloor - 2\left\lfloor\frac{n}{2^r}\right\rfloor \right). \]
Since \[ c_n=\frac{(2n)!}{(n!)^2}, \] step 1 gives \[ \begin{aligned} v_2(c_n) &= \sum_{r\geq1} \left( \left\lfloor\frac{2n}{2^r}\right\rfloor - 2\left\lfloor\frac{n}{2^r}\right\rfloor \right)\\ &= \sum_{r\geq1} \left( \left\lfloor\frac{n}{2^{r-1}}\right\rfloor - 2\left\lfloor\frac{n}{2^r}\right\rfloor \right). \end{aligned} \]
2.2. For every \(j\geq0\),\[ \left\lfloor\frac{n}{2^j}\right\rfloor - 2\left\lfloor\frac{n}{2^{j+1}}\right\rfloor = \varepsilon_j. \]
From the binary expansion, \[ \left\lfloor\frac{n}{2^j}\right\rfloor = \varepsilon_j + 2\sum_{k=j+1}^N\varepsilon_k2^{k-j-1}, \] whereas \[ \left\lfloor\frac{n}{2^{j+1}}\right\rfloor = \sum_{k=j+1}^N\varepsilon_k2^{k-j-1}. \] Subtracting twice the second equality from the first gives the claim.
2.3. One has\[ v_2(c_n) = \sum_{j=0}^N\varepsilon_j. \]
In step 1, set \(j=r-1\) and apply step 2 term by term. For \(j>N\), the binary digit \(\varepsilon_j\) is zero, so the resulting sum is exactly \[ \sum_{j=0}^N\varepsilon_j. \]
2.4. Q.E.D.
Step 3 proves the claim of step 2.
3. (a) The coefficient \(c_n\) is even.
Since \(n>0\), its binary expansion has at least one digit equal to \(1\). Thus step 2 gives \[ v_2(c_n)\geq1, \] so \(2\) divides \(c_n\).
4. (b) One has\[ \boxed{ 4\mid c_n \quad\Longleftrightarrow\quad n\text{ is not a power of }2 }. \]
By step 2, \[ 4\mid c_n \quad\Longleftrightarrow\quad v_2(c_n)\geq2 \quad\Longleftrightarrow\quad \sum_{j=0}^N\varepsilon_j\geq2. \] A positive integer has exactly one nonzero binary digit if and only if it is a power of \(2\). Hence the binary digit sum is at least two exactly when \(n\) is not a power of \(2\).
5. Q.E.D.
Step 3 proves part (a), and step 4 proves part (b).