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
80which 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.
Contributed by RogerHui.