Essays/Pascal's Ladder
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
- Hockey Stick Theorem or Christmas Stocking Theorem
Contributed by Roger Hui.