Proof : $2^{n-1}\mid n!$ if and only if $n$ is a power of $2$. I want to prove that:
$2^{n-1}\mid n!$ if and only if $n$ is a power of $2$. 
 A: Hint: It is well-known(?) that the maximal $k$ with $p^k|n!$ is given by
$$k=\left\lfloor \frac{n}{p}\right\rfloor+\left\lfloor \frac{n}{p^2}\right\rfloor+\left\lfloor \frac{n}{p^3}\right\rfloor+\ldots$$
A: write out n! and consider how many times each divides by 2 for example 16:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 = 16!
  ^   ^   ^   ^   ^     ^     ^     ^    divisible by 2
      ^       ^         ^           ^    divisible by 2^2
              ^                     ^    divisible by 2^3
                                    ^    divisible by 2^4

so there are $16/2 = 8$ numbers there divisible by 2. $16/4 = 4$ numbers there divisible by 2^2. etc.
in total then, there are 16/2 + 16/2^2 + 16/2^3 + 16/2^4.
In general if 2^r is the highest power of 2 dividing n! then $r = \sum_{i=1} [n/2^i]$.

To show that $2^{n-1}\mid n!$ we thus want to prove $n-1 = \sum_{i=1} [n/2^i]$ iff $n = 2^k$. ($\Leftarrow$) is immediate from computation. For ($\Rightarrow$) Let $2^{k-1} < n < 2^k$ but then $r < n - 1$ by comparing each term of the summation for $n$ and the one for $2^{k}$.
