## Wednesday, November 18, 2009

### Pascal's Rule

Theorem: Pascal's Rule

C(n,k) + C(n,k-1) = C(n+1,k)

where:

Proof:

(1) We can find a common denominator for C(n,k) and C(n,k-1) so that we have:

(2) So that:

(3) To complete the proof, we note that: n-k+1 = n+1-k so that we have:

= C(n,k+1)

QED

References

#### 1 comment :

Anonymous said...

If you choose k numbers from n+1 you could choose k numbers from n (the largest number would not be included) or you could include the number n+1 so for the remaining elements you would choose k-1 elements from n.