Trouble understanding Legendre's formula and inductive proof of it

Question

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

Answer 1

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.

Answer 2

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