Pascal's ladder

[Roger|Dyalog]

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, and Patashnik, Concrete Mathematics, page 155.

The Problem

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

      +⌿ c ! d + ⍳n
      ((d-c)+⍳n) ! d+⍳n

For example:

      c←2 ⋄ d←4 ⋄ n←4
      c ! d + ⍳n
6 10 15 21
      +⌿ c ! d + ⍳n
54

Diagrammatically, the sum is that of a diagonal segment of Pascal’s triangle. We call this Pascal’s ladder.



Pascal’s Identity

Pascal’s identity asserts that the sum of two adjacent entries in a row of Pascal’s triangle, is equal to the entry between them on the row below them.



The identity extends to the 1s on the edges of the triangle, if we consider the triangle to be bordered by 0s. The APL primitive ! agrees with this extension:

      0 1 2 3 4 5 ! 5
1 5 10 10 5 1
      ¯1  0 1 2 3 4 5  6 ! 5
0 1 5 10 10 5 1 0

The veracity of Pascal’s identity can be seen by Ken Iverson’s favorite APL expression, Dyalog Blog, 2014-12-03: If x is a row of Pascal’s triangle, then the next row is (0,x)+(x,0).

      x← 1 5 10 10 5 1
      (0,x)+(x,0)
1 6 15 20 15 6 1

Pascal’s Ladder

For the sum in question, can we do better than adding up the n numbers? Yes we can. First, augment the top of the ladder by the number on its right:



By repeated application of Pascal’s identity, the sequence collapses into a single number,

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

This single number (blue, 56) is the sum of the original Pascal’s ladder (green, 6 10 15 21) augmented by the number at the top of the ladder (red, 4). Therefore, the sum of Pascal’s ladder is just the difference between two numbers (blue minus red, 56-4). (One might call this Pascal’s telescoping sum.) That is,

      +⌿ c ! d+⍳n  ←→  ((c+1)!d+n) - (c+1)!d

For example:

      c←2 ⋄ d←4 ⋄ n←4

      c ! d+⍳n
6 10 15 21
      +⌿ c ! d+⍳n
52

      (c+1)!d+n
56
      (c+1)!d
4
      ((c+1)!d+n) - (c+1)!d
52

       (c d n) ← 4 17 30
       +⌿ c ! d+⍳n
1527751
      ((c+1)!d+n) - (c+1)!d
1527751

The derivation works equally well for a ladder “leaning the other way”, that is, for a ladder with a positive slope or with a negative slope. Alternatively, the ladders are the same sequence of numbers so of course their sums would be the same.



Hockey Sticks and Christmas Stockings

In the literature, the sum is called the “hockey stick identity” or “Christmas stocking identity” and equivalent to Pascal’s ladder starting at c=0 or c=d (that is, at a 1 in the triangle). The names derive from that the diagrams are reminiscent of those objects.



Compare the proof presented here with the proofs for hockey sticks, e.g. in the Wikipedia.

That Pascal’s ladder and hockey sticks are equivalent is illustrated by the following diagrams:


A hockey stick is just one application of Pascal’s ladder (one might call it Pascal’s extension ladder ☺).


Conversely, Pascal’s ladder derives from the difference between two hockey sticks that have the same starting point.

Applications

Project Euler is a website with a set of mathematical/programming problems, wherein problem 113 is as follows:

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, 155349.

As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below 10*10.

How many numbers below a googol (10*100) are not bouncy?

Project Euler participants who have solved the problem are honor-bound not to reveal the answer. I will say that Pascal’s ladder is useful for an efficient solution, and that the number of non-bouncy numbers below a googolplex (10*10*100) is 2755731922... (994 decimal digits).

Another application of Pascal’s ladder will be the subject of an upcoming post. Portions of this text previously appeared in the J Wiki essay Pascal’s Ladder, 2006-02-13.