Pascal’s rule proof

We need to show

$\displaystyle\binom{n}{k}+\binom{n}{k-1}$

$\displaystyle=$

$\displaystyle\binom{n+1}{k}$

Let us begin by writing the left-hand side as

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

Getting a common denominator and simplifying, we have

$\displaystyle\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}$	$\displaystyle=$	$\displaystyle\frac{(n-k+1)n!}{(n-k+1)k!(n-k)!}+\frac{kn!}{k(k-1)!(n-k+1)!}$
	$\displaystyle=$	$\displaystyle\frac{(n-k+1)n!+kn!}{k!(n-k+1)!}$
	$\displaystyle=$	$\displaystyle\frac{(n+1)n!}{k!((n+1)-k)!}$
	$\displaystyle=$	$\displaystyle\frac{(n+1)!}{k!((n+1)-k)!}$
	$\displaystyle=$	$\displaystyle\binom{n+1}{k}$