Understanding an application of Legendre's Formula as used in the proof of Bertrand's Postulate

Question

In Wikipedia's proof of Bertrand's Postulate, Legendre's Formula is used to establish an upper bound to the p-adic valuation of ${2n}\choose{n}$

The argument is presented as this:

(1) Let $R(p, x)$ be the p-adic order of $x$ so that it is the largest number of $r$ such that $p^r$ divides $x$.

(2) Applying Legendre's Formula: $$R\left(p, {{2n}\choose{n}}\right) = \sum\limits_{j=1}^{\infty}\left(\left\lfloor\frac{2n}{p^j}\right\rfloor - 2\left\lfloor\frac{n}{p^j}\right\rfloor\right)$$

I am not clear on the notation or the meaning of the argument.

Here is the argument:

But each term of the last summation must be either zero (if $n/p^j \bmod 1<1/2$) or one (if $n/p^j\bmod 1\ge1/2$), and all terms with $j>\log_p(2n)$ are zero.

I am not clear why it must be $0$ or $1$.

If I change the binomial coefficient to something else. Let's say ${n^2+2n}\choose{n^2}$ which then becomes:

$$R\left(p, {{n^2+2n}\choose{n^2}}\right) = \sum\limits_{j=1}^{\infty}\left(\left\lfloor\frac{n^2+2n}{p^j}\right\rfloor - \left\lfloor\frac{n^2}{p^j}\right\rfloor - \left\lfloor\frac{2n}{p^j}\right\rfloor\right)$$

How would I determine the possible values for each $p$? In this case is it still $0$ or $1$ or is there now a greater range of possibile integers returned by applying Legendre's Formula.

I am trying to understand how to analyze the results of applying Legendre's Formula to a binomial coefficient so that I can better understand the reasoning used in the proof.

Answer 1

Since you say you’re not clear on the notation: Perhaps the part you’re missing is that $x\bmod1$ is the fractional part of $x$.

It’s still just $0$ or $1$ in your second example. Quite generally, $\lfloor x+y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor$ can only be $0$ or $1$. If you write $x$ and $y$ as sums of integer and fractional parts, $x=i+u$ and $y=j+v$ with $u,v\in[0,1)$, you get

\begin{eqnarray*} \lfloor x+y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor &=& \lfloor i+u+j+v\rfloor-\lfloor i+u\rfloor-\lfloor j+v\rfloor \\ &=& i+j+\lfloor u+v\rfloor-i-j \\ &=& \lfloor u+v\rfloor \end{eqnarray*}

with $0\le u+v\lt2$, and thus $\lfloor u+v\rfloor=0$ or $1$.