3
$\begingroup$

What is the highest exponent of $2$ dividing $\binom{n}{k}$?

I know that

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

And therefore the highest exponent of $2$ dividing $\binom{n}{k}$ is

$$\sum_{i=1}^{\infty} \left( \lfloor \frac{n}{2^i}\rfloor -\lfloor \frac{k}{2^i}\rfloor-\lfloor \frac{n-k}{2^i}\rfloor \right)$$

I am stuck here!

$\endgroup$
  • 3
    $\begingroup$ en.wikipedia.org/wiki/Kummer%27s_theorem $\endgroup$ – kimchi lover Jul 4 '17 at 14:50
  • $\begingroup$ Do we have an easier statement? How this power changes when we vary $k$ from $1$ to $n$? $\endgroup$ – Deda Jul 4 '17 at 14:52
  • $\begingroup$ Sorry, but your formula is wrong, e.g. test $\binom {2^5} {2^3} $ $= 10518300 = 2^2 \cdot 3^3 \cdot 5^2 \cdot 13 \cdot 29 \cdot 31 $ means: $2 \neq 0=\sum_{i=1}^\infty (2^{5-i}-2^{3-i}-(2^{5-i}-2^{3-i}))$ $\endgroup$ – user90369 Jul 4 '17 at 15:18
2
$\begingroup$

While as pointed out in the comments, this question is answered by Kummer's theorem, another approach that might be useful is as follows:

You can use the standard binomial bounds $\left( \frac{n}{k} \right)^k \leq \binom{n}{k} \leq \left( \frac{en}{k} \right)^k$ to get some easy bounds, by taking base 2 logarithms of these. Then, the highest exponent is lower bounded by $ \log_2 \left( \left( \frac{n}{k} \right)^k \right) $ and upper bounded by $\log_2 \left( \left( \frac{en}{k} \right)^k \right) $.

The bounds in this case are $ k \left( \log_2 n - \log_2 k \right) $ and $k \left( \log_2 e + \log_2 n - \log_2 k \right) $.

These bounds can easily be improved by using Stirling's approximation on the binomial coefficient with more terms retained to get more refined upper and lower bounds. By retaining more terms, if you have an upper bound and lower bound which are within 1 of the same integer, then the integer in the middle is precisely the required power of 2.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Kummer's theorem is amazing! It says that $\dbinom{36}{9}$ has prime factor $2^p$ and $p$ is the number of $carries$ you have to do when adding $36-9=27$ to $9$ in base $2$ enter image description here

And this is true for any other prime factor of $\dbinom{36}{9}=94\,143\,280=2^4\cdot 5\cdot 7\cdot 11 \cdot 17 \cdot 29 \cdot 31$

Actually in base $31$ you have to add $r_{31}+9_{31}=15_{31}$ with only 1 carry.

Amazing. Thank you for making me discover this pearl :)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The formula you used is used to prove Kummer's theorem $\endgroup$ – Raffaele Jul 4 '17 at 17:18
  • $\begingroup$ Your welcome. ${}$ $\endgroup$ – Deda Jul 4 '17 at 19:18
1
$\begingroup$

From Legendre's Theorem

The greatest power of $2$ dividing $n!$ is $2^{n−r}$ where $r$ is the number of $1$s in the binary expansion of $n$.

As a result $n!=2^{n-r_n}\cdot q_n$, $k!=2^{k-r_k}\cdot q_k$ and $(n-k)!=2^{n-k-r_{n-k}}\cdot q_{n-k}$. So $$\frac{n!}{k!(n-k)!}=\frac{2^{n-r_n}q_n}{2^{k-r_k}q_k\cdot 2^{n-k-r_{n-k}}q_{n-k}}=\frac{q_n}{q_kq_{n-k}}\cdot 2^{n-r_n-(k-r_k)-(n-k-r_{n-k})}=\\\frac{q_n}{q_kq_{n-k}}\cdot 2^{r_k+r_{n-k}-r_n}$$

| cite | improve this answer | |
$\endgroup$

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.