Who is asking: Student
I am aware that this question was once addressed by your staff before, but the response given does not come as a helpful means to solving this question. Any help you can give would greatly be appreciated. I'm not looking for an easy answer, just directions on how you would go about finding the answer. Thank you. Q.
My previous answer was somewhat abstract so maybe you need to look at an example. Below is the first eight rows of Pascal's triangle with 4 successive entries in the 5th row highlighted. (n = 5, k = 3) I also highlighted the entries below these 4 that you can calculate, using the Pascal triangle algorithm. This leads to the number 35 in the 8th row. (n + k = 8)
Work your way up from the entry in the n + kth row to the k + 1 entries in the nth row. (I,m going to use the notation nCk for n choose k since it is easy to type.)
= 7C4 + 7C5
= 6C3 + 6C4 + 6C4 + 6C5
= 6C3 + 2(6C4) + 6C5
= 5C2 + 5C3 + 2(5C3 + 5C4) + 5C4 + 5C5
= 5C2 +3(5C3) + 3(5C4) + 5C5
= 1(5C2) +3(5C3) + 3(5C4) + 1(5C5)
Hence we have written the entry in the 8th row in terms of the 4 entries in the 5th row with coefficients 1,3,3,1. Does 1,3,3,1 look familiar?
Do this again but starting with 5 successive entries in the 6th row. (n = 6, k = 4)You will have to extend Pascal's triangle two more rows. Write the entry you get in the 10th row in terms of the 5 enrties in the 6th row. What coefficients do you get?I hope this helps,
I think there is an 'image' related to the Pascal Triangle which is central to this.
Let me try with a 'labeling' of the position in the triangle - really coordinates which would describe the powers of (a,b) in (a+b)^n
(0,0) (1,0) (0,1) (2,0) (1,1) (0,2) (3,0) (2,1) (1,2) (0,3) (4,0) (3,1) (2,2) (1,3) (0,4)etc.
I suspect you are familiar with Pascal's theorem which is the case where k=1. This Theorem says than N(m,n) + N(m-1,n+1) = N(m+1,n) where N(m,n) is the number in the corresponding spot of the triangle.
If you take two of these, adjacent, then you can move up two steps:
= N(m+1,n) + N(m, n+1)
= N (m+1,n+1)
So we see N (m+1,n+1) = N(m,n) + 2 N(m-1,n) + N(m-2,n+2) If you look carefully, you will see that the numbers here are starting to look like line 2 of the pascal triangle 1 2 1. If you jump to three steps, you can expand the pieces out - and you will find the coefficients are like those of line 3:
Now there IS a combinatorial / counting story which goes underneath this type of calculation (and lets you organize the numbers in a meaningful way).
If you want to compute the number N(m,n) you are actually counting the number of paths 'down' from (0,0) to (m,n) along a grid structure tracing out the Pascal Triangle:
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \etc. What is happening with the identity is that you are 'tracking' paths to the final point on level n+k - and recording how many of these paths pass through each point along level n. You will find that the identity actually makes sense with this image. Walter Whiteley
To return to the previous page use your browser's back button.