Prove that $s_p(n-1)+s_p(n)+1-s_p(2n)\ge v_p(n)\cdot (p-1)$ for $p|n$

elementary-number-theorynumber theory

Prove that $\frac{(2n)!}{n!(n+1)!}$ is an integer.

Now, one way of proving this is $$\frac{(2n+1)!}{n!(n+1)!}=\frac{2n+1}{n}\cdot \frac{(2n)!}{(n-1)!(n+1)}=\frac{2n+1}{n}\cdot \binom{2n-1}{n+1}\in \Bbb Z$$

but $\gcd(n,2n+1)=1\implies n|\binom{2n}{n-1}$


The other possible way I think is using $v_p.$

Let $p$ be an odd prime dividing $n$ then $$v_p\left(\frac{(2n)!}{(n-1)!(n+1)!}\right)=v_p(2n!)-v_p(n-1!)-v_p(n+1!)=\frac{2n-s_p(2n)-n+1+s_p(n-1)-n-1+s_p(n+1!)}{p-1}=\frac{s_p(n-1)+s_p(n+1)-s_p(2n)}{p-1}$$

where $s_p$ denotes the sum of digits of $n$ is base $p$.

Since $p|n\implies s_p(n+1)=s_p(n)+1.$

And it is well known that $p-1|x-s_p(x).$

Now, to show that $n|\left(\frac{(2n)!}{n!(n+1)!}\right)$ enough to show that $$s_p(n-1)+s_p(n)+1-s_p(2n)\ge v_p(n)\cdot (p-1)$$

When $2|n$ note that $v_2(\frac{(2n)!}{n!(n+1)!})=v_2(\frac{(2n+1)!}{n!(n+1)!})=v_2(\binom{2n+1}{n})$

Any idea on how to prove this without using the first proof? Also, this identity is definitely true because of the first proof.

Best Answer

We have the following basic inequality : for all $m,n \geq 0$ , we have $$s_p(m) + s_p(n) \geq s_p(m+n)$$ (with equality if and only if there are no "carries"). This is not particularly difficult to prove in isolation.


Using this, even if $p$ doesn't divide $n$, we can see that the inequality holds. In this case, $v_p(n) = 0$, so all we need to prove is that $s_p(n-1)+s_p(n)+1 \geq s_p(2n)$, but this is clear once you notice that $$ s_p(2n) \leq s_p(n+1)+s_p(n-1) \leq s_p\left(n\right) +s_p(1)+ s_p(n-1) $$ and $s_p(1) = 1$.


We induct on $v_p(n)$ now. Suppose the fact is true for $v_p(n) = k$ with $k \geq 0$. We will assume that $v_p(n) = k+1$ so that $p|n$, and note that \begin{align} &s_p(n-1)+ s_p(n)+1-s_p(2n) \\ &= \left[s_p\left(\frac{n}{p}-1\right) + (p-1)\right]+s_p\left(\frac{n}{p}\right)+1 -s_p\left(\frac{2n}{p}\right)\\ &= (p-1) + \left[s_p\left(\frac{n}{p}-1\right) + s_p\left(\frac np\right) + 1 - s_p\left(\frac{2n}{p}\right)\right]\\ & \geq (p-1) + k(p-1) = (k+1)(p-1) \end{align}

as desired.

Related Question