# 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.

-
Actually I would find it very hard to prove Pascal's recurrence in any way that uses matrices at all! Also there is no such thing as the proof of an identity; there are many possibilities. – Marc van Leeuwen Mar 12 '14 at 7:37

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*}

-
I don't see it. – George Newton Mar 12 '14 at 3:34
@GeorgeNewton I added some detail – angryavian Mar 12 '14 at 3:38

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

-