2
$\begingroup$

I'm having trouble proving this inequality.

Let $p(m!)$ be the exponent of 2 in the prime factorization of $m!$

Prove that $$ p(m!) \leq m-1 $$

I guessed that $$ p(2^k!) = 2^k-1 $$ but that doesn't help much.

I know that $$p(m)=\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^k}\right\rfloor.$$ The upper bound of $p(m!)$ I get with this formula is too big though.

I think induction is useless here ...

Thanks for your help.

$\endgroup$
1
  • 3
    $\begingroup$ The floor becomes $0$ when $2^k > m$, so $p(m) < \sum\limits_{k=1}^\infty \frac{m}{2^k} = m$. $\endgroup$ Commented Sep 19, 2013 at 18:50

1 Answer 1

1
$\begingroup$

From the floor-formula, observe that $p(m)=\lfloor \frac m2\rfloor + p(\lfloor \frac m2\rfloor)$, so by induction (with $\lfloor \frac m2\rfloor <m$ and after checking the validity for small $m$) you get $p(m)\le \lfloor \frac m2\rfloor+(\lfloor \frac m2\rfloor-1)\le m-1$.

$\endgroup$
1
  • $\begingroup$ I get it, thanks. Check the comment above for a more straightforward and simple proof. $\endgroup$ Commented Sep 19, 2013 at 19:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .