Prove that C(n-1,k-1) + C(n-1,k)= C(n,k)
Proof strategy.
For this proof, we will take the left hand side (LHS) and transform it into the right hand side (RHS) via a series of equalities.
Now, you will see some transformations of factorials (factorials have the ! sign) in this proof. Most notably, we will be making use of the fact that n!=n*(n-1)! (Lipschutz, Discrete Mathematics, 1992, pg 244). To understand our fact in bold, suppose we have 4!. Now, 4! is equal to 4*3*2*1=24. Now, observe that if we factor out the four, we get 4*(4-1)! or 4*3! or 4*(3*2*1) or 4*6=24 (note 3!=3*2*1=6). Thus, in both instances we got the same result. Also, on a side note, remember that 1! and 0! both equal one.
Now, remember anything of the form C(this,that) can be represented as: (this)!/[(that)!*(this - that)!]. Also note that C(n,k)= n!/[k!*(n-k)!]. (Hammack, Book of Proof, 2013, pg 76).
Proof
1)Thus, C(n-1,k-1) + C(n-1,k) =(n-1)!/[(k-1)!*((n-1) - (k-1))!] + (n-1)!/[k!*(n-1-k)!]
2)=(n-1)!/[(k-1)!*(n-k)!] + (n-1)!/[k!*(n-k-1)!]
Via the commutative law of addition, we can rewrite n-1-k as n-k-1, as it represents the same sum: n+(-k) + (-1) = n+(-1)+(-k). Now, in order to get a common denominator in both terms, we will need to multiply the first fraction by k/k and the second fraction by (n-k)/(n-k). This will make sense, in a bit.
3)=k*(n-1)!/[k*(k-1)!*(n-k)!] + (n-k)*(n-1)!/[k!*(n-k)*(n-k-1)!].
Now use the fact that n!=n*(n-1)! and apply it to the portions in bold. Also, notice in the second fraction, that via the commutative law of multiplication, we can multiply the three terms in the denominator in any order and get the same product, so writing the denominator as k!*(n-k)*(n-k-1)! makes it easier to spot the rule.
4)= k*(n-1)!/[k!*(n-k)!] + (n-k)*(n-1)!/[k!*(n-k)!]. Notice that we now have a common denominator.
5)=k*(n-1)! + (n-k)*(n-1)!/[k!*(n-k)!] Now factor (n-1)! out of the numerator
6)=(n-1)!*(k+n-k)/[k!*(n-k)!] simplify the numerator
7)= n*(n-1)!/[k!*(n-k)!] use our fact in bold
8)=n!/[k!*(n-k)!]
9)=C(n,k)
Hence, we have transformed the LHS into the RHS, so the proof is complete.
Proof strategy.
For this proof, we will take the left hand side (LHS) and transform it into the right hand side (RHS) via a series of equalities.
Now, you will see some transformations of factorials (factorials have the ! sign) in this proof. Most notably, we will be making use of the fact that n!=n*(n-1)! (Lipschutz, Discrete Mathematics, 1992, pg 244). To understand our fact in bold, suppose we have 4!. Now, 4! is equal to 4*3*2*1=24. Now, observe that if we factor out the four, we get 4*(4-1)! or 4*3! or 4*(3*2*1) or 4*6=24 (note 3!=3*2*1=6). Thus, in both instances we got the same result. Also, on a side note, remember that 1! and 0! both equal one.
Now, remember anything of the form C(this,that) can be represented as: (this)!/[(that)!*(this - that)!]. Also note that C(n,k)= n!/[k!*(n-k)!]. (Hammack, Book of Proof, 2013, pg 76).
Proof
1)Thus, C(n-1,k-1) + C(n-1,k) =(n-1)!/[(k-1)!*((n-1) - (k-1))!] + (n-1)!/[k!*(n-1-k)!]
2)=(n-1)!/[(k-1)!*(n-k)!] + (n-1)!/[k!*(n-k-1)!]
Via the commutative law of addition, we can rewrite n-1-k as n-k-1, as it represents the same sum: n+(-k) + (-1) = n+(-1)+(-k). Now, in order to get a common denominator in both terms, we will need to multiply the first fraction by k/k and the second fraction by (n-k)/(n-k). This will make sense, in a bit.
3)=k*(n-1)!/[k*(k-1)!*(n-k)!] + (n-k)*(n-1)!/[k!*(n-k)*(n-k-1)!].
Now use the fact that n!=n*(n-1)! and apply it to the portions in bold. Also, notice in the second fraction, that via the commutative law of multiplication, we can multiply the three terms in the denominator in any order and get the same product, so writing the denominator as k!*(n-k)*(n-k-1)! makes it easier to spot the rule.
4)= k*(n-1)!/[k!*(n-k)!] + (n-k)*(n-1)!/[k!*(n-k)!]. Notice that we now have a common denominator.
5)=k*(n-1)! + (n-k)*(n-1)!/[k!*(n-k)!] Now factor (n-1)! out of the numerator
6)=(n-1)!*(k+n-k)/[k!*(n-k)!] simplify the numerator
7)= n*(n-1)!/[k!*(n-k)!] use our fact in bold
8)=n!/[k!*(n-k)!]
9)=C(n,k)
Hence, we have transformed the LHS into the RHS, so the proof is complete.