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$.

-

2 Answers

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}$.

-
I don't understand ($\Rightarrow$)? –  misi10 Dec 1 '12 at 20:16

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$$

-
this formula is unknown for me? and then? –  misi10 Nov 30 '12 at 15:44
This is sometimes known as De Polignac's formula but is also attributed to Legendre. –  lhf Nov 30 '12 at 16:02
i can not continue,give me more hint. –  misi10 Nov 30 '12 at 18:47
Hagen, math.stackexchange.com/questions/141196/… and many other MSE questions. –  Will Jagy Nov 30 '12 at 19:56
There is also some recent thing for posting fixed, easily searchable quality answers to questions, or parts of questions, that come up over and over and over again. I re-posted my little induction proof there but i do not recall how to find it. Certainly, if some fact is necessary for 100 different questions (this probably qualifies), a post with a few correct proofs seems worthwhile. –  Will Jagy Nov 30 '12 at 20:05