Proof of combination sum What is the proof that C(n,k) = C(n-1,k) + C(n-1,k-1), without the use of matrices to represent them? Thank you very much.
 A: An counting argument will go something like this.
$C(n,k)$ is the number of ways of picking $k$ elements out of a total of $n$, but you can count that in another way. You can fix one element $c$, and you either pick it or not, if you pick it, then you have yet to pick another $k-1$ from the rest, which is done in $C(n-1,k-1)$ ways, and if you don't pick it then you have yet to pick $k$ elemets out of $n-1$ ($c$ is not there anymore), which is done in $C(n-1,k)$ ways. And you can see there is no overlap between the two, as one is counting sets with $c$ in it, and the other one without it, so you can add them up, meaning
$$C(n,k) = C(n-1,k) + C(n-1,k-1)$$
A: Start from the right-hand side, and add the fractions by finding a common denominator:
$$\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}=
\frac{(n-1)!(n-k+k)}{k!(n-k)!}=\frac{n!}{k!(n-k)!}$$

Edit:
\begin{align*}
&\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}\\
&=
\frac{(n-1)!}{k!(n-1-k)!}\cdot \frac{n-k}{n-k}+\frac{(n-1)!}{(k-1)!(n-k)!}\cdot\frac{k}{k}\\
&= \frac{(n-1)!(n-k)+(n-1)!k}{k!(n-k)!}\\
&= \frac{(n-1)!n}{k!(n-k)!}\\
&=\frac{n!}{k!(n-k)!}
\end{align*}
