Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 7:37

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
I don't see it. –  George Newton Mar 12 at 3:34
    
@GeorgeNewton I added some detail –  angryavian Mar 12 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)$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.