Our server costs ~$33 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!

8th October 2016, 10:15 (This post was last modified: 8th October 2016, 10:16 by robvalue. )

I don't know Maths is fun! I've always said so

Cool stuff about the binomial! I think I remember working out a similar proof when I was bored at college, many years ago. I can't remember if it was exactly the same.

Feel free to send me a private message.
Please visit my website here! It's got lots of information about atheism/theism and support for new atheists.

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

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.

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.