# Binomial coefficients: how to prove an inequality on the $p$-adic valuation?

In section 4 of the article by Afred van der Poorten's A Proof That Euler Missed ... the following inequality is used:

$$\nu_{p}\displaystyle\binom{n}{m}\leq\left\lfloor\dfrac{\ln n}{\ln p}\right\rfloor-\nu_{p}(m)\qquad(\ast)$$

(In the original denoted $\text{ord}$ $_{p}(\cdot)$ instead of $\nu_p(\cdot)$).

where $\nu_{p}(k)$ is the $p$-adic valuation of $k\in\mathbb{Q}$, i. e. the exponent of the prime $p$ in the prime factorization of $k$. I know some properties of the foor function and that

$$\nu_{p}(a/b)=\nu_{p}(a)-\nu_{p}(b),$$

$$\nu_{p}(a\cdot b)=\nu_{p}(a)\cdot \nu_{p}(b)$$

and

$$\nu_{p}(n!)=\displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{n}{p^{i}}\right\rfloor$$

but I didn't convince myself on the correct argument I should use to prove $(\ast )$.

Question: How can this inequality be proven?

• what is $\ln n$ here? which function is it? Is it usual logarithm? – Why Oct 2 '19 at 11:49
• @M.A.SARKAR $\ln x$ denotes the natural logarithm, also denoted $\log x$. – Américo Tavares Oct 4 '19 at 21:21

Since $\nu_p(n!)=\sum_i\lfloor n/p^i\rfloor$, $\nu_p\binom nm=\sum_i(\lfloor n/p^i\rfloor-\lfloor m/p^i\rfloor-\lfloor (n-m)/p^i\rfloor)$. Observe that each summand is $\le 1$, and for $i>\left\lfloor\frac{\ln n}{\ln p}\right\rfloor$ it's clearly $0$. That gives $v_{p}\binom{n}{m}\le \left\lfloor\frac{\ln n}{\ln p}\right\rfloor$.
Finally observe that for $i\le\nu_p(m)$ $\lfloor m/p^i\rfloor=m/p^i$, so ($\lfloor m/p^i\rfloor+\lfloor x/p^i\rfloor=\lfloor(m+x)/p^i\rfloor$ and) the corresponding summand is also $0$. That gives the inequality in question.
Theorem (Kummer): $\nu_p {n \choose m}$ is the number of carries it takes to add $m$ and $n-m$ in base $p$.
Now note that $\lfloor \frac{\ln n}{\ln p} \rfloor$ is the maximum possible number of carries and the last $\nu_p(m)$ digits of $m$ cannot be associated to any carries.