Grove HSC 3U book EX 10.1 Q15 Pascal Triangle identity

Prove $\left({n\atop k}\right)=\left({n-1\atop k-1}\right)+\left({n-1\atop k}\right)$


LHS $=\left({n\atop k}\right)={n!\over k! (n-k)!}$

RHS $=\left( {n-1\atop k-1}\right)+\left({n-1 \atop k}\right)$

$={(n-1)!\over (k-1)! (n-1-(k-1))!}+ {(n-1)!\over k! (n-1-k)!}$

$={(n-1)!\over (k-1)! (n-k)!}+ {(n-1)!\over k! (n-k-1)!}$

$={k(n-1)!\over k(k-1)! (n-k)!}+ {(n-1)!(n-k)\over k! (n-k)(n-k-1)!}$

$={k(n-1)!\over k! (n-k)!}+ {(n-1)!(n-k)\over k! (n-k)!}$

$={k(n-1)! + (n-1)!(n-k)\over k! (n-k)!}$

$={(n-1)!(k + (n-k))\over k! (n-k)!}$

$={(n-1)!n\over k! (n-k)!}$

$={n!\over k! (n-k)!}$

=LHS

as required.