Essays/Pascal's Ladder

From J Wiki
Jump to: navigation, search

The numbers in Pascal's triangle satisfy, practically speaking, infinitely many identifies, 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
+/ (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
   (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.