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.

The identity

$\displaystyle (n+1) \text{lcm} \left( {n \choose 0}, {n \choose 1}, ... {n \choose n} \right) = \text{lcm}(1, 2, ... n+1)$

is probably not well-known. The only way I know how to prove it is by using Kummer's theorem that the power of $p$ dividing ${a+b \choose a}$ is the number of carries needed to add $a$ and $b$ in base $p$. Is there a more direct proof, e.g. by showing that each side divides the other?

share|improve this question

3 Answers 3

up vote 15 down vote accepted

Consider Leibniz harmonic triangle — a table that is like «Pascal triangle reversed»: on it's sides lie numbers $\frac{1}{n}$ and each number is the sum of two beneath it (see the picture).

One can easily proove by induction that m-th number in n-th row of Leibniz triangle is $\frac{1}{(n+1)\binom{n}{m}}$. So LHS of our identity is just lcd of fractions in n-th row of the triangle.

But it's not hard to see that any such number is an integer linear combination of fractions on triangle's sides (i.e. $1/1,1/2,\dots,1/n$) — and vice versa. So LHS is equal to $lcd(1/1,\dots,1/n)$ — and that is exactly RHS.

share|improve this answer
    
Beautiful! I have to admit I was really not expecting the answer to this question to be "yes." –  Qiaochu Yuan Aug 5 '10 at 19:55
1  
(I must confess, most of the credit goes to a friend of mine.) –  Grigory M Aug 6 '10 at 12:29
    
"...it's not hard to see that any such number is an integer linear combination of fractions on triangle's sides... " How do I show this? –  Mark Aug 21 '11 at 1:15
    
@Mark induction by row number –  Grigory M Aug 21 '11 at 8:15

It will need something clever. For n + 1 = 6, you need 6 times the lcm of 1 5 and 10 in order to get enough powers of 2 ( and 3 ). Is there a characterization of those n + 1 where the entire factor of n + 1 is needed, and not the lcm, for the left hand side?

share|improve this answer

More generally, for $0 \leq k \leq n$, there is an identity

$(n+1) {\rm lcm} ({n \choose 0}, {n \choose 1}, \dots {n \choose k}) = {\rm lcm} (n+1,n,n-1, \dots n+1-k)$.

This is simply the fact that any integer linear combination of $f(x), \Delta f(x), \Delta^2 f(x), \dots \Delta^k f(x)$ is an integer linear combination of $f(x), f(x-1), f(x-2), \dots f(x-k)$ where $\Delta$ is the difference operator, $f(x) = 1/x$, and $x = (n+1)$.

share|improve this answer
    
(btw, Leibnitz harmonic triangle too gives this identity) –  Grigory M Aug 7 '10 at 9:25
2  
That's correct, but the use of absolute values in the Leibniz triangle and its specialized definition somewhat obscures the generic, linear nature of the identity. –  T.. Aug 7 '10 at 9:43
    
@T: well, have to agree with you (but the fact that one needs 1/x to count lcm of binomial coefficients still seems somewhat mysterious to me, btw) –  Grigory M Aug 7 '10 at 9:49

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.