I'm asked to show that $\displaystyle {n \choose k} = \sum^{k+1}_{i=1}{n-i \choose k-i+1}$ for all positive integers0 <= k <= n.I've tried using pascal's identity in combination with mathematical induction, but I can't seem to prove this. Please help.