1
$\begingroup$

The part I'm having trouble with specifically is how/why does the sum $$\sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^i}\right\rfloor$$ give the greatest power of $p$ for which $n!$ is divisible. How is counting the multiples of $p$, $p^2$, $p^3$,... in $n$ related to $n!$ in such a way that when you sum up all of those you get the greatest power of $p$ that divides $n!$.

Also how would an inductive proof of the Legendre's formula look like? I've tried proving it specifically for $p=2$ and I took my IH to be $$v_2(n!)=\sum_{i=1}^{\infty}\left\lfloor\frac{n}{2^i}\right\rfloor$$ but I can't seem to extend this for $n+1$.

$\endgroup$
3
  • $\begingroup$ There is an induction proof provided here, but I can't quite understand what is the IH and how does this prove the validity of the statement for $n+1$ ? $\endgroup$
    – bonehead
    Nov 22, 2016 at 12:51
  • $\begingroup$ Did you take a look at the accepted answer here: math.stackexchange.com/questions/141196/… ? $\endgroup$
    – StubbornAtom
    Nov 22, 2016 at 13:18
  • $\begingroup$ @StubbornAtom I did though I still couldn't really understand the connection. I guess that my confusion arises from not understanding how does $$\left \lfloor\frac{N}{p^i}\right\rfloor$$ counts terms that are multiples of p less than $N$, and how do they contribute to $N!$ rather than to $N$ itself. $\endgroup$
    – bonehead
    Nov 22, 2016 at 13:23

2 Answers 2

Reset to default
2
$\begingroup$

The induction in the answer here (which you are presumably referring to, seeing your comment on it) is different than you would expect. Normally you would show that the formula holds for $1$ (or some other anchor) and then show that $φ(n+1)$ follows from $φ(n)$, thus creating a chain of inductions like

1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ ...

The validity of $φ(1)$ thus extends to any $n$.

In the case of the Legendre formula this is different: you prove $φ(n)$ using $φ(\lfloor n/2\rfloor)$ instead of using $φ(n-1)$. Or you can say that from the hypothesis of $φ(m)$ you derive the validity of $φ(2m)$ and also $φ(2m+1)$ because that has the same result of $\lfloor\circ/2\rfloor$.

So the pattern looks more like

            4
      2 ⇒ { 5
1 ⇒ {
      3 ⇒ { 6
            7 etc.

and covers all $n$ in a different, yet fully justified, fashion.

It's analogous with higher primes.

$\endgroup$
3
  • $\begingroup$ So cool. I'm guessing that this is possible because of nature of the floor function since in its case $\phi(2rn)$=$\phi(2rn+1)$ ? $\endgroup$
    – bonehead
    Nov 22, 2016 at 13:08
  • 1
    $\begingroup$ Almost: I meant to say that (yes, because the nature of the floor function) $\lfloor(2m)/2\rfloor = \lfloor(2m+1)/2\rfloor$ so $\phi(2m)$ and $\phi(2m+1)$ (different) follow both from the same IH. $\endgroup$
    – The Vee
    Nov 22, 2016 at 13:10
  • 1
    $\begingroup$ Btw. I used $m$ as in M, there's no need to write it as a product of R N. I suppose it just looked the same in lowercase. $\endgroup$
    – The Vee
    Nov 22, 2016 at 13:11
1
$\begingroup$

Assume $$\nu_p((n-1)!)=\sum_{i=1}^\infty\left\lfloor \frac {n-1}{p^i}\right\rfloor.$$ If $n=p^ku$ with $p\nmid u$ and $k\ge 0$ then we have $ \left\lfloor \frac {n}{p^i}\right\rfloor=\left\lfloor \frac {n-1}{p^i}\right\rfloor+1$ for $k\ge i$ and $ \left\lfloor \frac {n}{p^i}\right\rfloor=\left\lfloor \frac {n-1}{p^i}\right\rfloor$ for $k< i$, hence $$\sum_{i=1}^\infty\left\lfloor \frac {n}{p^i}\right\rfloor =\sum_{i=1}^\infty\left\lfloor \frac {n-1}{p^i}\right\rfloor+\sum_{i=1}^k1=\nu_p((n-1)!)+k=\nu_p((n-1)!)+\nu_p(n)=\nu_p(n!)$$

$\endgroup$

You must log in to answer this question.

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