Number of unique paths in Pascal's Triangle

[tarmon.gaidon]

Homework Statement

Let pascal(n,i) be the value of the i^th element of the n^th row of Pascal's triangle. Using induction show that the number of unique paths from entry {0,0} to entry {n,i} in Pascal's triangle is equal to pascal(n,i).

The Attempt at a Solution

The base case n=1 seems easy enough to prove. It is obvious that there is only one path to each of the two elements in the n^th row.

It was brought to my attention that each value at {n,i} in Pascal's triangle can be represented by _nC_i.

That being said I am not sure how to precede. I am just looking for some insight on how to continue.

Any suggestions would be greatly appreciated.

 

[mfb]

Hint: How (from which elements) can you reach the i^th element in the n^th row, if movement is restricted in the appropriate way?