Prove that $2^n$ does not divide $n!$ I want to prove that $2^n$ does not divide $n!$.
I was trying by induction and I'm confused about if what I'm doing is right.
First I test it with $n=1$. In fact:
$$2^1 \nmid 1!$$
So if i take the I.H. as $2^n \nmid n!$ and I try to prove it for $n+1$:
$$2^{n+1} \nmid (n+1)!$$
$$2^{n} \cdot 2 \nmid (n+1) \cdot n!$$
As  $2^n \nmid n!$ it must be that $2^n$ divides $n+1$, so I need to prove that it doesn't. If I try by induction again I must have $n>1$ for it to be true:
$$P(n) = 2^n \nmid n+1$$
$$P(n+1) = 2^n \cdot 2 \nmid n+1+1$$
but $2^n \nmid n+1$ and $2^n \nmid 1$
because $n>1$
So my question is obviously if this is correct. I'm doubting because the exception I have to do with $n$ being greater than 1 for the second part. If I made a mistake could you point to me in a better direction? I'm sure there must be a simpler way to prove this.
Thanks!
 A: The maximal power of $2$ which divides $n!$ is $$v_2(n!)=\lfloor \frac n2 \rfloor+\lfloor \frac n4 \rfloor +\cdots=\sum_{i=1}^{\infty} \lfloor\frac n{2^i}\rfloor$$
We bound this from above by dropping the floor function to see that $$v_2(n!)<n\sum_{i=1}^{\infty} \frac 1{2^i}=n$$
A: By Legendre's theorem
$$\nu_2(n!) = \sum_{m\geq 1}\left\lfloor\frac{n}{2^m}\right\rfloor\leq \sum_{m\geq 1}\frac{n}{2^m}=n. $$
Equality may hold only if $2^k\parallel n$, but in such a case the $(k+1)$-th terms of the central sums fullfill a strict inequality.
A: The mistake in your work is the conclusion that if $2^n | j * k$, then either $2^n | j$ or $2^n | k$. For instance, consider that 8 divides $12*6 = 72$ but neither 12 or 6 is divisible by 8.
A: A proof by induction
will be difficult
because, as $n$ increments,
$2^n$ adds one factor of $2$
while $n!$ can add many.
The way I would do it
is use
Legendre's theorem,
stated here, for example:
http://www.cut-the-knot.org/blue/LegendresTheorem.shtml
If $p$ is a prime,
and
$v_p(n!)$
is the exponent of
the greatest power of $p$
dividing $n!$,
so
$p^{v_p(n!)} \mid n!$
and
$p^{v_p(n!)+1} \not\mid n!$,
then
$v_p(n!)
=\sum_{k=1}^{\lfloor \log_p n \rfloor} \lfloor \dfrac{n}{p^k} \rfloor
$.
It follows that
$\begin{array}\\
v_p(n!)
&=\sum_{k=1}^{\lfloor \log_p n \rfloor} \lfloor \dfrac{n}{p^k} \rfloor\\
&\le\sum_{k=1}^{\lfloor \log_p n \rfloor}  \dfrac{n}{p^k} \\
&=n\sum_{k=1}^{\lfloor \log_p n \rfloor}  \dfrac{1}{p^k} \\
&<n\sum_{k=1}^{\infty}  \dfrac{1}{p^k} 
\qquad\text{(here is where we get a strict inequality)}\\
&=n\dfrac{\frac1{p}}{1-\frac1{p}}\\
&=\dfrac{n}{p-1}\\
\end{array}
$
In particular,
for $p=2$,
$v_2(n!)
< n
$,
so
$2^n
\not\mid n!
$.
Note that if
$n=p^m$
for some integer $m$,
then
$\begin{array}\\
v_p(n!)
&=v_p((p^m)!)\\
&=n\sum_{k=1}^{\lfloor \log_p n \rfloor}  \dfrac{1}{p^k}\\
&=n\sum_{k=1}^{m}  \dfrac{1}{p^k}\\
&=p^m\dfrac{\frac1{p}-\frac1{p^{m+1}}}{1-\frac1{p}}\\
&=p^m\dfrac{1-\frac1{p^{m}}}{p-1}\\
&=\dfrac{p^m-1}{p-1}\\
\end{array}
$ 
If $p=2$,
$v_2((2^m)!)
=2^m-1
$,
so this misses by just $1$,
so that
$2^{2^m-1} \mid (2^m)!$
and
$2^{2^m} \not\mid (2^m)!$.
A: As pointed out in the other answers we can write the maximum power of $2$ that divides $n!$ as $\nu_2(n!) = \sum_{k\geq 0}\left\lfloor\frac{n}{2^k}\right\rfloor$. We can give a simple interpretation of this number by working in binary. The binary expansion of $n$ is $n = \sum_{k\geq 0} a_k 2^k$ with $a_k\in\{0,1\}$. Using this we find
$$\matrix{\nu_2(n!) &=& \sum_{k\geq 0}\left\lfloor\sum_{i\geq 0} a_i 2^{i-k}\right\rfloor \\= \sum_{k\geq 0}\sum_{i\geq k} a_i 2^{i-k} &=& \sum_{k\geq 0} a_k(1+2+4+\ldots + 2^{k-1}) \\= \sum_{k\geq 0} a_k(2^k-1) &=& n - \sum_{k\geq 0} a_k}$$
Thus 
$$\nu_2(n!) = n - s_2(n)$$
where $s_2(n)$ is the sum of the binary digits of $n$. If $n>0$ then the binary expansion of $n$ must contain atleast one "$1$" so $\nu_2(n!) < n$ follows. The minimum value of $s_2(n)$ for $n>0$ occurs if $n$ is on the form $2^k$ for which $s_2(n) = 1$ and $v_2(n!) = n-1$.
