Proof of Legendre's formula by counting multiples of prime powers

Proof

1. Let $p$ be a prime number and $n$ a natural number. If $n = 0$, then $0! = 1$ by the definition of the factorial. So $\nu_p(0!) = 0$, and every term $\lfloor 0 / p^i \rfloor$ is $0$. Assume now $n \ge 1$.
2. We have $n! = 1 \cdot 2 \cdots n$. Applying the valuation of a product $n - 1$ times gives $\nu_p(n!) = \sum_{k=1}^{n} \nu_p(k)$.
3. Let $1 \le k \le n$ and $i \ge 1$. By the definition of the p-adic valuation, $p^i \mid k$ holds if and only if $i \le \nu_p(k)$. Indeed, if $i \le \nu_p(k)$ then $p^i \mid p^{\nu_p(k)} \mid k$, and if $i > \nu_p(k)$ then $p^i \nmid k$ by maximality.
4. So $\nu_p(k)$ is the number of integers $i \ge 1$ with $p^i \mid k$.
5. Substituting step 4 into step 2 and counting the pairs $(k, i)$ the other way gives $\nu_p(n!) = \sum_{i \ge 1} N_i$. Here $N_i$ is the number of $k$ with $1 \le k \le n$ and $p^i \mid k$.
6. Only finitely many $N_i$ are nonzero, because $p^i > n$ implies $N_i = 0$.
7. Fix $i \ge 1$ and let $d = p^i$. The multiples of $d$ in $\set{1, \dots, n}$ are the numbers $jd$ with $j$ an integer and $1 \le j \le n/d$.
8. An integer $j$ satisfies $j \le n/d$ if and only if $j \le \lfloor n/d \rfloor$, by the definition of the floor function. So $N_i = \lfloor n / p^i \rfloor$.
9. Hence $\nu_p(n!) = \sum_{i=1}^{\infty} \lfloor n / p^i \rfloor$, where only finitely many terms are nonzero.