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

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}