Row 0 : 1
Row 1 : 1 1
Row 2 : 1 2 1
Row 3 : 1 3 3 1
Row 4 : 1 4 6 4 1
Etc.
Take a row of Pascal's Triangle.
Write a second copy of the row below it and place 0.
Multiply each pair of numbers and
then sum these products.
For example,
1 1 0
0 1 1
----------------
0 2 0
0 + 2 + 0 = 2 (it is in row 2)
1 2 1 0
0 1 2 1
-------------
0 2 2 0
0 + 2 + 2 + 0 = 4 (in row 4)
1 3 3 1 0
0 1 3 3 1
----------------------
0 3 9 3 0
0 + 3 + 9 + 3 + 0 = 15 (in row 6)
1 4 6 4 1 0
0 1 4 6 4 1
-----------------------------
0 4 24 24 4 0
0 + 4 + 24 + 24 + 4 + 0 = 56 (in row 8)
etc.
We want to prove that
ReplyDeletesum (k=0 to n-1) C(n,k)*C(n,k+1) = C(2n,n-1).
This statement has a combinatorial proof.
C(2n,n-1) is the number of subsets of {1,...,2n} that have exactly (n-1) elements. To choose such a subset, we may select k of the first n elements {1,...,n}, and delete k+1 of the last n elements {n+1,...,2n}. We obtain all (n-1)-subsets as k ranges from 0 to n-1.