Let $\left(\!\!{n\choose k}\!\!\right)=\binom{n+k-1}k$, prove $\left(\!\!{n\choose k}\!\!\right)=\sum_{i=0}^k\ \left(\!\!{n-1\choose i}\!\!\right)$

183 Views Asked by At

I need help proving this. Let $n$ and $k$ be positive integers, and let $$\left(\!\!{n\choose k}\!\!\right) ={n+k -1\choose k},$$ prove:

$$\left(\!\!{n\choose k}\!\!\right) = \sum_{i=0}^{k}\ \left(\!\!{n-1\choose i}\!\!\right).$$

I'm thinking I need to show that the equation $$\sum_{i=0}^{k}\ \left(\!\!{n-1\choose i}\!\!\right) = {n+k -1\choose k}$$ is true but I am unsure how to make this jump.