Legendre's Formula

**Step 1: Write $v_p(n!)$ as a sum over the factors.** By definition $n! = 1\cdot 2\cdots n$, so $v_p(n!) = \sum_{k=1}^{n} v_p(k)$, the sum of the $p$-adic valuation of every integer from $1$ to $n$.

**Step 2: Rewrite each $v_p(k)$ as a count.** For each $k$, $v_p(k) = \sum_{i=1}^{\infty} [p^i \mid k]$ (using Iverson bracket notation, $1$ if true, $0$ if false), since $k$ is divisible by $p^i$ for exactly $v_p(k)$ values of $i$ (namely $i=1,\dots,v_p(k)$).

Step 3: Swap the order of summation. Substituting, $v_p(n!) = \sum_{k=1}^n \sum_{i=1}^{\infty} [p^i \mid k] = \sum_{i=1}^{\infty} \sum_{k=1}^n [p^i \mid k]$, exchanging the (finite, so justified) double sum.

**Step 4: Count multiples of $p^i$ directly.** The inner sum $\sum_{k=1}^n [p^i \mid k]$ counts how many integers from $1$ to $n$ are multiples of $p^i$, which is exactly $\left\lfloor \frac{n}{p^i} \right\rfloor$ (the multiples are $p^i, 2p^i, \dots, \lfloor n/p^i\rfloor \cdot p^i$).

Step 5: Conclude. Substituting back, $v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$, which is finite since $\lfloor n/p^i \rfloor = 0$ once $p^i > n$, completing the proof.