Pascal Triangle
Warning
This post is more than a year old. Information may be outdated.
In Probability,
$$ {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} $$
Proof
$$ {n-1 \choose k-1} + {n-1 \choose k} $$
$$ = {(n-1)! \over {(k-1)!~(n-k)!}} + {(n-1)! \over {(n-1-k)!~k!}} $$
$$ = ({k \over k} {(n-1)! \over {(k-1)!~(n-k)!}}) + ({(n-1)! \over {(n-1-k)!~k!}} {(n-k) \over (n-k)}) $$
$$
= {{{(n-1)!} (k + n - k)} \over {k!(n-k)!}} = {n! \over {k!(n-k)!}}
$$
$$ = {n \choose k} ~~~~~~~~~~ \blacksquare $$