12
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Trevor Gunn Jun 27 '17 at 19:42
  • 1
    $\begingroup$ Don't forget $k=0$ or $k=n$ $\endgroup$ – Bram28 Jun 27 '17 at 19:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Jun 27 '17 at 19:48
  • 1
    $\begingroup$ Hint: $\sum_{k=1}^n \binom{n}{k} = 2^n$, then use induction. $\endgroup$ – flawr Jun 27 '17 at 19:50
14
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Thank you very much! That seems like a very useful fact. $\endgroup$ – as2457 Jun 27 '17 at 20:09
  • 2
    $\begingroup$ 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$. $\endgroup$ – Steven Stadnicki Jun 27 '17 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.