Summation of combinations 
Possible Duplicate:
simple binomial theorem proof 

Why is $${6\choose 0} + {7\choose 1} + \ldots + {n+6 \choose n} = {n+7 \choose n}\;?$$
 A: HINTS: The algebraic argument is a proof by induction: verify the equality for $n=0$, and show that if $${6\choose 0} + {7\choose 1} + \ldots + {n+6 \choose n} = {n+7 \choose n}\;,$$ then $${6\choose 0} + {7\choose 1} + \ldots + {(n+1)+6 \choose {n+1}} = {(n+1)+7 \choose {n+1}}\;.$$ This is a pretty straightforward application of the Pascal’s triangle identity.
For the combinatorial argument, observe that $\binom{n+7}n=\binom{n+7}7$ is the number of ways to choose a $7$-element subset of $\{1,2,\dots,n+7\}$, and $\binom{k+6}k=\binom{k+6}6$ is the number of ways to choose a $7$-element subset of $\{1,\dots,n+7\}$ whose largest element is the number $k+1$. That is, to choose a $7$-element subset whose largest element is $10$, you first choose $10$, and then you have to choose $6$ of the numbers $\{1,\dots,9\}$.
A: The standard recursive formula for binomial coefficients is
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
There is a technique for recursion called "unrolling," where you repeatedly substitute a recurrence into its equation for itself. Here if we reverse the terms and then substitute repeatedly we get:
$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$
$\binom{n}{k} = \binom{n-1}{k} + \binom{n-2}{k-1} + \binom{n-2}{k-2}$
$\vdots$
$\binom{n}{k} = \binom{n-1}{k} + \binom{n-2}{k-1} + \binom{n-3}{k-2} + \cdots + \binom{n-k}{0}$
