Figuring out a pattern in Pascal's Triangle

Factual Questions
1

This is just idle curiosity; I noticed something and I’m trying to track down a simple way to express it/prove it.

Take a rectangular ‘chunk’ of Pascal’s triangle in the following way: Count off k diagonals (starting from the upper left), up to n numbers in the diagonal. Now at the lower edges, copy the values from the last diagonal edges down one. Do this to both the n-length diagonal chosen last, and for the k-length rightward diagonal at the bottom.

You should have a n+1 x k+1 tilted rectangle with the point on the bottom corner missing. For example, for n=5 and k=3, the copied values on the left are 1,3,6,10,15; on the right bottom are 1,5,15.

It turns out for what I was looking at, the values on the lower right are ‘successes’, which I’ll call ‘s’. (In the 5x3 case, we have s = 1+5+15 = 21) . What I discovered is the relation between the sum of all the values in this near-rectangle and the total successes s:
Total = 2*(n/k + 1)*s - 1

That looks so simple that it seems there must be a fairly easy way to derive it. I’m just not sure how, and I’m looking for any insight into how this comes about.

2

I can’t figure out what you’re saying. Let’s take your example where n is 5 and k is 3. You’re saying that the parallelogram (a more accurate word than “near-rectangle”) that you’re talking about includes all the following numbers:

On the first row of Pascal’s triangle:

1

On the second row:

1 1

On the third row:

1 2 1

On the fourth row:

3 3 1

On the fifth row:

6 4 1

On the sixth row:

10 5

On the seventh row:

15

Is that correct?

You’re adding up all those numbers. (Or perhaps you’re adding up all of them except the 15 at the bottom, since you say that the bottom corner is missing.) The sum of all those numbers is 40. Without the 15, the sum is 25. How do you get either 40 or 25 from the formula you give? I suspect that you forgot some parentheses in the formula. Could you carefully explain the formula?

3

I’ll start with a diagram, since it took me a while to figure out what you meant.


              /\                                                   
             / 1\                                   1              
            /    \                                                 
           / 1   1\                               1   1            
          /        \                                               
         | 1   2   1\                           1   2   1          
          \          \                         /                   
         1 \ 3   3   1\                       1   3   3   1        
            \          \                         /                 
       1   4 \ 6   4   1|                       3   6   4   1      
              \        /                           /         \     
     1   5  10 \10   5/  1                        6  10   5   1    
                \    /                               /     \       
   1   6  15  20 \15/  6   1                       10  15   5      
                  \/                                   / \         
 1   7  21  35  35  21   7   1                       15  15

At left is Pascal’s triangle, with a 3x5 rectangle drawn in. You take this rectangle, and copy the lower two sides downward and outward, giving you a 4x6 rectangle missing its bottom point, as shown at right. You are interested in the sum of all 23 of these numbers, and also in the sum of the three numbers along the lower right.

It’s not hard to find simple expressions for these sums, if you know one binomial identity:
n
(sum) B(m+i,i) = B(m+n+1,n)
i=0
where B(n,r) is the binomial coefficient, the number at row n and column r of Pascal’s triangle). This is easy to understand, and then prove, in terms of Pascal’s triangle. The sum is over the first n+1 numbers along a southeastward “column”; for example, for m=2 and n=4 it’s just the first n+1=5 numbers 1, 3, 6, 10, 15 in the m+1=3rd southeast-moving column from top, boxed below.


               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  
               +--+

The sum of these numbers is just the binomial coefficient southwestward from the bottommost of these–35, in this case. The proof should be obvious from the properties of Pascal’s triangle.

Now you can use this identity to write your “success” sum as a single binomial coefficient. Using the identity twice you can express the “total” sum in terms of a single binomial coefficient as well. Then the result you’re looking for follows naturally.

4

That’s a beautiful picture and exactly what I was talking about, Omphaloskeptic. Wendell, I think you missed the ‘copied’ lines that I added, which change the sum.

Just to make sure I have this right:

The sum of the actual chunk taken out of the triangle is equal (almost) to a “southwest” diagonal of length k+1 starting at the end of row n-1. The ‘almost’ is needed because the first value (1) is not included in the sum. But that will get subtracted out later, so for now I’ll go with this as the sum of that box.

In terms of the coefficients, we have sum(i=0->k) B(n-1+i,n-1), which using the identity for a diagonal in this direction yields B(n+k,n). The diagram shows that this is the value that the parallelogram ‘points to’ at its bottom (that is, the next value vertically down from the lowest corner).



                /\                                                   
               / 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
                   +--+ 

The sum of the boxed values is equal to the marked coefficient (56), less 1.

The two copied legs are equal to the number just below and to the right of the box (for the ‘success’ leg), and just below and to the left for the other one. These are 35 and 21 in the 5 x 3 example. But the sum of these two is just the same single binary coefficient for the box’s sum B(n+k,n).

Therefore the total values in my special ‘near-parallelogram’ are
Total = 2*B(n+k,n) - 1
with the extra 1 being subtracted out.

To put this in terms of the total ‘successes’, note that s = B(n+k-1,n).

Dividing gives us:

B(n+k,n)

B(n+k-1,n)

(n+k)!/((n+k-n)!n!)

(n+k-1)!/((n+k-1-n)!n!

(n+k)!(k-1)!

(n+k-1)!k!

(n+k)

k
Thus B(n+k,n) = (n+k)/k * B(n+k-1,n) and the formula makes sense.

Thanks for the help.

5

Yep, good job.

Just for completeness, do you see how to derive that binomial identity I gave? It’s useful enough that it’s worth understanding how to prove it so you can rederive it when you need it. (As an example of its usefulness, you can derive formulas for the sum of powers, like 1+4+9+16+…+n[sup]2[/sup] and 1+8+27+64+…+n[sup]3[/sup], using these identities.)

6

Yeah, it’s easy to see by “visual induction” that if you have a partial sum adding to the next ‘lower’ value, the next value in the sum is going to just be its neighbor in the Triangle. The triangle is built by adding neighbors, so the next partial sum will be in the spot indicated.

Proving that formally probably requires using the binomial formula or looking at the principle by which a term in Pascal’s triangle equals the choose function, and I’m more likely to remember the visual method of deriving it more easily.

One more thing - when searching for pre-built Triangles one of the first that comes up is this page. I think this quote says it best :

Enjoy.

7

Right, it’s easy to convert this idea to a standard inductive proof; it’s just nice to have a visual mnemonic for it.

I guess the quote is technically true, anyway.

8

That website has a lot of stuff that is clearly over my head, but the more I read the more I suspected it was some kind of mystical new-age thing that really had nothing to do with mathematics.

Then I came across, “What is 1^0? There are different opinions between mathematicians.” I’m pretty sure there’s no real dispute that 1^n = 1 for all n and that k^0 = 1 for all non-zero k, so I really don’t get this line at all. Did he mean 0^0? And what the hell does it have to do with what he’s talking about in that section?