I was working on a programming problem wherein I had to display pascal's triangle, so I went into binomial coefficients, and find out above formula $\;\displaystyle\binom n{k+1}=\binom n k\cdot\frac{n-k}{k+1}\;$ to fetch the next pascal's number in a row, knowing $1$ will be the first item in the row, I can use it to produce next pascal number in a row.
I tried googling around trying to find the proof but all in vain. Can someone redirect to some links or help me with the solution for this. Thanks in advance.
Best Answer
Here is a bijective proof that $(k+1)\binom n{k+1} = (n-k)\binom n k$. Given $n$ items, we count the number of ways of choosing $k+1$ items, with one marked item. First, we can select $k+1$ items and then mark one of the items in $k+1$ ways. This gives the left hand side. On the other hand, we can choose $k$ items, and then pick one of the remaining $n-k$ items and mark it. This gives the right hand side.