28
$\begingroup$

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?

3 Answers 3

22

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.

  • 0
    Beautiful! I have to admit I was really not expecting the answer to this question to be "yes."2010-08-05
  • 1
    (I must confess, most of the credit goes to a friend of mine.)2010-08-06
  • 0
    "...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?2011-08-21
  • 0
    @Mark induction by row number2011-08-21
7

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

  • 0
    (btw, Leibnitz harmonic triangle too gives this identity)2010-08-07
  • 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.2010-08-07
  • 0
    @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)2010-08-07
0

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?