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?

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

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.

$\endgroup$
  • $\begingroup$ Beautiful! I have to admit I was really not expecting the answer to this question to be "yes." $\endgroup$ – Qiaochu Yuan Aug 5 '10 at 19:55
  • 1
    $\begingroup$ (I must confess, most of the credit goes to a friend of mine.) $\endgroup$ – Grigory M Aug 6 '10 at 12:29
  • $\begingroup$ "...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? $\endgroup$ – Mark Aug 21 '11 at 1:15
  • $\begingroup$ @Mark induction by row number $\endgroup$ – Grigory M Aug 21 '11 at 8:15
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (btw, Leibnitz harmonic triangle too gives this identity) $\endgroup$ – Grigory M Aug 7 '10 at 9:25
  • 2
    $\begingroup$ 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. $\endgroup$ – T.. Aug 7 '10 at 9:43
  • $\begingroup$ @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) $\endgroup$ – Grigory M Aug 7 '10 at 9:49
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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