TAOCP 1.2.5 Exercise 11
Let $\nu_2(m)$ denote the exponent of $2$ in the prime factorization of $m$.
Section 1.2.5: Permutations and Factorials
Exercise 11. [**] [M15] Let the representation of $n$ in the binary system be $n = 2^{e_1}+2^{e_2}+\cdots+2^{e_r}$, where $e_1 > e_2 > \cdots > e_r \ge 0$. Show that $n!$ is divisible by $2^{n-r}$ but not by $2^{n-r+1}$.
x 12. [M22] (A. Legendre, 1808.) Generalizing the result of the previous exercise, let $p$ be a prime number, and let the representation of $n$ in the $p$-ary number system be
$$ n = a_k p^k + a_{k-1}p^{k-1} + \cdots + a_1p + a_0. $$
Express the number $\mu$ of Eq. (8) in a simple formula involving $n$, $p$, and the $a$'s.
Verified: no
Solve time: 34m34s
Let $\nu_2(m)$ denote the exponent of $2$ in the prime factorization of $m$. We must prove that
$$ \nu_2(n!) = n-r, $$
where
$$ n=2^{e_1}+2^{e_2}+\cdots+2^{e_r}, \qquad e_1>e_2>\cdots>e_r\ge 0 $$
is the binary expansion of $n$.
By Legendre’s formula,
$$ \nu_2(n!) = \left\lfloor \frac n2 \right\rfloor + \left\lfloor \frac n{2^2} \right\rfloor + \left\lfloor \frac n{2^3} \right\rfloor +\cdots . $$
Since
$$ n=\sum_{i=1}^r 2^{e_i}, $$
we have
$$ \left\lfloor \frac n{2^k} \right\rfloor = \sum_{i=1}^r \left\lfloor \frac{2^{e_i}}{2^k} \right\rfloor . $$
Now
$$ \left\lfloor \frac{2^{e_i}}{2^k} \right\rfloor = \begin{cases} 2^{e_i-k}, & e_i\ge k,\ 0, & e_i<k. \end{cases} $$
Therefore,
$$ \nu_2(n!) = \sum_{k\ge1}\sum_{i=1}^r \left\lfloor \frac{2^{e_i}}{2^k} \right\rfloor = \sum_{i=1}^r \sum_{k=1}^{e_i} 2^{e_i-k}. $$
For fixed $i$,
$$ \sum_{k=1}^{e_i}2^{e_i-k} = 2^{e_i-1}+2^{e_i-2}+\cdots+1 = 2^{e_i}-1. $$
Hence
$$ \nu_2(n!) = \sum_{i=1}^r (2^{e_i}-1) = \sum_{i=1}^r 2^{e_i} - \sum_{i=1}^r 1 = n-r. $$
Thus the exact power of $2$ dividing $n!$ is $2^{n-r}$, that is,
$$ 2^{,n-r}\mid n! \quad\text{but}\quad 2^{,n-r+1}\nmid n!. $$
This is exactly the required result.