Take a row of Pascals Triangle. Write a second copy of the row below it but with an offset. Multiply each pair of numbers and then sum these products. (A missing number is considered to be zero.)
The result is number further down the Triangle.
Can you explain or prove the result?
Example with the 4th row and offset by 1:
1 4 6 4 1 0
0 1 4 6 4 1
0 + 4 + 24 + 24 + 4 + 0 = 56 which is in row 8.
Ooh! Ooh! I know this one! In 1976 I was in the first session of Operations Research I class, and the Professor (who I thought didn't have much on the ball) stunned me by giving a geometric proof that
n
______
C(n,i)*C(n,i) = C(2n,n)
/
/
------
i=0
I never underestimated him again. And now, Jer is asking for a more general proof of the same situation.
Basically, consider a grid of city blocks (all streets are North south or East West) which goes from (0,0) to (n+k, n-k). Traveling only along the streets, we can go from the origin to (n+k, n-k) in 2n blocks.
And how many different direct paths are there? Well,we need to go North (n-k) times and East (n+k) times, and we can do them in any sequence. There are C(2n,n-k) ways to pick (n-k) objects out of 2n, so there are C(2n,n-k) direct paths from (0,0) to (n+k, n-k).
Or here is another way to calculate it. Count how many different ways there are to reach a "halfway" point, and then how many paths from there, and do this for all the different halfway points. For example, let n = 4 and k = 1. Then we are trying to get from (0,0) to (5,3). Our "halfway" points are (1,3),(2,2),(3,1) and (4,0). All are 4 blocks from the two corners, as the crow walks.
There are 4 ways to get from (0,0) to (5,3) via (1,3), because there are 4 direct ways to get from (0,0) to (1,3) and only 1 direct way to get from (1,3) to (5,3).
Similarly, there are 24 ways to get from (0,0) to (5,3) via (2,2), because there are 6 (ie, C(4,2)) direct ways to get from (0,0) to (2,2) and 4 (ie, C(4,1)) direct ways to get from (2,2) to (5,3). 6*4 = 24 paths.
And 24 more paths via (3,1). And 4 more paths via (4,0). 56 total.
See where we are going?
In other words, we have proved that
3
______
C(4,i)*C(4,i+i) = C(8,3)
/
/
------
i=0
And the same geometric argument proves that
n-k
______
C(n,i)*C(n,i+k) = C(2n,n-k)
/
/
------
i=0
The right hand side counts the number of paths between diagonal corners of an (n-k)*(n+k) city grid, without worrying about where the midway point is. The left-hand side counts the number of paths through each halfway point, and sums them up. But the two have to be equal. And the result has to be in a row on a pascal triangle
Professor Richard Foster is the best teacher I ever had.
Edited on October 5, 2011, 8:14 am
Happy 35th anniversary (spoiler)
