Proof. We do it by \(\nu_p\)’ing. First, notice that \(\nu_p(\lcm(1,2,\ldots,n+1)) = \left\lfloor \log_p n+1 \right\rfloor.\) Ok, great.

Now, treat \(n=a\cdot p^k-1\) for \(a\perp p\) as a separate case.

For the binomial coefficients we have \[\nu_p( (n+1)(n+0)(n-1)\cdots (n-i+1) ) - \nu_p(i!).\] We can think of this like a game! You get dropped into the natural numbers, and get to walk forward \(i\) steps. You collect \(\nu_p(x)\) points for walking on tile \(x\). How many points can you get compared to someone else who is playing the same game?

Well, it turns out the following fact is useful for analyzing the game:

\[\nu_p(w!) \le \nu_p((n+w)!) - \nu_p(n!).\] In fact, this is an immediate consequence of the inequality: \[\left\lfloor x-y \right\rfloor \le \left\lfloor x \right\rfloor-\left\lfloor y \right\rfloor.\] Because we use the formula: \[\nu_p(n!) = \sum_{i\ge 1} \left\lfloor n/p^i \right\rfloor.\]

So, now that we understand the game, how does the game help? Let’s call the players “top” and “bottom” for numerator and denominator. Well, then once top gets a good point thing, he resets to the start basically, and doesn’t get any further ahead, until bottom also gets the good point thing that top got. So, top is only ever ahead by at most once. And it will be ahead at least once too because just think about it.