# Is there a direct proof of this lcm identity?

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?

• Can you please give me an elaborate outline of proving the above result using Kummer's Theorem? – crskhr yesterday

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.

• 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
• (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

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)$.

• (btw, Leibnitz harmonic triangle too gives this identity) – Grigory M Aug 7 '10 at 9:25
• 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

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?