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