Highest exponent of $2$ dividing $\binom{n}{k}$ 
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!
 A: 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. 
A: 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}$$
A: 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$

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 :)
