Home » Blog » Prove the law of Pascal’s triangle

Prove the law of Pascal’s triangle

by RoRi

Prove that

    \[ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}. \]

Proof. Starting on the right and expanding the terms using the definition of binomial coefficients,

    \begin{align*} \binom{n}{k-1} + \binom{n}{k} &= \frac{n!}{(k-1)!(n-(k-1))!} + \frac{n!}{k!(n-k)!} \\ &= \frac{(n!)k + (n!)(n-k+1)}{k!(n-k+1)!} & (\text{common denominator})\\ &= \frac{(n!)(k+n-k+1)}{k!(n+1-k)!} \\ &= \frac{(n!)(n+1)}{k!(n+1-k)!} \\ &= \frac{(n+1)!}{k!((n+1)-k)!} \\ &= \binom{n+1}{k} & (\text{Def. of bin. coeff.}). \qquad \blacksquare \end{align*}

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):