Hey I am having trouble with this question. We cannot use algebraic proofs:



Our professor gave us a hint for part (a) which was as follows: (xCy means x choose y)

You are on the origin (0,0) in the xy plane and need to get to the point (4,3) by only going right or up. Then there are 7C4 ways to get to (4,3).

For a combinatorial proof I see that you have 7 moves to make to get to (4,3) and you must choose 4 right moves hence you get 7C4. Similarly we know that xCy = xC(x-y) so 7C4 = 7C3 which means you have 7 moves and you must choose 3 up moves to get to (4,3).

So for the RHS, I considered some possible cases to get to (4,3). You must pick one of the following thus we use the sum rule and add all the following cases:

3C3 corresponds to the case where you go right 4 times first, thus you are left with 3 moves and must choose 3 up moves.
4C3 corresponds to the case where you go right 3 times first, thus you are left with 4 moves and must choose 3 up moves.
5C3 corresponds to the case where you go right 2 times first, thus you are left with 5 moves and must choose 3 up moves.
6C3 corresponds to the case where you go right 1 times first, thus you are left with 6 moves and must choose 3 up moves.

Is this a correct combinatorial proof? Do I need to say any more? Would I just do the same thing to prove the general case in part (b)?

Thank you

This is not a correct combinatorial proof. What if you didn't choose to go right at first? You would also need to add this case, but you are also overcounting in your method. For example, your first and fourth cases overlap. In your fourth case, what if you go right once at first and then your 3 up moves end up being the last three moves? This means you will have go right 4 times at first which is the same as your first case.

Try something like this. You have 7 moves: move #1, move #2, move #3, move #4, move #5 , move #6, move #7. Where you only have 4 right moves and 3 up moves

Case 1 : Your fourth right move is on move #4, then you have 3C3 ways to choose the remaining 3 of your right moves (since move #1, move #2, move #3 are the only choices for your remaining 3 right moves)
Case 2: Your fourth right move is on move #5, then you have 4C3 ways to choose the remaining 3 of your right moves (since move #1, move #2, move #3, move #4 are the only choices for your remaining 3 right moves)
Case 3: Your fourth right move is on move #6, then you have 5C3 ways to choose the remaining 3 of your right moves (since move #1, move #2, move #3, move #4, move #5 are the only choices for your remaining 3 right moves)
Case 4: Your fourth right move is on move #7, then you have 6C3 ways to choose the remaining 3 of your right moves (since move #1, move #2, move #3, move #4, move #5, move #6 are the only choices for your remaining 3 right moves)

You should be able to generalize it from this.

Another point of view :

7C4 is the number of possible choices of 4 elements in a set of 7 elements.
Let {a,b,c,d,e,f,g} be that set of 7 elements.

How can you choose 4 elements ?
First, you can choose a, then you still have to choose 3 elements among the 6 remaining : b,c,d,e,f,g. That's 6C3 choices.
Then, you can decide to not choose a, and choose b. You still have to choose 3 elements among the 5 remaining : c,d,e,f,g. That' s 5C3 choices.
Then, you can decide to not choose a nor b, and choose c ...
And so on.
Finally : 7C4 = 6C3 + 5C3 + 4C3 + 3C3

The generalisation is quite easy.

Your way seems a lot simpler, thank you feanur