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.