Prove that $n!$ is not divisible by $2^n$

Question

Let $n$ be a natural number. Prove that $n!$ is not divisible by $2^n$.

Please let me know this proof.

Answer 1

Let $v_2(n!)$ be the order to which $2$ divides $n!$ (so $v_2(6!)=4$ for example).

Legendre tells us that $$v_2(n!)=\sum_{i=1}^{\infty} \Bigg \lfloor \frac n{2^i}\Bigg \rfloor$$ But for $n>0$ we then deduce $$v_2(n!)<\sum_{i=1}^{\infty} \frac n{2^i}=n\sum_{i=1}^{\infty} \frac 1{2^i}=n$$

And we are done.

Answer 2

If the statement does not hold then there exists the smallest positive integer $n$ such that $2^n$ divides $n!$. Since $2^1$ does not divide $1!$, then $n>1$. Now let $m=\lfloor n/2\rfloor\geq 1$. We have that $$n!=(\text{odd factors})\cdot 2m\cdot (2m-2)\cdots 4\cdot 2=(\text{odd factors})\cdot2^{m}\cdot m!$$ which implies that $2^{n-m}$ divides $m!$. This is a contradiction! Why?

Answer 3

We can count how many 2 factors are in $n!$. We know there are $\frac{n}{2}$ two factors, in addition, more $\frac{n}{4}$ two factors(from the numbers divisible by 4) and so on. So the number of all two factors is: $N=\frac{n}{2}+\frac{n}{4}+\dots+\frac{n}{2^k}$, where $2^{k+1} >n$. So if $2^n|n!$, then $N>n$, so $\frac{n}{2}+\frac{n}{4}+\dots+\frac{n}{2^k} > n$, after simplification: $\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^k} > 1$. We know that, if $k$ goes towards to the infinity, then $\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^k} = 1$, but it never will be greater than $n$.

Of course $N= \lfloor\frac{n}{2}\rfloor+\lfloor\frac{n}{4}\rfloor+\dots+\lfloor\frac{n}{2^k}\rfloor$ but it doesn't matter in this case. It would be unnecessary addition.