Question about Legendre's Theorem. True or false:
$$
\exists k \in \mathbb{Z} \text { such that } \forall n \in \mathbb{N}, \frac{n !}{2^{n+k}} \in \mathbb{N} .
$$
By intuition, I feel it should be false. Then I tried to prove it by contradiction that assumes it is TRUE for $n$ that :
$$
\frac{n !}{2^{n+k}} = a, a \in \mathbb{N}
$$
So it should be also TRUE for $n+1$ that:
$$
\frac{(n+1) !}{2^{n+k+1}} = b, b \in \mathbb{N}
$$
$$\Rightarrow \frac{n !}{2^{n+k}}\cdot\frac{n+1}{2^{1}}=b$$
$$\Rightarrow a\cdot\frac{n+1}{2}=b$$
$$\Rightarrow \frac{a}{2}\cdot(n+1)=b$$
Then I realize that if $a$ is odd and $n$ is even, $b$ can never be a natural number and I can find the contradiction! And I am working on it right now. But I am wondering that am I on the right track?
 A: Consider the largest $n$ such that $2^n | (2^m)!$
This $n$ is equal to $\sum\limits_{i = 1}^m 2^{m - i} = \sum\limits_{i = 0}^{m - 1} 2^i = 2^m - 1$. This is because we can get one factor of 2 from all the multiples of $2^1$ ($2^{m - 1}$ of those), an additional factor of 2 from all the multiples of $2^2$ ($2^{m - 2}$ of those), an additional factor of 2 from all the multiples of $2^3$ ($2^{m - 3}$ of those), etc.
Therefore, we see that for all $m$, $2^{2^m}$ does not divide $(2^m)!$.
Then in particular, we see that $2^{2^m - m}$ does not divide $(2^m - 1)!$ for all $m$.
So for all $j \in \mathbb{N}$, we see that $\frac{(2^{j + 1} - 1)!}{2^{2^{j + 1} - (j + 1)}} \notin \mathbb{N}$. That is, $\frac{(2^{j + 1} - 1)!}{2^{(2^{j + 1} - 1) - j}} \notin \mathbb{N}$.
Thus, your theorem is proved.
Edit: to be more precise, we see that if there were some $k$ such that for all $n$, $\frac{n!}{2^{k + n}} \in \mathbb{N}$, then clearly it must be the case that $k \leq 0$. For if $k > 0$, then $\frac{0!}{2^{0 + k}} = \frac{1}{2^k} \notin \mathbb{N}$. So write $k = -j$ for some $j \in \mathbb{N}$. Then the above remark proves that $-j$ doesn't work.
A: You might want to consider what powers of 2 occur in $1,\ldots,2^N$ for some $N$. From the multiples of 2 we get $2^{N-1}$, from the multiple of 4 you get another $2^{N-2}$ (because we already counted a factor 2 for these we only need to count another factor 2), the same for higher power of 2.
So we get the 2 a total of
$$ 2^{N-1}+2^{N-2}+\ldots+2^{N-(N-1)}+2^{N-N} = 2^N-1$$ times.
Now, take $n=2^N-1$. Then $n!$ is missing another total of $N$ 2s, so $n!$ has a total of $2^{N}-1 - N$ 2s.
So can there be a $k$ so that $2^N-1-N \geq 2^N-1+k$ for all $N$? well, obviously not. So no matter how small $k$ gets, as soon as $N>-k$ this won’t work.
Test:
Take $k=-6$. We choose $N=7$, then $(2^7-1)!/2^{2^7-1-6} = 22664...75/2$.
