Proving $n!$ is never divisible by $2^n$ The problem wants me to prove by induction that $n!\neq2^nk$ for every $n$ in $N$. First of all, I've been usually doing proofs where I show something is true, so now I'm a bit confused since I do not know do I apply the same approach (base case, assumption, show for $n+1$) or do I perhaps show the base case, assume that it does hold, and then show that that assumption leads to some contradiction for $n+1$ ?  
I've tried the following. Showed that for $n=1\Rightarrow2\neq4k$. Assuming it holds for $n$ I tried to prove for $n+1$, $$(n+1)!\neq2^{n+1}k\Rightarrow(n+1)n!\neq2^n\cdot2k$$ Now I should probably use the IH somehow but I'm not sure how.
 A: By Legendre's formula,
$$\nu_2(n!)=\sum_{k=1}^\infty{\left\lfloor\frac n{2^k}\right\rfloor}.$$
But 
$$\sum_{k=1}^\infty{\left\lfloor\frac n{2^k}\right\rfloor}<\sum_{k=1}^\infty\frac n{2^k}=n.$$
The strict inequality is justified by the fact that all the terms with $2^k>n$ are missing.

Note that the "worst case" is when $n$ is a power of $2$: then $n!$ is divisible by $2^{n-1}$.

Induction:
The development of $n!$ has $\lfloor n/2\rfloor$ even factors. If you discard the odd factors and divide all even ones by $2$, you end-up with the development of $\lfloor n/2\rfloor$!
Hence 
$$
 \nu_2(n!)=\left\lfloor\frac n{2}\right\rfloor+
\nu_2\left(\left\lfloor\frac n{2}\right\rfloor !\right)$$
 giving Legendre's formula by induction. (Also using $\lfloor\lfloor n/2^k\rfloor/2\rfloor=\lfloor n/2^{k+1}\rfloor$.)
A: Let $y=f(x)$ be the largest integer y such that $2^y$ divides x.
If $k\le2^m$ then $f(k)=f(2^m+k)$ which implies $f(k!)=f(\frac{(2^m+k)!}{2^m!})$
So if you've proven that $f(k!)<2^k$ for all $k\le 2^m$ then $f((2^m+k)!)=f(2^m!)f(k!)<2^{2^m}2^k=2^{2^m+k}$ so you prove it also for m+1
A: The underlying issue is brought to light by noting the following:
(2n)! $\;$=$\;$ (2q+1)[$2\cdot 4\cdot 6\cdot \cdots (2n-4) \cdot (2n-2)\cdot 2n$] $\;$=$\;$ $2^n \cdot$ n! (2q+1)
(2n+1)! = (2n+1)(2n)! = $2^n\cdot$ n! (2q+1)(2n+1) = $2^n\cdot$ n! (2p+1)
n! $\;=\:\; 2^{k_n}$ (2m+1)
$k_1 = 0, \;k_2 = 1, \; k_3 = 1; \; k_4 = 3 \;\;$ ($k_n<n \;\;$all by trivial inspection)
A proof by induction then follows easily.
