Essays/Pascal's Ladder

From J Wiki
Jump to navigation Jump to search

The numbers in Pascal's triangle satisfy, practically speaking, infinitely many identities, so it's not too surprising that we can find some surprising relationships by looking closely.
                            — Graham, Knuth, & Patashni, Concrete Mathematics, page 155.

We consider the following sums of binomial coefficients, for c <: d :

+/ c ! d + i.n
+/ ((d-c) + i.n) ! d + i.n

What are these sums? To use a particular example, the terms of the sums are

   c=:2 [ d=:4 [ n=:5
   c ! d + i.n
6 10 15 21 28
   ((d-c) + i.n) ! d + i.n
6 10 15 21 28

and are adjacent entries in Pascal's triangle:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

If we add the extra term 4 in Pascal's triangle to the right of 6 , (or to the left of 6 in the mirror image of the above diagram reflected about the vertical axis), the sum collapses into a single binomial coefficient:

        6 4
      10         10 10
    15         15         15 20
  21         21         21        21 35
28         28         28        28        28 56
                                            84

   +/ 6 10 15 21 28
80
   3!9
84
   (3!9) - 3!4
80

which is (1+c)!d+n,  from which the original extra term (1+c)!d must be subtracted. That is,

(+/ c ! d + i.n)     = ((1+c)!d+n) - (1+c)!d
(+/ (c+i.n) ! d+i.n) = ((c+n-1)!d+n) - (c-1)!d

"Pascal's ladder" or "Pascal's telescoping sum" would be good descriptions of this.

Of course, to make the derivation rigorous and respectable, one would have to employ a proof by (say) induction. The details of such a proof are left as an exercise for the reader.



See also



Contributed by Roger Hui.