# Binomial coefficients that are powers of 2

I would like a proof that $${{n}\choose{k}} = \frac{n!}{k!(n-k)!} = 2^m$$ for $n,k,m\in \mathbb{N}$, only if $k=1$ or $k=n-1$.

It seems to me that this must be true since for other values of $k$ the numerator contains more factors that are not powers of 2 than the denominator. Furthermore, the numerator also contains larger factors than the denominator and thus can't all be cancelled. Nevertheless, I have been unable to form an elegant, watertight proof.

• Kummer's Theorem says that $v_p\left( \binom{a + b}{a} \right)$ is the number of carries required to compute $a + b$ in base $p$. So this is equivalent to if $a, b \ge 2$ then $a + b$ requires a carry in base $p$ for some prime $p \ne 2$. I don't know if this helps. – Trevor Gunn Jun 27 '17 at 19:42
• Don't forget $k=0$ or $k=n$ – Bram28 Jun 27 '17 at 19:48
• According to the Wolfram page on Binomial Coefficients, mathworld.wolfram.com/BinomialCoefficient.html, Erdős (of course) proved that 'doubly interior' coefficients (those with $3\leq k\leq n-3$) are never powers of an integer except for ${50\choose 3}=140^2$, and it's easy to prove that $n\choose 2$ can never be a power of two for $n\geq 3$, so the statement is certainly true - but it feels like there should be a much more elementary proof for this case. – Steven Stadnicki Jun 27 '17 at 19:48
• Hint: $\sum_{k=1}^n \binom{n}{k} = 2^n$, then use induction. – flawr Jun 27 '17 at 19:50

Betrand's Postulate implies that for $n \ge 1$ there is always a prime $p$ with $n < p \le 2n$.

Sylvester strengthened this result to:

If $n \ge 2k$ then at least one of the numbers $n, n - 1, n - 2, \cdots, n - k + 1$ has a prime divisor $p > k$.

Hence if $n \ge 2k$, which we can always assume since $\displaystyle \binom{n}{k} = \binom{n}{n - k}$, then

$$\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}$$

has a prime $p$ in the numerator with $p > k$. Hence $p \mid \binom{n}{k}$. Since we are assuming $k, n - k \ge 2$ this shows that $\binom{n}{k}$ is not a power of $2$.

Reference

M. Aigner Proofs from THE BOOK, Springer (2014), 5th ed. (Ch. 2, 3)

• Thank you very much! That seems like a very useful fact. – as2457 Jun 27 '17 at 20:09
• Note that this also proves 'half of' the Erdős result I mentioned in the comments: $n\choose k$ can never be a power of any number $d\leq k$. – Steven Stadnicki Jun 27 '17 at 22:17