Pascal Triangle

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$$