Re: Divisibility property of binomial coefficients (Hoggatt triangles)

From: George Russell (ger_at_tzi.de)
Date: 08/23/04 

Date: Mon, 23 Aug 2004 14:01:19 +0000 (UTC)

tchow@lsa.umich.edu wrote:
> Is it true, and if so how does one prove, that
>
> (n choose m) * (n choose m+1) * ... * (n choose m+k)
>
> is divisible by
>
> (n choose 0) * (n choose 1) * ... * (n choose k) ?
>
> This problem is associated with so-called "Hoggatt triangles" and
> "Hoggatt sequences" but the papers containing those keywords appear
> to assert the above divisibility property without proof.

Let p be prime. For a natural number r, let Dp(r) be the highest integer i
such p^i | r.

It is fairly straightforward to prove that
(1) If m>=0, Dp(m!) = sum_{k=0} floor (m/p^k)
(2) If n>=m>=0 and the digits of n are n1 n2 n3 ... nt and the digits of m,
when padded out with leading zeros as necessary, are m1 m2 m3 ... mt
then
Dp(n choose m) is the number of j with mj > nj

(This is due to Kummer apparently, see
    http://mathworld.wolfram.com/BinomialCoefficient.html
though I have stated it in a different way.
)

Example: 210 = 10 choose 6 = (in base 2)
        1010
choose 0110
with ^ one 2. Hence 10 choose 6 is divisible by 2 but not 4.

(3) I think the result now follows quite easily, by looking at the individual
digits.