Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 proved?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
Thanks! Very simple your explanation. –  Américo Tavares Aug 19 '10 at 14:00
add comment

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.

Kummer's theorem itself is not hard to prove; it more or less follows from the last identity you list.

share|improve this answer
    
Thanks as well! To follow your proof I feel I need to learn more advanced concepts. I will try to do so. –  Américo Tavares Aug 19 '10 at 20:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.